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

Коль скоро отправка уже заблокирована, а проверять решения уже можно, впору писать разбор задач. Ну, приступим.

1. Total.
Элементарная задача на знание базовых алгоритмов, по всей видимости. Можно заметить, что всегда выгодно взять в выигрышные карточки n/2 самых дорогих. Это можно сделать просто отсортировав массив. После этого просто суммируем первые n/2 элементов и отнимаем то, что мы проиграем - сумму оставшихся карточек, которые будут проигрышными. Наиболее быстрые алгоритмы сортировки отработают здесь за O(nlogn), но в принципе, судя по ограничениям, здесь должна пройти и сортировка за O(n^2).
Наилучшая ассимптотика: O(nlogn).
Код на С++:

    int n;
    cin>>n;
    int*a=new int[n];
    
    for(int i=0;i<n;i++)
    cin>>a[i];
    
    sort(a,a+n);
    
    int ans=0;
    
    for(int i=0;i<n;i++)
    if(i<n/2)
    ans-=a[i];
    else
    ans+=a[i];
    
    cout<<ans<<endl;

2. Msum.
Так как заранее известно, как будет ходить каждый игрок, просто промоделируем эту игру. Если в конце у нас кто-то из игроков набрал больше очков, чем другой, то он выиграл. Иначе ничья.
Наилучшая ассимптотика: O(n).
Код:

    int n;
    cin>>n;
    long long a=0,b=0,t; // a - очки первого игрока, b - очки второго, t - переменная, хранящая число на входе
    
    for(int i=2;i<=n+1;i++)
    {cin>>t;
    if(i%2)
    b+=t*i;
    else
    a+=t*i;}
    
    long long c,d; // с - номер выигравшего игрока, d - его очки
    if(a>b)
    c=1,d=a;
    else if(a<b)
    c=2,d=b;
    else
    c=-1,d=a;
    
    cout<<c<<' '<<d<<endl;

3. Mcode.
Даже не знаю, что и сказать по этому поводу. Ограничения времени по задаче неприятно удивили. Ну да ладно, опишу своё решение, может, кто-нибудь потом выложет более оптимальное.

Итак, будем перебирать высоту самого оптимального прямоугольника. Вместе с тем для каждой высоты будем перебирать соответствующую ей ширину. При этом в таких пределах, чтобы всегда выполнялось h*w<=n. Легко заметить, что операций у нас будет выполнено примерно n/1+n/2+n/3+...+n/n=n(1+1/2+1/3+...+1/n). Легко заметить, что в скобках у нас находится гармонический ряд. В 1740 году Леонард Эйлер получил ассимптотическое выражение, позволяющее охарактеризовать эту сумму как O(lnn). Таким образом итоговая ассимптотика выходит O(nlogn). Обычно на задачах с ограничениями n<=1e6 этого вполне хватает, но... Это NetOI. И несмотря на то, что такое решение успевало выполниться на макс. тесте с лимитом проверки Online (50 мс), теперь оно на двух последних тестах даёт TLE и в итоге проходит лишь на оценку 18/20...
UPDATE: можно добиться прохождения всех тестов, если высоту перебирать не от единицы, а от большого числа, хотя это в целом неассимптотическая оптимизация.
Наилучшая ассимптотика: O(nlogn).
Код:

    int n;
    cin>>n;
    int ans=1e9;
    int root=sqrt(n);
    for(int i=max(1,root-30);i<=root;i++)
    for(int j=1;j*i<=n;j++)
    if(n-i*j+abs(i-j)<ans)
    ans=n-i*j+abs(i-j);
    cout<<ans<<endl;

4. Cub.
Симулируем контест. Можно перебирать каждую секунду и проверять, изменился ли во время неё баланс сил, а можно поступить более хитро и как бы использовать checkpoint'ы. Когда какая-нибудь команда сдаёт задачу, мы вначале проверяем, лидировала ли какая-то команда перед сдачей и если да, то начисляем ей очки за время, прошедшее с предыдущей сдачи кем-либо задачи. После этого инкрементируем счётчик сданных задач у этой команды. И, наконец, в конце надо ещё начислить очки той команде, которая лидировала к моменту времени 2880 секунд.
Наилучшая ассимптотика: О(n).
Код:

    int n;
    cin>>n;
    int a=0,b=0,c=0,d=0; // a - кол-во сданных задач у первой команды, b - у второй, c,d - очки первой и второй команд соответственно.
    
    int w,m,s,ps=0; // ps - предыдущий момент сдачи кем-либо задачи в секундах. 
    
    for(int i=0;i<n;i++)
    {
     cin>>w>>m>>s;
    
     s+=m*60;
    
     if(a>b)   
     c+=s-ps;
     if(b>a)
     d+=s-ps;
     
     if(w-1)
     b++;
     else
     a++;
     
     ps=s;
    }
    
    s=2880;
    
     if(a>b)   
     c+=s-ps;
     if(b>a)
     d+=s-ps;
    
    cout<<c<<' '<<d<<endl;

5. Cell.
Очень интересная задача. Очень жаль, что в отличие от mcode авторы не стали требовать константной ассимптотики и ограничились линейной при n=1e6. Решение для этой задачи за О(n) в целом интуитивно понятно и я не буду на нём останавливаться. Рассмотрим решение за O(1). Для начала обратим внимание, что нам удобнее рассматривать здесь нумерацию начиная с нуля, а не с единицы.
                                                           

Теперь отметим некоторые значимые клетки - углы.

                                                           

Для удобства пронумеруем их.
                                                           

Теперь обратим внимание на то, как получаются числа в углах. Пускай K(n) - число в каком-то углу.
K(1)=1;
K(2)=1+1;
K(3)=1+1+2;
K(4)=1+1+2+2;
K(5)=1+1+2+2+3;
Легко заметить, что такой вид сумм в углах позволяет нам обобщить эту функцию таким образом:
K(2n)=n(n+1)=n*n+n;
K(2n-1)=n(n+1)-n=n*n;

Как мы видим, принципиальная разница получилась в том, чётный наш угол или же нет. Покрасим все чётные углы в один цвет, а нечётные в другой.
                                                           

Что мы можем заметить далее - чётные и нечётные углы внутри себя отличаются тем, в какую сторону мы будем из них двигаться. Так, из нечётных (зелёных) углов мы можем двигаться либо вверх, либо вних, а из чётных - либо влево, либо вправо. Так как эти параметры чередуются, мы можем утверждать, что то, в какую сторону идёт движение от угла зависит лишь от того, чему равен остаток от деления его номера на 4. Добавим же ещё два цвета в нашу таблицу.
                                                           

Наконец, мы можем заметить, что для любой точки мы можем быстро определить её координаты, если знаем координаты угла, который был до неё. Чтобы было проще понять, для каких клеток какие углы мы должны найти, покрасим каждую клетку в цвет соответствующего ей угла.
                                                           

Наконец, мы определили для клетки номер соответствующего ей угла. Теперь нам остаётся лишь записать соответствующие формулы для ответа для четырёх случаев - для каждого из цветов.
                                                                                   
Numb - номер ближайшего угла, dist - расстояние до него. Деление целочисленное, с округлением в меньшую сторону.

Наилучшая ассимптотика: О(1).
Код:

    int k;
    cin>>k;
    
    k--;
    
    int n=sqrt(k);
    
    int sum=n*n;
    
    int numb=2*n-1; // Номер ближайшего угла, в котором находится значение вида n*n
    
    if(n*n+n<=k) // Искомый угол может быть либо numb, либо numb+1, проверяем это
    numb++,sum+=n;
    
    int x,y;
    
    int dist=k-sum;
    
    if(numb%4==1)
    x=1+numb/4,y=dist-numb/4;
    else if(numb%4==2)
    x=1+numb/4-dist,y=1+numb/4;
    else if(numb%4==3)
    x=-(1+numb/4),y=1+numb/4-dist;
    else
    x=-numb/4+dist,y=-numb/4;
    
    cout<<x<<' '<<y<<endl;

Відредаговано adamant (2013-11-16 12:04:26)