Форум Всеукраїнської інтернет-олімпіади NetOI

Задача Unizero.
Припустимо, що у нас є поле 00...00 (довжиною n). І за умовою задачі нам потрібно розтавити одиниці (більш ніж одну) так, щоб не суперечило даній умові. Випадки розміщення будуть наступні:
1) Через один нуль (00..01010..000): щоб не порушити умову, будем розтавляти такі послідовності, як: 101, 10101,1010101 і т.д. Щоб знайти кількість позицій для кожної такої послідновності в нашому полі, потрібно до загальної суми додати різницю довжини поля і дожину вибраної послідовності + 1. Для кращого розуміння розглянемо поле довжиною 6 (000000). Кількість позицій довжиною в 3 (101) = 6 - 3 + 1 (позиції: 101000, 010100,001010,000101), довжиною в 5 (10101) = 6-5+1 (101010, 010101). Отже відповідь для послідовностей "через один нуль" буде : (n-2)+(n-4)+(n-6)... .
2) Через к нулів (00..0100..{k}..0010..00). Порядок обчислення буде аналогічний прикладу через один нуль, а саме сума = (n-(k)+1)+(n-(2*k)+1)+(n-(3*k)+1)...
Замітимо, що коли будемо підраховувати загальну суму усіх (n-i+1), даний вираз (n-i+1), де 1<i<n, буде зустрічатися рівно числу кільності дільників числа i.
Отже, для знаходження відповіді на поставлену задачу, потрібно підрахувати суму( (n-i)*(кількість_дільників(i)) ).
Код вийшов наступний:
for(int i=2;i<n;i++)
        for(int j=i;j<n;j+=i)
            a[j]++;
    ll sm = 0;
    for(int i=2;i<n;i++)
    sm+=a[i]*(n-i);
    cout<<sm;
Напевно це рішення не є подібним авторському, але ,не знаю чому, дане рішення бере нуль балів (Time limit), хоча відправка після завершення 2 туру показала, що мінімальний час виконання:
(0.06 c - 0.07 c) - і це 19 тестів, 20 тест - 0,1 с, і остальні по 0,52 с.
Чесно кажучи, не розумію таку систему оцінювання

Відредаговано PAS99 (2015-12-22 10:47:40)

PAS99 написав:

Задача Unizero.
Припустимо, що у нас є поле 00...00 (довжиною n). І за умовою задачі нам потрібно розтавити одиниці (більш ніж одну) так, щоб не суперечило даній умові. Випадки розміщення будуть наступні:
1) Через один нуль (00..01010..000): щоб не порушити умову, будем розтавляти такі послідовності, як: 101, 10101,1010101 і т.д. Щоб знайти кількість позицій для кожної такої послідновності в нашому полі, потрібно до загальної суми додати різницю довжини поля і дожину вибраної послідовності + 1. Для кращого розуміння розглянемо поле довжиною 6 (000000). Кількість позицій довжиною в 3 (101) = 6 - 3 + 1 (позиції: 101000, 010100,001010,000101), довжиною в 5 (10101) = 6-5+1 (101010, 010101). Отже відповідь для послідовностей "через один нуль" буде : (n-2)+(n-4)+(n-6)... .
2) Через к нулів (00..0100..{k}..0010..00). Порядок обчислення буде аналогічний прикладу через один нуль, а саме сума = (n-(k)+1)+(n-(2*k)+1)+(n-(3*k)+1)...
Замітимо, що коли будемо підраховувати загальну суму усіх (n-i+1), даний вираз (n-i+1), де 1<i<n, буде зустрічатися рівно числу кільності дільників числа i.
Отже, для знаходження відповіді на поставлену задачу, потрібно підрахувати суму( (n-i)*(кількість_дільників(i)) ).
Код вийшов наступний:
for(int i=2;i<n;i++)
        for(int j=i;j<n;j+=i)
            a[j]++;
    ll sm = 0;
    for(int i=2;i<n;i++)
    sm+=a[i]*(n-i);
    cout<<sm;
Напевно це рішення не є подібним авторському, але ,не знаю чому, дане рішення бере нуль балів (Time limit), хоча відправка після завершення 2 туру показала, що мінімальний час виконання:
(0.06 c - 0.07 c) - і це 19 тестів, 20 тест - 0,1 с, і остальні по 0,52 с.
Чесно кажучи, не розумію таку систему оцінювання

Из вашего разбора уже видно, что нужно посчитать сумму арифметических прогрессий с шагом - 2, 3 и т.д. Поскольку сумма АП считается за О(1). То такое решение не превосходило бы О(n).

На всякий случай приведу полнобальные решения (они отличаются от того, что я посылал на тур):

Unizero

#include <iostream>

int main()
{
    long long n,c,i,ans=0;
    std::cin>>n;
    for(i=2;i<n;++i)
    {
        c=(n+i-1)/i;
        ans+=n*(c-1)-i*c*(c-1)/2;
    }
    std::cout<<ans;
    return 0;
}

Идея: формула решения , внутренняя сумма раскрыта для ускорения вычислений. Желающие могут попробовать раскрыть и внешнюю сумму.
Сложность: O(n) времени, O(1) памяти.

Walk

#include <cstdio>

long long egcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
    {
        x=a<0?-1:+1;
        y=0;
        return a<0?-a:a;
    }
    long long c=a/b;
    long long p,q;
    long long ret=egcd(b,a%b,p,q);
    x=q;
    y=p-c*q;
    return ret;
}

long long inv_m(long long a,long long b)
{
    long long x,y;
    egcd(a,b,x,y);
    return ((x%b)+b)%b;
}

long long a(long long n)
{
    const long long m=1000000007LL;
    long long ret=0;
    long long c=1;
    for(long long i=0;i<n+1;++i)
    {
        ret=(ret+c)%m;
        c=(((c*2*(2*i+1))%m)*inv_m(i+2,m))%m;
    }
    return ret;
}

int main()
{
    long t;
    scanf("%ld",&t);
    printf("%ld",(long)a(((long long)t-1LL)/2LL));
    return 0;
}

Идея: беглый взгляд на OEIS находит выражение для ответа через сумму чисел Каталана. Для чисел Каталана есть рекуррентная формула, поэтому (частичная) сумма и следующее число Каталана считаются вместе. Формула содержит деление, но т. к. 1000000007 - простое число, то мы имеем право "делить по модулю", т. е. умножать на обратное по модулю 1000000007.
Сложность: O(t) времени, O(1) памяти.

Hanoy2015

#include <iostream>
#include <algorithm>

int main()
{
    int N;
    int a[64];
    int c=0;
    unsigned long long answer=0;
    std::cin>>N;
    for(int i=0;i<N;++i)
        std::cin>>a[i];
    std::sort(a,a+N);
    for(int i=N-1;i>=0;--i)
        answer+=1LL<<(c+=(i<N-1&&a[i]!=a[i+1]));
    std::cout<<answer;
    return 0;
}

Идея: сортируем диски, дальше - обычные Ханойские башни, но стопка из k одинаковых дисков воспринимается как 1 диск со стоимостью перемещения в k ходов.
Сложность: O(N) времени, O(1) памяти.

Schoolnet2015n

#include <cstdio>

static const int MAX_N=1000;

bool n[MAX_N][MAX_N]={{0}};

int c[MAX_N]={0};
int s[MAX_N]={0};

int N;

int dfs(int i)
{
    int ret=1;
    if(c[i]) return 0;
    c[i]=1;
    for(int j=0;j<N;++j)
        if(n[i][j])
            ret+=dfs(j);
    return ret;
}

int main()
{
    int a,b=0,c;
    scanf("%d",&N);
    for(int i=0;i<N;++i)
        for(int j=0;j<N;++j)
        {
            scanf("%d",&a);
            n[i][j]=a;
        }
    for(int i=0;i<N;++i)
    {
        if((a=dfs(i))>b)
        {
            b=a;
            c=i+1;
        }
    }
    printf("%d %d",b,c);
    return 0;
}

Идея: стандартная задача.
Сложность: O(N^2) времени, O(N^2) памяти.

FactZero

#include <cstdio>

int main()
{
    long n,k;
    long m=0;
    long p[32]={};
    long c[32]={};
    long b=2000000000L;
    scanf("%ld%ld",&n,&k);
    for(long d=2,t=k;t>1;++d)
    {
        if(t%d==0)
        {
            while(t%d==0)
            {
                ++c[m];
                t/=d;
            }
            p[m++]=d;
        }
    }
    for(int i=0;i<m;++i)
    {
        long q=n;
        long t=0;
        while(q>0) {q/=p[i];t+=q;}
        t/=c[i];
        if(t<b) b=t;
    }
    printf("%ld\n",b);
    return 0;
}

Идея: раскладываем k на простые множители, смотрим, с какой кратностью каждый множитель входит в n!. Ищем минимум (с учётом кратностей в k).
Сложность: O(k+log(n)*log(k)) времени, O(log(k)) памяти.

Правка: временная сложность в FactZero.

Відредаговано FordPerfect (2016-01-12 17:50:45)

Hanoy2015
Важко конкурувати з лаконічністю рядка

answer+=1LL<<(c+=(i<N-1&&a[i]!=a[i+1]));

в рішенні FordPerfect, але насмілюсь викласти і своє повнобальне рішення.

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
   int N, a, n[10001]={};
    cin >> N;
    for (int i=1; i<=N; i++)
        {
            cin>>a;
            n[a]++;
        }

long double res=0;
for (int i=10000,k=0; i>0; i--)
{
    if (n[i]!=0)
    {
        res+=pow(2.0,k)*n[i];
        k++;
    }
}

cout << (unsigned long long)res;
return 0;
}

Алгоритм такий:
В класичному варіанті кількість перекладань дорівнює: 2^n -1
Якщо перекладати диски пачками, то так воно і буде (n – кількість «пачок»).
Але кожна пачка перекладається поштучно, тобто найбільші диски перекладаються один раз (2^0*а), де а-кількість найбільших дисків, далі 2^1*в, де в – кількість менших дисків, далі 2^2*с, де с – кількість ще менших дисків і т.д.
1) Підраховуємо яких і скільки дисків є за допомогою додаткового масиву n[10000] під час уведення.
2) Потім знайдемо суму перекладань.
Обрахунки виконуємо в дійсних числх, а результат виводимо в максимально можливому типі цілих.

Відредаговано LVV (2015-12-24 06:31:12)

код розвязку задачі Unizero на основі знаходження сум арифметичних прогресій:

var l,f:int64;
n,i,j,k,nach:longint;
begin
read(n);
n:=n-2;l:=0;k:=1;
while (n>0)do begin
   if k=1 then begin
                   f:=n;
                   nach:=1;
                   end else begin
                      nach:=n mod k;
                       if nach=0 then nach:=k;
                      f:=(n-nach)div k+1;
                   end;
   l:=l+(nach+n)*f div 2;
   n:=n-2;k:=k+1;
end;
writeln(l);
end.

протокол тестування:
Тест    Результат    Час роботи
00    PASSED (+0)    0.01 с
01    PASSED (+1)    0.01 с
02    PASSED (+1)    0.01 с
03    PASSED (+1)    0.01 с
04    PASSED (+1)    0.01 с
05    PASSED (+1)    0.01 с
06    PASSED (+1)    0.01 с
07    PASSED (+1)    0.01 с
08    PASSED (+1)    0.01 с
09    PASSED (+1)    0.01 с
10    PASSED (+1)    0.01 с
11    PASSED (+2)    0.01 с
12    PASSED (+2)    0.01 с
13    PASSED (+2)    0.01 с
14    PASSED (+2)    0.01 с
15    PASSED (+2)    0.01 с
16    PASSED (+2)    0.01 с
17    PASSED (+2)    0.01 с
18    PASSED (+2)    0.01 с
19    PASSED (+2)    0.02 с
20    PASSED (+2)    0.04 с
21    PASSED (+2)    0.04 с
22    PASSED (+2)    0.09 с
23    PASSED (+2)    0.10 с
24    PASSED (+2)    0.14 с
25    PASSED (+2)    0.17 с