Написання програм CONFUSE, CONTEST і ABRAKA (Завдання першого туру XV Всеукраїнської олiмпiади з iнформатики)

учасники, що перемогли його, виграли свої партії у всіх учасників, що йому програли.

Для інших учасників підсумкове місце визначити не можна.

Завдання

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

Вхідні дані

В першому рядку вхідного файлу CONTEST.DAT задаються два натуральних числа: N — кількість учасників турніру (1£N£100) та M — кількість зіграних партій. Наступні M рядків описують зіграні партії. В рядку задаються два числа: номер переможця та номер учасника, що програв.

Вихідні дані

В єдиному рядку вихідного файлу CONTEST.SOL повинно бути ціле число — шукана
кількість учасників.

Приклад вхідних та вихідних даних

CONTEST.DAT	CONTEST.SOL
6 8 1 5 1 4 5 2 5 6 3 2 2 6 6 4 4 3	4

Абракадабра

Під час своєї роботи алгоритм стискання даних методом «сортування блоку» застосовує до блоків даних перетворення, яке визначається наступним чином.

Рядок P називається ротацією рядка S, якщо він утворений циклічним зсувом символів S, тобто якщо S=a₁a₂…a_N, де a_i — i–ий символ рядка S, то P=a_pa_p+1…a_Na₁…a_p-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 karaab	abraka

Циферблат

На циферблаті записана послідовність чисел у двійковій системі числення. Циферблат може бути розбитий на сектори. Лінії розбиття можуть проходити як між числами, так і між цифрами одного числа, розбиваючи його на два чи більше чисел. Для кожного сектора можна порахувати суму чисел, які в ньому розташовані.

Кожне число в послідовності не дорівнює 0, та його запис почитається з одиниці. Кількість цифр в двійковому запису числа не перевищує 25. Загальна кількість цифр на циферблаті не
більша за 100.

На малюнку зображено звичний нам циферблат з числами від 1 до 12 (в дещо незвичному вигляді). Його розбито на 4 сектори. Суми для секторів будуть 1, 15, 18 та 36.

Завдання

Напишіть програму DIAL, що за заданою послідовністю визначає кількість різних розбиттів циферблату на сектори, такі що сума чисел у всіх секторах однакова.

Вхідні дані

В єдиному рядку вхідного файлу DIAL.DAT задана послідовність чисел. Числа послідовності розділені пропуском.

Вихідні дані

В єдиному рядку вихідного файлу DIAL.SOL повинно знаходитися натуральне число — кількість шуканих розбиттів циферблату на сектори.

Приклад вхідних та вихідних даних

DIAL.DAT	DIAL.SOL
101 1 1101	9

XV Всеукраїнська олімпіада з інформатики

Другий тур

Кубики

Тривимірна фігура складається з одиничних кубиків. За фігурою можна побудувати її фронтальну та праву проекції. Очевидно, що за цими двома проекціями не завжди можна відтворити фігуру.

Завдання

Напишіть програму 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 1 0 1 1 0 0 1 1 1 1	4 7

Багатокутники

На площині задана така множина з N багатокутників, що виконуються наступні умови:

1)  ніякі два багатокутника не мають спільних точок;

2)  для кожного i–го багатокутника існує P_i багатокутників, всередині яких він знаходиться, і
N-1-P_i багатокутників, котрі знаходяться всередині нього, 0£P_i£N-1.

Завдання

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

Вхідні дані

Перший рядок вхідного файлу POLYGON.DAT містить ціле число N — кількість багатокутників, 3£N£10000. Наступні N рядків файлу описують N багатокутників. (i+1)–ий рядок файлу описує i–ий багатокутник. Перше ціле число C_i — кількість вершин багатокутника, 3£C_i£20. Наступні C_i пар чисел — координати вершин багатокутника у порядку його обходу. Координати вершин — цілі числа, що належать діапазону від -2 000 000 000 до 2 000 000 000.

Вихідні дані

Єдиний рядок вихідного файлу POLYGON.SOL повинен містити N чисел: i–те число рядка повинно бути P_i — кількість багатокутників, всередині яких знаходиться