Решения принимаются до 0 часов 17 ноября 2018 г.
====================================================================================
Задача Fishing. Герой олимпиад Вася Пупкин наловил рыбы и принес домой М окуней и N карасей. Он решил угостить друзей, подарив каждому из них по 2 окунька и одному карасю. К тому же его кошка Мурка тоже должна получить К рыб (Мурке безразлично каких). Какое максимальное количество друзей Василий сможет угостить? Например, если M = 6, N = 3, а K = 2, Василий сможет угостить 2-х друзей, Мурка получит одного окуня и одного карасика, а один окунь (повезло!) останется Васе.
Технические условия. Программа Fishing читает з устройства стандартного ввода в одной строке через пробелы целые числа M (0 ≤ M ≤ 100), N (0 ≤ N ≤ 100), K (0 ≤ K ≤ M+N). Программа выводит на устройство стандартного вывода единственное число – максимальное количество друзей, которых Вася угостит «рыбным ассорти».
Примеры
|
Ввод |
Вывод |
|
6 3 2 |
2 |
|
2 1 1 |
0 |
|
6 10 3 |
3 |
- - - - - - - - - - - - - - - - - - - - - - - -
Задача Brackets2018. Герой олимпиад Василий Пупкин взял правильно записанное математическое выражение со скобками и выбросил из него всё, кроме скобок, например:
(()(()())(())())
Затем он под каждой открывающейся скобкой записывает, сколько скобок (любых) находится между ней и соответствующей ей закрывающейся, а под закрывающимися не пишет ничего:
|
( |
( |
) |
( |
( |
) |
( |
) |
) |
( |
( |
) |
) |
( |
) |
) |
|
14 |
0 |
|
4 |
0 |
|
0 |
|
|
2 |
0 |
|
|
0 |
|
|
Вам дан такой ряд чисел. Восстановите первоначальную последовательность скобок.
Технические условия. Программа Brackets2018 читает с устройства стандартного ввода натуральное число N, не большее 100, и в той же строке через пробел N целых неотрицательных чисел, не больших 200. Программа выводит на устройство стандартного вывода последовательность скобок, которая соответствует начальному ряду чисел. Если ответа не существует, программа выводит impossible.
Примеры
|
Ввод |
Вывод |
|
8 14 0 4 0 0 2 0 0 |
(()(()())(())()) |
|
2 1 1 |
impossible |
- - - - - - - - - - - - - - - - - - - - - - - -
Задача Twogifts. Герой олимпиад Василий Пупкин выбирает себе подарки на Новый год. Он знает, что св. Николай сделает ему ровно два подарка: один якобы от мамы, а другой якобы от папы. В магазине продается n подарков, известна цена каждого подарка: цена i-го подарка равна ai гривен. Василий знает, что на покупку подарков для него возможно потратить не более x гривен. Разумеется, он хочет получить как можно больше дорогие подарки. Таким образом, он хочет выбрать два разных подарка по максимальной суммарной цене, но при этом она не должна превышать x. Помогите Василию выбрать себе подарки.
Технические условия. Программа Twogifts читает с устройства стандартного ввода в первой строке два целых числа через пробел: n и x (2 ≤ n ≤ 100000, 2 ≤ x ≤ 109). Вторая строка содержит n целых чисел: a1, a2, ..., an (1 ≤ ai ≤ 109). Гарантируется, что существует два подарка по суммарной цене не более x. Программа выводит на устройство стандартного вывода одно целое число: максимальную суммарную цену двух различных подарков, не превышающую x.
Пример
| Ввод | Вывод |
| 6 18 | 15 |
| 5 3 10 2 4 9 |
- - - - - - - - - - - - - - - - - - - - - - - -
Задача Presents. Дети в детском саду получили большой мешок с конфетами. Их в мешке М штук. Решено, что конфеты должны быть распределены среди N детей. Каждый ребенок указал количество конфет, которое он хочет. Если ребенку не достанется такого количество конфет, которое он хочет, он будет обижен. «Гнев» будет равным квадрату количества желаемых, но не полученных конфет. Например, если Вася утверждает, что хочет 32 конфеты, но получает лишь 29, ему не хватает 3 конфет, поэтому его «гнев» будет равным 9. Помогите распределить конфеты так, чтобы сумма детского гнева была минимальной.
Технические условия. Программа Presents читает с устройства стандартного ввода в первой строке два целых числа M (1 ≤ M ≤ 2 · 109) і N (1 ≤ N ≤ 100 000), следующие N строк содержат целые числа (по одному в строке), которые отображают пожелания детей. Эти числа строго меньше 2·109, а их сумма всегда больше М. Программа выводит единственное искомое число - минимально возможную сумму детского «гнева».
Примеры
|
Ввод |
Вывод |
|
5 3 1 3 2 |
1 |
| Ввод | Вывод |
|
10 4 4 5 2 3 |
4 |
- - - - - - - - - - - - - - - - - - - - - - - -
Задача Dogging. Вася Пупкин недавно приобрел себе собаку. На зоологических форумах он вычитал, что собачкам этой породы необходимо не менее K прогулок в любые два последовательных дня, чтобы быть счастливыми. К примеру, если K = 7 и Вася погулял с собакой трижды вчера, то сегодня ему надо выгулять его по меньшей мере четыре раза. Вася уже нашел желаемое количество прогулок (с учетом своих дел) на следующие N дней, но боится, что иногда прогулок будет мало. Поэтому он просит Вас помочь ему определить, какое количество прогулок надо сделать дополнительно, чтобы его верный пес был счастлив.
Технические условия. Программа Dogging читает с устройства стандартного ввода два натуральных числа N и K (N,K ≤ 105) – количество дней и количество необходимых прогулок. Далее с той же строки программа читает еще N целых неотрицательных чисел - количество запланированных прогулок на каждый из следующих N дней. Каждое из чисел не превышает 105. Программа должна выводить единственное число - минимальное количество дополнительных прогулок, которые необходимо сделать.
Примеры
|
Ввод |
Вывод |
|
4 5 2 2 1 3 |
2 |
|
4 1 0 0 0 0 |
2 |
----------------
Задания подготовили Непомнящий Г., Пасихов Ю., Стречень М.