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


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

Ви не зайшли.

#1 2014-02-15 21:17:29

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Разбор задач

1. Lens.
Вы не умеете правильно выбирать неассимптотические оптимизации? Тогда мы идём к вам! Тайм-лимит оказался очень жёстким. В итоге моё ассимптотически оптимальное решение набрало лишь 75/100 баллов, хотя и имело ряд оптимизаций. Но всё же, о задаче. Можно заметить, что ответом является количество натуральных делителей числа F*F. Действительно,
F=fd/(f+d)
Ff+Fd=fd
d=Ff/(f-F)

Обратим внимание, что мы не рассматриваем мнимые изображения, поэтому можно утверждать, что f=F+k. Тогда:
d=F*(F+k)/k
d=F*F/k+F

Понятно, что второе слагаемое не повлияет на то, будет ли d в итоге целым. Поэтому, нам надо найти все k, которые делят F нацело. Для этого нам следует за sqrt(F) факторизовать число F и из этой факторизации получить факторизацию F*F, а из неё - количество делителей числа.

И да, только в этой задаче я обнаружил, что, оказывается, N операций умножения выполняются быстрее, чем ОДНА операция извлечения корня. Это, конечно, для меня преприятнейшая новость, стоившая около 15 баллов.
Наилучшая ассимптотика: O(sqrtn)
Код:

Код:

   

    int F;
    cin>>F;
    int cur=0;
        if(!(F&1))
        cur++;
        while(!(F&1))
        arr[cur]++,F>>=1;
    for(int i=3;i*i<=F;i+=2)
    {
        if(!(F%i))
        cur++;
        while(!(F%i))
        arr[cur]++,F/=i;
    }
    if(F!=1)
    arr[++cur]++;
    int ans=1;
    for(int i=0;i<=cur;i++)
    ans*=(arr[i]<<1)+1;
    cout<<ans;

2. Sweets.

Рисунок дерева является очень значительной подсказкой к решению. Легко заметить, что мы можем решать задачу, так сказать, с конца. Выстроим первое поколение дерева (оно состоит из одного элемента - 1), после этого каждое следующее будем добывать, сдвигая предыдущие числа влево и ставя после них те, которые ещё не включены в наше дерево.
          1
         1 2
      1 3 2 4
1 5 3 6 2 7 4 8

И так далее. Это легко сделать симулируя дерево массивом на 2*N элементов.
Итоговая ассимптотика: O(N)

4. MaxDivs3.
Легко заметить, что N^3-N=N(N-1)(N+1). С помощью линейного решета Эратосфена факторизуем все числа в пределах [1..B+1] и после этого будем искать ответ, перебирая для каждой искомой тройки делители её произведения. Так как у каждого числа в среднем O(lnx) делителей, а троек нам надо перебрать O(n), получаем ассимптотику O(nlogn).

К сожалению, моё решение использует контейнер map для хранения факторизации числа, что значительно замедляет его и делает ассимптотику O(n*logn*logn). Однако, по всей видимости, можно улучшить решение до O(nlogn).
Итоговая ассимптотика: O(nlogn).

5. Girls.
Для тех, кто достаточно хорошо знаком с олимпиадным программированием не составит труда узнать, что девочки играют в игру "Ним", а размеры в кучках зашифрованы в виде числа. Восстановим эти размеры, возьмём от них остаток по модулю r+1, а затем найдём их общий xor. К сожалению, здесь я также допустил очень досадную ошибку, т.к. я сначала проксорил, а потом от итога взял остаток. Ну что сказать, сам себе злой буратино.
Итоговая ассимптотика: O(t*logMAXN).
Код:

Код:

    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
     int n,m,k;
     cin>>n>>m>>k;
     int arr[101]={0};   
     int cur=0;
     while(n)
     arr[cur++]=n%m,n/=m;
     int xr=0;
     for(int i=0;i<cur;i++)
     xr^=arr[i]%(k+1);
     cout<<(xr?1:2)<<"\n";

Відредаговано adamant (2014-02-15 21:46:25)

Поза форумом

 

#2 2014-02-15 21:28:20

OArtem3
Новий користувач
Звідки: Харьков
Зареєстрований: 2011-10-27
Повідомлень: 6

Re: Разбор задач

Вот мои конфетки:

Код:

#include <iostream>

using namespace std;

int a[300000];

int main()
{
   int n;
   cin >> n;

   int last = 0;
   for (int step = 2; step < n; step *= 2)
      for (int i = step / 2 - 1; i < n; i += step)
         a[i] = ++last;
   a[n/2-1] = ++last;
   a[n-1] = ++last;

   for (int i = 0; i < n; ++i)
      cout << a[i] << " ";

   return 0;
}

Может кто-то подсказать, что тут может быть не так? 15 балов получил. На онлайн проверке WA и один RE.

Поза форумом

 

#3 2014-02-15 21:29:16

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Задачу divide я попытался решать жадно, но решение набрало только 55/100. Причины мне неизвестны. Скажу точнее, когда появится архив олимпиады.

Основная идея моего решения:
Если в какой-то паре будет самый худший с точки зрения Кати фильм, то он гарантированно уйдёт к нам. Логично при этом поставить ему в пару самый худший для Димы фильм из оставшихся, чтобы потерять как можно меньше. Реализовать такой проход можно, например, с помощью C++ STL контейнера set или собственной структуры упорядоченного множества (им может быть бинарное сбалансированное дерево или, например, ленивое дерево отрезков).

Ассимптотика: O(nlogn).

Відредаговано adamant (2014-02-15 21:46:10)

Поза форумом

 

#4 2014-02-15 21:33:16

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

OArtem3 написав:

Вот мои конфетки:

Код:

#include <iostream>

using namespace std;

int a[300000];

int main()
{
   int n;
   cin >> n;

   int last = 0;
   for (int step = 2; step < n; step *= 2)
      for (int i = step / 2 - 1; i < n; i += step)
         a[i] = ++last;
   a[n/2-1] = ++last;
   a[n-1] = ++last;

   for (int i = 0; i < n; ++i)
      cout << a[i] << " ";

   return 0;
}

Может кто-то подсказать, что тут может быть не так? 15 балов получил. На онлайн проверке WA и один RE.

Не вникал в суть решения, но уже на ввод 8 он даёт неправильный ответ.

1 5 2 7 3 6 4 8
На следующий день останутся:
1 2 3 4
На последующий день
1 3, хотя должны остаться 1 2.

Поза форумом

 

#5 2014-02-15 21:41:18

OArtem3
Новий користувач
Звідки: Харьков
Зареєстрований: 2011-10-27
Повідомлень: 6

Re: Разбор задач

Точно sad
Обидно.

Поза форумом

 

#6 2014-02-18 10:52:26

fedorovoleksandr
Новий користувач
Зареєстрований: 2012-02-13
Повідомлень: 2

Re: Разбор задач

1. Lens.
@adamant (к сожалению) у меня не прошло Ваше решение на 100% из-за тайм-лимита системы; насчет неассимптотических оптимизаций - у меня получилось создать решения, работающие на последнем тесте соответственно за 2.29, 1.30, 1.01, 0.85, 0.77, 0.73 секунды и весящие соответственно 197, 214, 305, 891, 7309, 89231 байт. Идея оптимизации проста: представляем перебираемые делители в виде n*j+r, где j>=1, n - произведение первых нескольких простых чисел, и НЕ перебираем те из них, для которых r делится на одно из этих простых чисел (если делится на какое-то простое число, то, поскольку n также делится на это же число, n*j+r есть составным); также заранее перебираем все простые числа, меньшие n.

Генератор решений:

Код:

#include<iostream>

// Первые несколько простых чисел
const int A[] = {2,3,5,7,11,13};

int I1=1;
template<typename T,size_t N>inline size_t SizeOfArray(const T(&)[N])
{return N;}

using namespace std;

int main(){
    for (int j=0;j<SizeOfArray(A);++j)I1*=A[j];
    freopen("Lens.cpp","w",stdout);
    cout<<"#include<iostream>"<<endl;
    cout<<"long long n,r=1,i="<<I1<<",t;"<<endl;
    cout<<"void f(long long i){"<<endl;
        cout<<"\tt=r+r;"<<endl;
        cout<<"\twhile(!(n%i))n/=i,r+=t;"<<endl<<"}"<<endl;
    cout<<"int main(){"<<endl;
        cout<<"\tstd::cin>>n;"<<endl;
        cout<<"\t";
        for (int i=2;i<=I1;++i)
        {
            bool g = true;
            for (int j=2;j*j<=i;++j)
                if (!(i%j)){g=false;break;}
            if (g)
                cout<<"f("<<i<<");";
        }
        cout<<endl;
        cout<<"\twhile(i*i<=n)";
        for (int i=0;i<I1;++i)
        {
            bool g = true;
            for (int j=0;j<SizeOfArray(A);++j)
                if ((i+I1)%A[j]==0)g=false;
            if (g)
                cout<<"f(i+"<<i<<"),";
        }
        cout<<"i+="<<I1<<";"<<endl;
        cout<<"\tstd::cout<<(n-1?r*3:r);"<<endl;
    cout<<"}"<<endl;
}

Поза форумом

 

#7 2015-11-12 20:34:55

Gleb Piliets
Новий користувач
Зареєстрований: 2015-11-12
Повідомлень: 2

Re: Разбор задач

Вот мой код, проходит на 0
Так вроде все правильно


#include<iostream>
#include <assert.h>
#include<cmath>
#include<vector>
using namespace std;

double power(double a, int n) {
    assert(n > 0 || (a != 0.0 || n != 0));
    switch (n) {
    case 0:
        return 1;
    case 1:
        return a;
    default: {
        double a2 = power(a, n / 2);
        if (n & 1) {
             return a * a2 * a2;
        }
        else {
             return a2 * a2;
        }
    }
    }
}

int main()
{
    int n;
    cin >> n;
    int wer = power(2,17);
    int ch[wer];
    vector<int> v;
    int tek[n],pr[n];
    for(int i = 0; i < n; i ++) ch[i] = i + 1;
    pr[0] = 1;
    pr[1] = 2;
    int i = 0,q = 0,l = 2;
    while(l != n)
    {

        for(int j = l; j < 2*l; j ++)
        {
            tek[i] = pr[q];
            i ++; q ++;
            tek[i] = ch[j];
            i ++;
            if(l == n /2)
            {
                v.push_back(tek[i-2]);
                v.push_back(tek[i-1]);
            }
        }
        for(int t = 0; t < i; t ++)
        {
            pr[t] = tek[t];
            tek[t] = 0;
        }
        l *= 2;
        i = 0,q = 0;
    }
    for(int i = 0; i < v.size(); i ++) cout << v[i] << " ";
    return 0;
}





Посмотрите кто-то если кому интересно

Відредаговано Gleb Piliets (2015-11-12 20:37:51)

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt