1. Завдання III туру NetOI-2016 (27.12.2016-27.01.2017)

З прийдешнім Новим Роком!

Завдання приймаються до 0 годин 28 січня 2017 року

Задача Bell. У півсферичний дзвін, краї якого щільно прилягають до горизонтальної поверхні столу, наливають рідину через отвір згори. Коли рідина доходить до деякого рівня h, вона підіймає дзвін та починає з-під нього витікати. Знайдіть цей рівень води, якщо маса дзвона дорівнює m, його внутрішній радіус - R, густина рідини - .

Технічні умови: Програма Bell читає з пристрою стандартного введення дійсні числа m, R та  через пропуск (виміряні в кг, м і кг / м³ відповідно) та виводить на пристрій стандартного виведення єдине число – шукану величину. Відповідь не повинна відрізнятися від правильної більше, ніж на =10^-6. Якщо дзвін не спливе, виведіть -1.

Обмеження: 0.01 <= m <= 10¹⁰, 0.1 <= R <=100, 100.0 <= <=15000.

Приклад:

Задача Cookies.  Бабуся пекла печиво. Для цього вона розкачала тісто в великий пласт у формі кола та стаканчиками різних діаметрів повидавлювала в ньому круглі шматочки, щоб потім запекти їх та отримати з них смачне печиво. Відомо, що ніякі два круглих вирізи не перетинаються між собою, крім того, всі вирізи повністю знаходяться всередині пласта тіста. Однак вирізи можуть торкатися один одного та країв тіста. Улюблений онук з корисливих міркувань вирішив допомогти бабусі: він вирішив вирізати з решти пласта круглу заготовку для печива якомога більшого розміру. Однак він не знає, який діаметр повинен бути в стаканчика, яким потрібно вирізати таку заготовку. Допоможіть йому.

Технічні умови. Напишіть програму Cookies, яка читає з пристрою стандартного введення дійсне число R  - радіус пласта тіста. Вважається, що центр пласта знаходиться в початку координат - в точці з координатами (0,0). Другий рядок містить число N - кількість вже вирізаних заготовок. Наступні рядків містять по 3 дійсних числа x_k, y_k, r_k - координати центра та радіус чергового вирізу (k = 1, 2,..., N). Програма виводить на пристрій стандартного виведення єдиний рядок - шуканий радіус максимальної за розміром заготовки, яку ще можна вирізати з пласта тіста. Відповідь не повинна відрізнятися від правильного більше за =10^-3.

Обмеження:  0.0 < R <=1000.0, 1 <= N <= 100.

Приклад: дивись малюнок

Задача Spruce.

Фермер Іван Петрович купив ділянку, що складається з m квадратних грядок з півдня на північ і з n грядок із заходу на схід. Він хоче посадити на ділянці ялинки, які, коли вони виростуть, він вигідно реалізує під Новий Рік. Однак ялинки можна садити лише за такими правилами:

1. На кожній грядці може рости не більше трьох ялин.
2. Не можна залишати грядки порожніми.
3. На кожному квадраті, утвореному чотирма сусідніми грядками, має рости рівно вісім ялин.

Допоможіть фермеру порахувати, скількома способами він може посадити ялинки на своїй ділянці.

Технічні умови: Програма Spruce читає з пристрою стандартного введення через пропуск числа m, n (2<=m, n<=30) і виводить на пристрій стандартного виведення шукану кількість способів.

Приклади

Введення 2 2
Виведення 19
Введення 2 3
Виведення 45

Задача Hopper.  Дослідники, які вивчають інтелект комах, провели наступний експеримент. Довгу стрічку розбили на N клітинок однакового розміру та на першу клітку посадили коника-стрибунця. Мета коника - дістатися останньої клітинки стрічки. Частина клітин стрічки зафарбовані в червоний колір, якого коник боїться - на такі клітини він ставати не може. Відомо, що перша й остання клітини стрічки ніколи не зафарбовуються в червоний колір.  Коник рухається по стрічці стрибками. Він може стрибати тільки з клітини в клітину. Коник може стрибати по стрічці як вперед, так і назад.

Спершу коник може перестрибнути тільки на сусідню клітку. Це стрибок довжини 1. Після кожного стрибка коник вибирає напрямок наступного стрибка (вперед або назад), а також може збільшити довжину стрибка на одну клітку, зменшити довжину стрибка на одну клітку або залишити довжину стрибка незмінною. Коник не може стрибати на червоні клітини або вистрибувати за межі стрічки.

Визначте, чи зможе коник дістатися останньої клітини стрічки, і, якщо зможе, то яку найменшу кількість стрибків йому доведеться для цього зробити.

Технічні умови. Напишіть програму Hopper, яка читає з пристрою стандартного введення число N - кількість клітинок в стрічці. Другий рядок введення містить послідовність з нулів і одиниць, розділених пропусками, яка показує, як розфарбована стрічка. При цьому 0 означає звичайну клітину, а 1 - зафарбовану в червоний колір. Програма виводить на пристрій стандартного виведення одне число - найменшу кількість стрибків, що виконає коник, щоб досягти останньої клітини стрічки, або число -1 - якщо це неможливо.

Обмеження: 1 < N <= 1000.

Приклад:

Задача Virus2016.

Є великий квадрат з довжиною сторони 2n+1, розбитий на клітини 1х1. У початковий момент часу (t = 0) в центрі квадрата (клітинка з координатами (0, 0)) оселився шкідливий вірус. Через секунду він, розпадаючись, заражає чотири сусідніх клітини з координатами (-1, -1), (-1, 1), (1, -1), (1, 1). Ще через секунду все чотири розпадаються так само, як і перший, заражаючи сусідів, але якщо в одній клітці може з'явитися не один, а кілька вірусів, то вони взаємно знищуються. Далі зазначені дії повторюються. Процес розмноження вірусу припиняється, якщо віруси з'явилися в клітинах, які прилягають до сторін квадрата. Визначити, скільки клітин з вірусом буде у великому квадраті в цей момент.

Технічні умови. Програма Virus2016 читає з пристрою стандартного введення ціле число  n (0<n<200). Програма виводить на пристрій стандартного виведення шукану кількість заражених клітин.

Приклад  (див. рисунок)

Завдання підготували Й.Ентін, Г.Непомнящий, Ю.Пасіхов