Розв'язки приймаються до 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). Програма виводить на пристрій стандартного виведення єдине число – максимальну кількість друзів, яких Василько пригостить «рибним асорті»

Приклади

- - - - - - - - - - - - - - - - - - - - - - - -

Задача Brackets2018. Герой олімпіад Василь Пупкін взяв правильно записаний математичний  вираз з дужками і  викинув з нього все, крім дужок, наприклад:

(()(()())(())())

Потім він під кожною відкриваючою дужкою записує, скільки дужок (будь-яких) знаходиться між нею і відповідній їй закриваючою, а під закриваючими не пише нічого:

Вам дано такий ряд чисел. Відновіть початкову послідовність дужок.

Технічні умови. Програма Brackets2018 читає зі стандартного пристрою введення натуральне число N, не більше 100 и в тому ж рядку  через пропуск N цілих невід’ємних чисел, не більших 200. Програма виводить на пристрій стандартного виведення послідовність дужок, що відповідає початковому ряду чисел. Якщо розв’язку не існує, програма виводить impossible.

Приклади

- - - - - - - - - - - - - - - - - - - - - - - -

Задача Twogifts. Герой олімпіад Василь Пупкін обирає собі подарунки на новий рік. Він знає, що св. Миколай зробить йому рівно два подарунки: один нібито від мами, а інший нібито від тата. У магазині продається n подарунків, про кожен подарунок відома його ціна: ціна i-го подарунка дорівнює a_i гривень. Василь знає, що можливо витратити на покупку  подарунків для ньго не більше x гривень. Зрозуміло, він хоче отримати якомога більше дорогі подарунки. Таким чином, він хоче вибрати два різних подарунка з максимальною сумарною ціною, але при цьому вона не повинна перевищувати x. Допоможіть Василеві вибрати собі подарунки.

Технічні умови. Програма Twogifts читає зі стандартного пристрою вводу два цілих числа: n і x (2 ≤ n ≤  100000, 2 ≤ x ≤ 10⁹). Другий рядок введення містить n цілих чисел: a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹). Гарантується, що існує два подарунки з сумарною ціною не більше x. Програма виводить на пристрій стандартного виведення одне ціле число: максимальну сумарну ціну двох різних подарунків, що не перевищує x.

Приклад

- - - - - - - - - - - - - - - - - - - - - - - -

Задача Presents. Діти в дитячому садку отримали великий мішок з цукерками. Їх у мішку М штук. Вирішено, що цукерки повинні бути розподілені серед N дітей. Кожна дитина вказала кількість цукерок, які вона хоче. Якщо дитині не дістанеться та  кількість цукерок, яку вона хоче, віна буде ображена. «Гнів» буде рівним квадрату кількості бажаних, але не отриманих  цукерок. Наприклад, якщо Василько стверджує, що хоче 32 цукерки, але отримує лише 29, йому не вистачає 3 цукерок, тому його «гнів» буде рівним 9.  Допоможіть розподілити цукерки так, щоб сума дитячого гніву була мінімальною.

Технічні умови. Програма  Presents читає з пристрою стандартного введення в першому рядку два цілих числа  M (1 ≤ M ≤ 2 · 10⁹) і N (1 ≤ N ≤ 100 000), наступні N рядків містять цілі числа (по одній на рядок), які відображають побажання дітей. Ці числа строго менші 2 · 10⁹, і їх сума завжди перевищує М. Програма виводить єдине шукане число – мінімально можливу сумі дитячого «гніву».

Приклади.

- - - - - - - - - - - - - - - - - - - - - - - -

Задача  Dogging.  Василько Пупкін  нещодавно придбав собі песика. На зоологічних форумах він вичитав, що песикам цієї породи необхідно щонайменше K прогулянок за будь-яких два послідовних дні, щоб бути щасливими. До прикладу, якщо K = 7 та Василь погуляв з песиком тричі вчора, то сьогодні йому треба вигуляти його щонайменше чотири рази.  Вася вже відмітив бажану кількість прогулянок (з урахуванням своїх справ) на наступні N днiв, але боїться, що іноді прогулянок буде замало. Тож він просить Вас допомогти йому визначити, яку кількість прогулянок треба зробити додатково, щоб його вірний пес був щасливий.

Технiчнi умови. Програма Dogging читає два натуральних числа N i K (N,K ≤ 10⁵) - кількість днів i кількість необхідних прогулянок. Далі програма читає ще N цілих невід’ємних чисел - кількість запланованих прогулянок на кожний з наступних N днів. Кожне з чисел не перевищує 10⁵. Програма повинна виводити єдине число - мінімальну кількість додаткових прогулянок, які необхідно зробити.

Приклади

-------------------

Завдання підготували Непомнящий Г., Пасіхов Ю., Стречень М.