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


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

Ви не зайшли.

#1 2018-11-21 04:59:02

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

РОЗВ'ЯЗКИ

Традиционно архивы всех решений можно будет увидеть только по завершении 4-го тура NetOi. Но, как говорится: "Дорога ложка к обеду". Поэтому предлагаю здесь делиться своими решениями, которые набрали максимум баллов.


Вік живи - вік навчайся.

Поза форумом

 

#2 2018-11-21 05:03:55

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

Re: РОЗВ'ЯЗКИ

Код:

// Fishing
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int M, N, K;
    cin >> M >> N >> K;

int ok = M / 2;//сколько друзей могут получить окуней
int mbm = (ok < N ? ok : N ); //максимальное количество друзей, если не учитывать Мурку 
    
    //находим остаток рыбы, который можно отдать Мурке без ущерба для друзей
    int o = M + N - mbm * 3; 

    if (K > o)//если Мурке нужно больше рыбы, чем осталось
    {
int nr = K - o, //сколько нужно рыбы отнять от друзей для Мурки
pd = ceil(nr / 3.0);    //сколько пострадает друзей при этом 
mbm = mbm - pd;//сколько друзей с рыбой останется
    }
    cout << mbm;
    return 0;
}

Код:

// Twogifts
#include <iostream>
#include <algorithm>
using namespace std;
int compare(const void * a, const void * b)
{
    return (*(int*)a - *(int*)b);
}
int main()
{
    int n, x;
    cin >> n >> x;
    int *a = new int[n];
    long long *min = new long long[n / 2];

    for (int i = 0; i<n; i++)
        cin >> a[i];

    qsort(a, n, sizeof(int), compare);

    long long sum;
    int k = 0;
    for (int i = 0, j = n - 1; i != j; )
    {
        sum = a[i] + a[j];
        if (sum > x) j--;
        else if (sum < x)
        {
            min[k] = sum;
            k++;
            i++;
        }
    else
    {
        cout << sum;
        return 0;
    }

    }

    long long max = min[0];
    for (int i = 0; i < k; i++)
        if (min[i] > max)
            max = min[i];

    cout << max;
    return 0;
}

Код:

// Dogging
#include <iostream>
using namespace std;
int main()
{
int N, K, PrPred, PrNew, PrDop;
cin >> N >> K;
    long long sum = 0;

    cin >> PrPred; //это прогулки за предыдущий день
    for (int i = 1; i < N; i++)
    {
        PrDop = 0;
        cin >> PrNew; //прогулки за новый (следующий) день
        if (PrPred + PrNew < K)
        {
            PrDop = K - PrPred - PrNew; //сколько нужно сделать дополнительных прогулок
            sum = sum + PrDop;
        }
        PrPred = PrNew + PrDop;
    }
    cout << sum;
    return 0;
}

Відредаговано LVV (2018-11-21 09:48:38)


Вік живи - вік навчайся.

Поза форумом

 

#3 2018-11-21 12:35:18

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

Re: РОЗВ'ЯЗКИ

Полнобальные решения:
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)

Поза форумом

 

#4 2018-11-24 14:58:25

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 25

Re: РОЗВ'ЯЗКИ

Twogifts.
Начал тоже с сортировки. А дальше подумал, что O(n^2) для n<10^5 это слишком для питона. В задаче по сути нужно уметь находить самое большое число не больше произвольного x, что в отсортированном массиве можно сделать за log(n) бинарным поиском.

Код:

n,x = map(int,raw_input().split())
a = map(int,raw_input().split())
a.sort()
max_price=0

for i in xrange(n-1):
    goal = x-a[i]
    lb = i+1#lower bound
    ub = n-1#upper bound
    if a[ub] < goal:
        max_price = max(a[i]+a[ub],max_price)
        continue
    if a[ub] == goal:
        max_price = x
        break
    if a[lb] > goal:
        break        
    while (ub-lb):
        middle = (lb+ub+1)/2
        if a[middle] > goal:
            ub = middle-1
        if a[middle] == goal:
            max_price = x
            break
        if a[middle] < goal:
            lb = middle
    else:
        max_price = max(max_price,a[i]+a[lb])
        continue
    break
print max_price

Поза форумом

 

#5 2018-11-24 20:20:36

Pasha2208
Олімпієць
Зареєстрований: 2018-11-24
Повідомлень: 18

Re: РОЗВ'ЯЗКИ

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

Поза форумом

 

#6 2018-11-26 13:08:36

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

Re: РОЗВ'ЯЗКИ

@Pasha2208

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

Влобная реализация данного алгоритма работает за O(M*N), что тормозит. Но результат можно получить быстрее.
Отсортируем детей по количеству желаемых конфет.
Наш алгоритм минимизирует максимум, поэтому мы, по сути, отсекаем верхний треугольник на получившемся графике - настолько большой, на сколько хватит М. На "чистое" отсечение М может не хватить, поэтому на "плато" останется хвостик.

Код:

5 5 1 2 3 4 5

    #
   ##
  ###
 ####
#####

    #
   ##
----+
 ####
#####

    #
 ####
#####

1^2+2^2+2^2+2^2+3^2=22

Дальнейший алгоритм сводится к нахождению максимального треугольника (на самом деле, скорее трапеции), на который хватит M, размера хвостика, и подсчёту ответа.

Задача несколько осложняется (для C/Pascal) необходимостью использования длинной арифметики, т. к. ответ (и промежуточные вычисления) может не помещаться в uint64.

Это, собственно, и приводит к коду из #3.

Відредаговано FordPerfect (2018-11-26 13:11:06)

Поза форумом

 

#7 2018-11-28 20:02:36

Pasha2208
Олімпієць
Зареєстрований: 2018-11-24
Повідомлень: 18

Re: РОЗВ'ЯЗКИ

Не понятно только  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)

Поза форумом

 

#8 2018-11-29 14:08:51

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

Re: РОЗВ'ЯЗКИ

Это расчёт максимальной трапеции, на которую хватит M.

По окончании цикла:
• S - это сумма в диапазоне [i;N] (индексы считаются с единицы),
• условие S-a[i-1]*ui64(N-i+1)>M выполнено (именно по нему мы вышли из цикла),
• величина S-a[i-1]*ui64(N-i+1) - это площадь "трапеции" (с основанием [i;N] и линией отсечения по a[i-1]),
• величина S-a[i]*ui64(N-i+1) - это площадь "треугольника" (с основанием [i;N] и линией отсечения по a[i]),
• соответственно, M лежит между этими двумя величинами, и i - это начало максимального "плато", для которого ещё хватит M.
Дальше мы вычитаем из M "треугольник".
После этого:
A - это количество строчек, которые мы можем убрать из "плато" целиком,
B - это длина строчки, которую мы из "плато" можем убрать частично ("хвостик").
Ну и дальнейший цикл как раз и проводит это вычитание.

ui64(N-i+1) - это приведение выражения N-i+1 к типу ui64 (т. е. unsigned long long). Без этого выражение a[i]*(N-i+1) будет вычислено в int32 и может переполниться.

Поза форумом

 

#9 2018-11-30 22:36:28

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 25

Re: РОЗВ'ЯЗКИ

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 в смысле "текущее", потому что при откидывании кинутых на конфеты детей оставшийся дефицит и число оставшихся детей меняется).

Поза форумом

 

#10 2018-12-04 20:04:21

Pasha2208
Олімпієць
Зареєстрований: 2018-11-24
Повідомлень: 18

Re: РОЗВ'ЯЗКИ

Можете объяснить алгоритм по задаче Brackets2018 приведённый выше, я делал другим алгоритмом, но он был раз в 7 больше, но работал правильно и тоже 20 баллов.

Поза форумом

 

#11 2018-12-09 23:14:07

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

Re: РОЗВ'ЯЗКИ

@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 (которые всё-ещё означают ошибку).

Поза форумом

 

#12 2018-12-10 16:37:49

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

Re: РОЗВ'ЯЗКИ

По здравом размышлении - мы знаем ожидаемое количество скобок во входном выражении, поэтому можно без всяких хитростей go(2*N).

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt