Фермери - герої задачі Garden отримали в спільне володіння сад прямокутної форми розміром M*N (M<=N), розділений стежками на однакові квадратні ділянки з довжиною сторони 1. Вирішили вони, що вирощувати будуть яблуні і груші, та ніяк не могли дійти згоди , де які дерева садити. У Інтернеті вони прочитали, що краще всього фруктові дерева плодоносять, якщо на кожній ділянці садити по одному дереву, а в кожному квадраті М*M посадити рівно K яблунь. Допоможіть фермерам підрахувати кількість способів посадки дерев в саду.
Технічні умови. Програма NewGarden читає з клавіатури через пропуски цілі числа N, M і К (2<=M<=5, M<=N<=100, 0<=K<=M2). Програма виводить на екран шукану кількість способів.
Приклад
Введення
6 3 1
Виведення
27
Задача Navy
Військово-морський флот деякої держави складається з N кораблів, кожний з яких має свої технічні характеристики. Зокрема, максимальна швидкість, яку може розвивати i-ий корабель,дорівнює деякому додатному числу vi км/г. Розвідка доповіла про те, що сусідня держава планує напасти і знищити якісь кораблі. У зв'язку з цим головнокомандуючий військово-морських сил адмірал Грицько Отаманенко віддав наказ в найкоротший термін зібрати всі кораблі разом (в одній точці) і підготуватися до оборони. Визначіть найменший час, який буде потрібен для того, щоб виконати наказ адмірала, якщо спочатку кораблі знаходилися в точках з координатами ( xi , yi ). Поверхня в даній державі вважається плоскою, кораблі – матеріальними точками, які можуть миттєво змінювати величину швидкості і напрям руху.
Технічні умови. Програма Navy читає з клавіатури кількість кораблів N (2<=N<=100) , і потім для кожного корабля по 3 дійсних числа xi , yi , vi (що не перевищують по модулю 1000 і що мають не більше 2 знаків після коми). Програма виводить на екран мінімальний час для збору кораблів в одній точці з точністю до 0.001.
Приклади
Введення
3 0.0 0.0 1.0 2.0 0.0 2.0 1.0 2.0 3.0
Виведення
0.667
Введення
4 0.0 1.1 1.0 1.1 0.0 1.0 -1.1 0.0 1.0 0.0 -1.1 1.0
Виведення
1.100
Задача Logo
Відомий учасникам олімпіади оператор Kife:( оголосив конкурс на новий логотип компанії. Герой олімпіад Вася Пупкін поставив за мету виграти цей конкурс. Для цього він намалював дуже креативний логотип: спочатку накреслив квадратну сітку NхN комірок, потім намалював на цій сітці K відрізків з кінцями в центрах комірок. Потім він вирішив зафарбовувати всі комірки сітки, які перетинає хоча б один відрізок. Ось тут-то виникла проблема: Вася не знає, скільки фарби йому знадобиться. Допоможіть Васі! Напишіть програму, яка порахує кількість клітинок, які треба зафарбовувати.Технічні умови. Програма Logo читає з клавіатури числа N і K (1<=N<=1000, 0<=K<=1000), а потім K груп по 4 цілих числа - координати комірок-кінців відрізків (1<=Xi1,Yi1,Xi2,Yi2<=N). Програма виводить на екран шукане число комірок, які треба зафарбовувати.
Приклад
Введення 10 3 3 7 4 2 2 4 5 5 2 6 6 8
Виведення 15
Задача Sightseeing
Серпень 2008 року. Каїр. Міжнародна олімпіада з інформатики. Ознайомлення учасників олімпіади з містом було вирішено провести за такою схемою: спочатку учасники K хвилин оглядають місто самі, потім прямують до точки збору на централізовану екскурсію. Район Каїра, в якому перебувають учасники олімпіади, є прямокутною сіткою вулиць NхM. Координати перехрестя задаються парою чисел (i, j). Північно-західне перехрестя району має координати (1,1), північно-східне – (1,M), південно-західне – (N,1) і південно-східне – (N,M). Огляд пам'яток проходить таким чином: опинившись на перехресті, команда або прямує на одне з 4 сусідніх перехресть, або зупиняється, протягом 5 хвилин милується краєвидами міста, а потім повторює вибір. Відстань між перехрестями така, що дорога від перехрестя до сусіднього з ним перехрестя також займає 5 хвилин. Для проведення централізованої екскурсії організатори вирішили призначити точкою збору перехрестя, в якому, як очікується, через K хвилин з початку екскурсії опиниться максимальна кількість команд. Знаючи місто, організатори для кожного перехрестя визначили ймовірність, що команда з нього піде на північ, на захід, на південь, на схід або залишиться на місці. Виходячи з цих даних, необхідно визначити оптимальну точку збору команд. У момент часу 0 всі команди починають огляд міста з перехрестя (R,C). Відомо, що команди не залишають меж району.
Технічні умови: Програма Sightseeing читає з клавіатури 5 чисел N, M, K, R і C (1<=N, M<=100, 0<=K<=500, K кратно 5, 1<=R<=N, 1<=C<=M), потім 5*N*M чисел –імовірності в описаній вище послідовності для перехресть в порядку (1,1)...(1,M) (2,1)...(2,M)... (N,1)..(N,M). Імовірністі - цілі числа від 0 до 100, задані у відсотках. Сума ймовірностей для кожного перехрестя дорівнює 100. Програма виводить 3 числа, розділені пропусками, - координати шуканої точки збору і відсоток команд, який, як очікується, опиниться на цьому перехресті у момент K з точністю не менше 5 знаків після коми або в експоненційній формі, не округлюючи.
Приклад
Введення: 3 3 5 2 2 0 0 0 0 100 0 0 0 0 100 0 0 0 0 100 0 0 0 0 100 70 10 10 5 5 0 0 0 0 100 0 0 0 0 100 0 0 0 0 100 0 0 0 0 100
Виведення 1 2 70.0000000000
Задача Patrol
У місті Глупові міліцейські машини здійснюють патрулювання уздовж деякого маршруту, який має форму замкненої ламаної (можливо, з самоперетинами та самонакладаннями). Усі патрульні машини рухаються без зупинок, з однаковими постійними швидкостями та в одному напрямку. Інтервали часу між проходженнями різних машин через одну й ту саму точку маршруту теж усі однакові. Водночас, виміряні по прямій відстані між деякими парами машин час від часу виявляються досить малими (але не настільки, щоб сталося зіткнення). Знайдіть, коли саме дві машини виявляються найближчими одна до одної.Технічні умови. Програма PATROL має прочитати з клавіатури спочатку кількість патрульних машин M, (2<=M<=1000) потім їх швидкість V (1<=V<=20), потім кількість вершин N (3<=N<=1000) у ламаній, що задає маршрут, потім N пар цілих чисел, що не більші за модулем 106 — координати цих вершин. У момент часу 0 одна з машин проїздить через першу вершину ламаної. Програма має вивести на екран момент часу, коли дві машини виявилися найближчими одна до одної (перший після моменту часу 0) та знайдену мінімальну відстань. Числа слід вивести на екран в один рядок, через пропуск, з точністю 3 знаки після коми, або в експоненційній формі, не округлюючи.
Приклад
Введення
4 5 8 0 0 0 6 2 6 4 4 6 6 8 6 8 0 4 1
Виведення
6.7053214991285295Е-0001 3.0000000000000000E+0000
Д.Нейтер, В.Неспірний, Г.Непомнящий, Ю.Пасіхов, І.Порубльов