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

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)