Перший тур
Кумедний конфуз
Нехай A — масив, що складається з N елементів A1,...,AN. Позначимо його максимальне і мінімальне значення як max(A) і min(A) відповідно. Обчислимо суму елементів S, S=A1+A2+…+AN. Замінимо кожний елемент масиву на різницю S та цього елемента: Ai:=S-Ai, 1<=i<=N. Таке перетворення масиву A назвемо операцією Confuse.
Завдання
Напишіть програму CONFUSE, що за масивом B, отриманим у результаті K–кратного застосування операції Confuse до деякого масиву A, обчислює різницю: max(A)-min(A).
Вхідні дані
Перший рядок вхідного файлу CONFUSE.DAT містить цілі числа N і K, де N — кількість елементів масиву B (2<=N<=10000), а K — кількість застосувань операції Confuse до початкового масиву A, 1<=K<=100. Другий рядок файлу містить N елементів масиву B. Елементи масиву B — цілі числа, що належать діапазону від -2 000 000 000 до 2 000 000 000.
Вихідні дані
Єдиний рядок вихідного файлу CONFUSE.SOL повинен містити ціле число, яке є різницею max(A) та min(A).
Приклад вхідних та вихідних даних
|
CONFUSE.DAT |
CONFUSE.SOL |
|
4 2 |
7 |
Змагання
В спортивному турнірі приймає участь N чоловік, з номерами від 1 до N. Турнір проходить за круговою системою: кожен учасник має зіграти з кожним іншим учасником по одній партії, яка закінчується перемогою одного з гравців. Вважається, що по закінченню турніра учасник займає місце P, якщо:
1) у нього виграли (P-1) учасників, та йому програли всі інших;
2) усі учасники, що перемогли його, виграли свої партії у всіх учасників, що йому програли.
Для інших учасників підсумкове місце визначити не можна.
Завдання
Напишіть програму CONTEST, що отримує на вхід число N та результати зіграних на даний момент партій турніра, та визначає кількість учасників, для яких по закінченні турніра не можна буде визначити підсумкове місце, незалежно від результатів тих партій, які ще будуть зіграні.
Вхідні дані
В першому рядку вхідного файлу CONTEST.DAT задаються два натуральних числа: N — кількість учасників турніру (1<=N<=100) та M — кількість зіграних партій. Наступні M рядків описують зіграні партії. В рядку задаються два числа: номер переможця та номер учасника, що програв.
Вихідні дані
В єдиному рядку вихідного файлу CONTEST.SOL повинно бути ціле число — шукана кількість учасників.
Приклад вхідних та вихідних даних
|
CONTEST.DAT |
CONTEST.SOL |
|
6 8 |
4 |
Абракадабра
|
Під час своєї роботи алгоритм стискання даних методом «сортування блоку» застосовує до блоків даних перетворення, яке визначається наступним чином.
Рядок P називається ротацією рядка S, якщо він утворений циклічним зсувом символів S, тобто якщо S=a1a2…aN, де ai — i–ий символ рядка S, то P=apap+1…aNa1…ap-1, де 1<=p<=N. Розглянемо таблицю M розміру N´N, рядками якої є всі ротації рядка S, відсортовані у лексикографічному (словниковому) порядку за зростанням.
Нехай рядок L є останнім стовпчиком таблиці M. Пряме перетворення отримує на вхід рядок S, видає рядок L та число K — номер рядка таблиці M, що містить рядок S. (Якщо таких рядків декілька, видається номер будь–якого з них).
Для S='abraka' таблицю M зображено на малюнку. Рядок S знаходиться у другому рядку таблиці M, L=‘karaab’.
Завдання
Напишіть програму ABRAKA, що виконує зворотнє перетворення, тобто отримує на вхід рядок L і число K, та видає рядок S.
Вхідні дані
Перший рядок вхідного файлу ABRAKA.DAT містить два цілих числа: K та N, 1<=N<=30000, 1<=K<=N. Другий рядок містить N символів рядка L — маленьких латинських літер.
Вихідні дані
Єдиний рядок вихідного файлу ABRAKA.SOL повинен містити рядок S.
Приклад вхідних та вихідних даних
|
ABRAKA.DAT |
ABRAKA.SOL |
|
2 6 |
abraka |
Циферблат
На циферблаті записана послідовність чисел у двійковій системі числення. Циферблат може бути розбитий на сектори. Лінії розбиття можуть проходити як між числами, так і між цифрами одного числа, розбиваючи його на два чи більше чисел. Для кожного сектора можна порахувати суму чисел, які в ньому розташовані.
Кожне число в послідовності не дорівнює 0, та його запис почитається з одиниці. Кількість цифр в двійковому запису числа не перевищує 25. Загальна кількість цифр на циферблаті не більша за 100.
На малюнку зображено звичний нам циферблат з числами від 1 до 12 (в дещо незвичному вигляді). Його розбито на 4 сектори. Суми для секторів будуть 1, 15, 18 та 36.
Завдання
Напишіть програму DIAL, що за заданою послідовністю визначає кількість різних розбиттів циферблату на сектори, такі що сума чисел у всіх секторах однакова.
Вхідні дані
В єдиному рядку вхідного файлу DIAL.DAT задана послідовність чисел. Числа послідовності розділені пропуском.
Вихідні дані
В єдиному рядку вихідного файлу DIAL.SOL повинно знаходитися натуральне число — кількість шуканих розбиттів циферблату на сектори.
Приклад вхідних та вихідних даних
|
DIAL.DAT |
DIAL.SOL |
|
101 1 1101 |
9 |
Другий тур
Кубики
Тривимірна фігура складається з одиничних кубиків. За фігурою можна побудувати її фронтальну та праву проекції. Очевидно, що за цими двома проекціями не завжди можна відтворити фігуру.
Завдання
Напишіть програму CUBES, що отримує на вхід фронтальну та праву проекції фігури та визначає мінімальну та максимальну кількість кубиків, яку можна було б використати для побудови фігури із заданими проекціями.
Вхідні дані
В першому рядку вхідного файлу CUBES.DAT знаходиться три числа N, M та К, що задають розміри проекцій (1≤N, M, K≤100). Далі задаються дві проекції: спочатку фронтальна, а потім права. Проекція задається N рядками, кожний з яких складається з чисел 0 та 1, що розділені пропуском. Для фронтальної проекції таких чисел буде M, а для правої — K. 0 означає вільну клітину проекції, 1 — заповнену.
Вихідні дані
В єдиному рядку вихідного файлу CUBES.SOL повинно знаходитися два числа: мінімальна та максимальна кількість кубиків, які можна було б використати для побудови фігури із заданими проекціями.
Приклад вхідних та вихідних даних
|
CUBES.DAT |
CUBES.SOL |
|
2 2 3 |
4 7 |
Багатокутники
На площині задана така множина з N багатокутників, що виконуються наступні умови:
1) ніякі два багатокутника не мають спільних точок;
2) для кожного i–го багатокутника існує Pi багатокутників, всередині яких він знаходиться, і N-1-Pi багатокутників, котрі знаходяться всередині нього, 0<=Pi<=N-1.
Завдання
Напишіть програму POLYGON, яка для кожного багатокутника видає кількість багатокутників, всередині яких він знаходиться.
Вхідні дані
Перший рядок вхідного файлу POLYGON.DAT містить ціле число N — кількість багатокутників, 3<=N<=10000. Наступні N рядків файлу описують N багатокутників. (i+1)–ий рядок файлу описує i–ий багатокутник. Перше ціле число Ci — кількість вершин багатокутника, 3<=Ci<=20. Наступні Ci пар чисел — координати вершин багатокутника у порядку його обходу. Координати вершин — цілі числа, що належать діапазону від -2 000 000 000 до 2 000 000 000.
Вихідні дані
Єдиний рядок вихідного файлу POLYGON.SOL повинен містити N чисел: i–те число рядка повинно бути Pi — кількість багатокутників, всередині яких знаходиться i–ий багатокутник.
Приклад вхідних та вихідних даних
|
POLYGON.DAT |
POLYGON.SOL |
|
3 |
0 2 1 |
Шляхи
Прямокутне поле складається з N рядків та M стовбчиків. Гральна фішка за один хід може пересунутися з клітини одного стовбчика на одну з клітин наступного стовбчика. Для кожної клітини поля відомі номери рядків клітин наступного стовбчика на які фішка може зробити хід. Фішка не може піти на клітину, яку вона вже відвідувала раніше.
На початку гри фішку встановлюють на довільну клітину першого стовбчика. Після цього фішка починає рухатися в бік останнього стовбчика. Коли фішка досягає останнього стовбчика, її знову встановлюють на будь–яку клітину першого стовбчика, що не була відвідана раніше, та поновлюють її рух.
Гра завершується коли фішка не може зробити хід.
Завдання
Напишіть програму WAYS, що за числами N, M (1≤N≤50, 2≤M≤10), та таблицею переходів між клітинами визначає яку найбільшу кількість разів можна провести фішку від першого до останнього стовбчика грального поля.
Вхідні дані
В першому рядку вхідного файлу WAYS.DAT знаходяться числа N та M. Далі слідує M-1 блок по N рядків в кожному — визначення можливих переходів для кожної клітини поля. Кожний i–ий рядок j–го блоку описує можливі переходи з клітини в i–му рядку та j–му стовбчику грального поля. Перше число в рядку задає кількість можливих переходів з клітини, після чого слідують номери рядків наступного стовбчика за зростанням та без повторень.
Вихідні дані
В єдиному рядку вихідного файлу WAYS.SOL повинно знаходитися ціле число, що дорівнює шуканій кількості шляхів. (Відповідь може бути 0, якщо з жодної клітини першого стовбчика не можна досягнути жодної клітини останнього). Для наведеного прикладу вхідних даних фішку можна провести 3 рази, наприклад, за такими маршрутами: (1-->3-->3), (2-->4-->4) та (4-->2-->2).
Приклад вхідних та вихідних даних
|
WAYS.DAT |
WAYS.SOL |
|
4 3 |
3 |
|
© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"