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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2015-12-22 10:10:53

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 308

Розбір рішень

Журі традиційно розмістить архів рішень майже через пів-року.
Може хто зараз поділиться своїми думками і рішеннями?

Поза форумом

 

#2 2015-12-22 10:45:20

PAS99
Новий користувач
Зареєстрований: 2015-12-21
Повідомлень: 3

Re: Розбір рішень

Задача 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 с.
Чесно кажучи, не розумію таку систему оцінювання sad

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

Поза форумом

 

#3 2015-12-22 11:59:43

by_andreyko
Новий користувач
Зареєстрований: 2015-11-14
Повідомлень: 4

Re: Розбір рішень

Задача Unizero.
Ніби все добре але проходить 26 з 40. Допоможіть, не знаю в чому пробема.
ПС. Тормозить на більших тестах


var k,l:int64;
procedure func(k,i,r:int64; var l:int64);
var b,a,n:int64;
begin
b:=k-2*i;
a:= b mod i;
n:=1+b div i;
if(b>0) then func(k, i+1, r+(a+b)*n div 2,l) else l:=r;
end;
begin
readln(k);
func(k,1,0,l);
writeln(l);
end.

Поза форумом

 

#4 2015-12-22 12:32:40

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Розбір рішень

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 с.
Чесно кажучи, не розумію таку систему оцінювання sad

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

Поза форумом

 

#5 2015-12-22 13:36:51

PAS99
Новий користувач
Зареєстрований: 2015-12-21
Повідомлень: 3

Re: Розбір рішень

Я розумію, що рішення не ідеальне, але проходячи 80% тестів не більше, ніж за 0,1 с , воно б мало набирати "хоч щось" sad

Поза форумом

 

#6 2015-12-22 14:29:48

FordPerfect
Новий користувач
Зареєстрований: 2014-11-15
Повідомлень: 14

Re: Розбір рішень

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

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;
}

Идея: формула решения http://latex.codecogs.com/png.latex?%5Csum_%7Bi%3D2%7D%5E%7Bn-1%7D%20%5Csum_%7Bk%3D2%7D%5E%7B%5Cleft%20%5Clceil%20%5Cfrac%7Bn%7D%7Bi%7D%20%5Cright%20%5Crceil%7D%20n-%28i%20k-i%29, внутренняя сумма раскрыта для ускорения вычислений. Желающие могут попробовать раскрыть и внешнюю сумму.
Сложность: 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)

Поза форумом

 

#7 2015-12-24 04:24:44

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 308

Re: Розбір рішень

FordPerfect, дякую за надані рішення. Вважаю дуже корисним для зацікавлених учасників ознайомлення з рішеннями саме після закінчення туру, коли умови задач іще "крутяться" в голові.

Поза форумом

 

#8 2015-12-24 06:27:20

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 308

Re: Розбір рішень

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)

Поза форумом

 

#9 2015-12-24 14:22:25

FordPerfect
Новий користувач
Зареєстрований: 2014-11-15
Повідомлень: 14

Re: Розбір рішень

Кстати в строчке

Код:

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

всё-таки нет undefined behavior, а только implementation-defined. Но, всё-равно, лучше, наверное:

Код:

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

Поза форумом

 

#10 2015-12-24 18:22:24

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Розбір рішень

код розвязку задачі 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 с

Поза форумом

 

#11 2016-01-17 06:25:35

FordPerfect
Новий користувач
Зареєстрований: 2014-11-15
Повідомлень: 14

Re: Розбір рішень

Unizero, праздник продолжается:

Код:

#include <iostream>

// sum[i=1;n] floor(n/i)
long long s1(long long n)
{
    long long ret=0;
    long long i=1;
    for(i=1;i*i<=n;++i)
        ret+=2*(n/i);
    --i;
    ret-=i*i;
    return ret;
}

// sum[i=1;n] floor(n/i)*i
 long long s2( long long n)
{
     long long ret=0;
     long long i=1;
    for(i=1;i*i<=n;++i)
    {
        long long a=n/(i+1);
        long long b=n/i;
        ret+=b*i;
        if(i<b) ret+=i*(b*(b+1)-a*(a+1))/2;
    }
    return ret;
}

// sum[i=1;n] floor(n/i)^2*i
long long s3(long long n)
{
    long long ret=0;
    long long i=1;
    for(i=1;i*i<=n;++i)
    {
        long long a=n/(i+1);
        long long b=n/i;
        ret+=b*b*i;
        if(i<b) ret+=i*i*(b*(b+1)-a*(a+1))/2;
    }
    return ret;
}

int main()
{
    long long n;
    std::cin>>n;
    std::cout<<n*s1(n-1)-(s3(n-1)+s2(n-1))/2-n*(n-1)/2;
    return 0;
}

Сложность: O(sqrt(n)) времени, O(1) памяти.
Идея: можно воспользоваться формулой из http://math.stackexchange.com/questions … rogression и обобщить её следующим образом:
http://latex.codecogs.com/png.latex?%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Cleft%20%5Clfloor%20%5Cfrac%7Bn%7D%7Bi%7D%20%5Cright%20%5Crfloor%5Ek%3D%20%5Cleft%28%20%5Csum_%7Bi%3D1%7D%5E%7B%5Clfloor%20%5Csqrt%7Bn%7D%20%5Crfloor%7D%20%5Cleft%20%5Clfloor%20%5Cfrac%7Bn%7D%7Bi%7D%20%5Cright%20%5Crfloor%5Ek%20&amp;plus;%5Cleft%28%20i%5Ek%20-%20%28i-1%29%5Ek%20%5Cright%29%20%5Cleft%20%5Clfloor%20%5Cfrac%7Bn%7D%7Bi%7D%20%5Cright%20%5Crfloor%20%5Cright%29%20-%20%5Clfloor%20%5Csqrt%7Bn%7D%20%5Crfloor%5E%7Bk&amp;plus;1%7D
http://latex.codecogs.com/png.latex?%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Cleft%20%5Clfloor%20%5Cfrac%7Bn%7D%7Bi%7D%20%5Cright%5Crfloor%5Ek%20i%3D%20%5Csum_%7Bi%3D1%7D%5E%7B%5Clfloor%20%5Csqrt%7Bn%7D%20%5Crfloor%7D%20%5Cleft%20%5Clfloor%20%5Cfrac%7Bn%7D%7Bi%7D%20%5Cright%5Crfloor%5Ek%20i&amp;plus;%20%5Csum_%7Bi%3D1%7D%5E%7B%5Cleft%5Clceil%20%5Csqrt%7Bn%7D%20%5Cright%5Crceil-1%7D%20%5Cfrac%7B%20%5Cleft%20%5Clfloor%20%5Cfrac%7Bn%7D%7Bi%7D%20%5Cright%5Crfloor%20%5Cleft%28%20%5Cleft%20%5Clfloor%20%5Cfrac%7Bn%7D%7Bi%7D%20%5Cright%5Crfloor%20&amp;plus;%201%20%5Cright%29%20-%20%5Cleft%20%5Clfloor%20%5Cfrac%7Bn%7D%7Bi&amp;plus;1%7D%20%5Cright%5Crfloor%20%5Cleft%28%20%5Cleft%20%5Clfloor%20%5Cfrac%7Bn%7D%7Bi&amp;plus;1%7D%20%5Cright%5Crfloor%20&amp;plus;%201%20%5Cright%29%20%7D%7B2%7D%20i%5Ek
(правка: исправил формулу)

Версии для ceil легко получить, используя тот факт, что ceil(n/i)=floor((n+i-1)/i)=floor((n-1)/i)+1.
Таким образом, формула из поста #6 может быть выражена через приведённые выше суммы.

Відредаговано FordPerfect (2016-01-17 06:47:10)

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt