20 листопада 2016 року відбувся ІІ тур Всеукраїнської учнівської олімпіади з інформатики (програмування).

Перше загальнокомандне місце здобули учні Хоцьківської ЗОШ І-ІІІ ступенів.

Козій Іван - учень 11 класу,
Чухно Катерина - учениця 10 класу,
Янча Тетяна - учениця 9 класу,
Коваленко Валентина - учениця 8 класу.

Задача 1 FELLING (30 балів). Вирішено вирубати деякі із N дерев, що ростуть у ряд, відстані між якими однакові. Після вирубки повинно залишитись M дерев, а відстані між сусідніми повинні також залишитись одинаковими. Написати програму, яка визначає, скільки існує способів вирубки дерев.

Вхідні дані: Файл Fell.dat через пропуск містить два цілих числа M i N (0 ≤ M ≤ N ≤ 1000).

Результат: У файлі Fell.res повинно міститись одне число – шукана кількість способів.

Задача 2 LAWN (30 балів). Газон можна вважати площиною, на якій в кожній точці з цілими координатами росте один пучок трави. Було пострижено деяку прямокутну ділянку газону. Сторони цієї ділянки паралельні осям координат, а дві протилежні вершини розташовано в точках (x1, y1) і (x2, y2). Пучки трави, що знаходяться на межі цього прямокутника, також були пострижені. Дощувальна установка розміщена в точці з координатами (x3, y3) і має радіус дії струменя r. Установка почала поливати усі пучки, відстань від яких до точки (x3, y3) не перевищує r. Написати програму, що визначає кількість пучків трави, які виявилося постриженими і политими.

Вхідні дані: У першому рядку файлу Lawn.dat через пропуск записані чотири цілі числа x1, y1, x2, y2 (-100 000 ≤ x1 < x2 ≤ 100 000; -100 000 ≤ y1 < y2 ≤ 100 000). У другому рядку вхідного файлу містяться три цілі числа x3, y3, r (-100 000 ≤ x3, y3 ≤ 100 000; 1 ≤ r ≤ 100 000).

Результати: У файл Lawn.res необхідно вивести одне ціле число - число пучків трави, які були і пострижені, і политі.

Задача 3 FORT (45 балів). У замку квадратної форми є вісім башень, чотири на стиках стін і по одній посередині кожної стіни. Замок захищає гарнізон із N солдатів (N ≤ 100). Необхідно визначити кількість захисників кожної стіни, розмістивши їх в башнях так, щоб вздовж кожної стіни була однакова кількість по M (M < N) солдатів.

Вхідні дані: У файлі Fort.dat записано через пропуск два числа N та M.

Результати: У файл Fort.res записати всі можливі варіанти розстановки солдатів у башнях, кожен варіант з нового рядка у формі, зображеній на таблиці (зірочки – кількість солдатів у башнях).

Задача 4 CUBES (55 балів). Кубик з ребром N см пофарбували і розрізали на кубики з ребром 1 см При цьому з'явилися такі, у яких забарвлена різна кількість граней. Наприклад, якщо N = 3, то після розрізання буде 8 кубиків, у яких забарвлено три грані, 12 з двома гранями, 6 з однією, а один кубик буде зовсім незабарвлений. Написати програму програму, яка б визначала, скільки кубиків з кожною можливою кількістю забарвлених граней.

Вхідні дані: У файлі Cub.dat записано натуральне число N (від 1 до 100000).

Результати: У файл Cub.dat у рядок через пропуск потрібно записати різні варіанти зафарбувань одержаних після розрізання кубиків у форматі: кількість зафарбованих граней/кількість кубиків у порядку зростання першого параметра (див. приклад).