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

Полнобальные решения:
Fishing:

#include <cstdio>
#include <algorithm>

int main()
{
    int M,N,K;
    std::scanf("%d%d%d",&M,&N,&K);
    std::printf("%d",std::min(std::min(M/2,N),(M+N-K)/3));
    return 0;
}

Brackets2018:

#include <cstdio>

char buf[1000000];
int id=0;
int N;

int go(int n)
{
    while(n>0&&N>0)
    {
        int k;
        std::scanf("%d",&k);
        --N;
        buf[id++]='(';
        if(go(k)) return -1;
        buf[id++]=')';
        n-=k+2;
    }
    return n;
}

int main()
{
    std::scanf("%d",&N);
    std::printf("%s",go(1000000)<0?"impossible":buf);
    return 0;
}

Twogifts:

#include <cstdio>
#include <algorithm>

int a[1000000];

int main()
{
    int n,x;
    std::scanf("%d%d",&n,&x);
    for(int i=0;i<n;++i) std::scanf("%d",&(a[i]));
    std::sort(a,a+n);
    int ret=0;
    int l=0,r=n-1;
    while(l<r)
    {
        int c=a[l]+a[r];
        if(c>x) --r;
        else {if(c>ret) ret=c; ++l;}
    }
    std::printf("%d",ret);
    return 0;
}

Полнобальное решение Presents может выглядеть, например, так (это не тот код, который я посылал на тур):

#include <cstdio>
#include <algorithm>

typedef unsigned long long ui64;
typedef __uint128_t ui128;

int a[1000000];

int main()
{
    int M,N;
    std::scanf("%d%d",&M,&N);
    for(int i=1;i<=N;++i)
        std::scanf("%d",&(a[i]));
    std::sort(a+1,a+N+1);
    ui64 S=0;
    int i=N;
    for(;i>=1;--i)
    {
        S+=a[i];
        if(S-a[i-1]*ui64(N-i+1)>M) break;
    }
    M-=S-a[i]*ui64(N-i+1);
    int A=M/(N-i+1);
    int B=M%(N-i+1);
    for(int j=N;j>=i;--j)
        a[j]=a[i]-A-(N-j<B);
    ui128 X=0;
    for(i=1;i<=N;++i)
    {
        X+=ui64(a[i])*ui64(a[i]);
    }
    if(X>1000000000000000000ULL)
        std::printf("%llu%018llu",ui64(X/1000000000000000000ULL),ui64(X%1000000000000000000ULL));
    else std::printf("%llu",ui64(X));

    return 0;
}

Вместо нестандартного __uint128_t можно честно написать длинку:

#include <cstdio>
#include <algorithm>

typedef unsigned long long ui64;

int a[1000000];

void printlong(ui64 X0,ui64 X1)
{
    if(X1>0ULL||X0>=10ULL)
        printlong((X0+((X1%10ULL)<<56))/10ULL,X1/10ULL);
    std::printf("%d",int((X0+6*X1)%10ULL));
}

int main()
{
    int M,N;
    std::scanf("%d%d",&M,&N);
    for(int i=1;i<=N;++i)
        std::scanf("%d",&(a[i]));
    std::sort(a+1,a+N+1);
    ui64 S=0;
    int i=N;
    for(;i>=1;--i)
    {
        S+=a[i];
        if(S-a[i-1]*ui64(N-i+1)>M) break;
    }
    M-=S-a[i]*ui64(N-i+1);
    int A=M/(N-i+1);
    int B=M%(N-i+1);
    for(int j=N;j>=i;--j)
        a[j]=a[i]-A-(N-j<B);
    ui64 X0=0ULL,X1=0ULL;
    for(i=1;i<=N;++i)
    {
        X0+=ui64(a[i])*ui64(a[i]);
        X1+=X0>>56;
        X0&=(1ULL<<56)-1ULL;
    }
    printlong(X0,X1);
    return 0;
}

Dogging:

#include <cstdio>
#include <algorithm>

int main()
{
    int N,K;
    int ret=0;
    std::scanf("%d%d",&N,&K);
    int c=K,b;
    for(int i=0;i<N;++i)
    {
        b=c;
        std::scanf("%d",&c);
        int d=std::max(K-b-c,0);
        ret+=d;
        c+=d;
    }
    std::printf("%d",ret);
    return 0;
}

Примечание: здесь используется интерпретация, при которой для N=1 ответ гарантированно 0.

Відредаговано FordPerfect (2018-11-21 12:37:12)

Помогите с решением Задача Presents напишите блок схему или просто объясните алгоритм выше по этой задаче.
Пишу на паскале.

Не понятно только  for(;i>=1;--i)
    {
        S+=a[i];
        if(S-a[i-1]*ui64(N-i+1)>M) break;
    }
    M-=S-a[i]*ui64(N-i+1);
    int A=M/(N-i+1);
    int B=M%(N-i+1);
    for(int j=N;j>=i;--j)
        a[j]=a[i]-A-(N-j<B);

в задаче Presents
только её не сделал на максимальный бал другим алгоритмом а этот не понял, жаль
можете объяснить по другому, а то я что-то тугодумлю)
начал изучать с++ не понял что такое ui64(n-i+1)
кому не лень напишите. очень прошу.

Відредаговано Pasha2208 (2018-11-28 20:06:12)

Presents. Попробую изложить происхождение алгоритма по-другому. Итак, конфеток на всех не хватит, а значит есть некий дефицит deficit, который нужно предоставить в виде суммы недовыданных конфеток deficit=a0+a1+...+an так, чтобы сумма квадратов a0^2+a1^2+...+an^2 оказалась минимальной. Согласно неравенству между средним квадратическим и средним арифметическим, сумма квадратов чисел с данной суммой минимальна когда все числа равны.
Но тут сразу возникают две проблемы. Первая это то, что дефицит может не делиться нацело на число детей, что ещё можно обойти, недодавая части детей k=[deficit/n] конфет, а deficit-kn детям k+1 конфету. Вторая проблема хуже, некоторым детям может хотеться получить в подарок менее k конфет, а мы, к сожалению, не можем выдавать ребенку отрицательное их число. Тогда выясняется, что если такой невзыскательный ребенок есть, то лучше всего ему не дать вообще ни одной конфеты, а потом свести задачу к n-1 детям. Если среди них опять есть кто-то невзыскательный, то опять не выдаём ему ни одной конфеты. Ну и так далее, пока все не будут хотеть получить в подарок не менее, чем [current_deficit/current_n] конфет (в названиях переменных появилось слово current в смысле "текущее", потому что при откидывании кинутых на конфеты детей оставшийся дефицит и число оставшихся детей меняется).

@Pasha2208
Т. к. ограничения достаточно небольшие, то мы можем использовать рекурсивное решение, не боясь переполнения стека.
Функция go(n) пытается прочитать (и "поглотить" в терминах парсеров) из ввода описание правильного скобочного выражения длины n (и в качестве побочного эффекта добавляет это скобочное выражение в buf), реализуя это в терминах рекурсивных вызовов go(). Если ей это не удалось, функция возвращает ненулевое значение; это может получиться в 3-х случаях:
1. Ввод закончился, а у нас план по скобкам недовыполнен. Пример: 2 10 0 (выражение имеет вид (() ???) где вместо ??? должно быть ещё 8 скобок).
2. Мы прочитали больше скобок, чем n (т. е. n закончилось посередине выражения). Пример: 4 2 4 0 0 (здесь 4 0 0 описывает (()()), что 6 скобок, а не заявленные 2).
3. Ошибка возникла на одном из вложенных уровней рекурсии.

Очевидно, что "содержимое скобок, помеченных значением n" - это как раз "правильное скобочное выражение длины n"; откуда понятно, как собственно реализовывать go() в терминах самой себя - прочитав k из ввода, запускаем go(k), и так, пока не исчерпаем n.

Чуть-чуть схитрив, получаем решение исходной задачи за один вызов go() - мысленно окружив всё выражение "виртуальными скобками" заведомо слишком большого размера. Хитрость в том, что теперь функция возвращает положительное значение для п. 1 (который теперь - для "виртуальных скобок", настоящий размер которых мы не знаем - означает правильное скобочное выражение) и отрицательное - для пп. 2 и 3 (которые всё-ещё означают ошибку).