Підготовка до олімпіад

Друзі Степана

Time limit:	100 ms
Memory limit:	128 M

Степан повернувся з міжнародної олімпіади школярів з програмування (ІОІ) і привіз з собою N різнокольорових каменів в якості сувенірів. Степан зовсім не жадібний хлопчик, тому вирішив поділитися камінням зі своїми друзями. Кожному другу Степан віддав рівно один камінь. Виявилося, що у самого Степана залишився теж тільки один камінь. Визначте, скільки ж у нього друзів?

Вхідні дані: У першому рядку задано число N (1 ≤ N ≤ 100).

Вихідні дані: Виведіть одне число - кількість друзів Степана.

Пояснення до прикладу: Степан привіз 2 каменя, один з яких залишився у нього. Отже, другий камінь Степан віддав своєму єдиному другу.

Приклад

Введення	Виведення
2	1

Факультатив з інформатики

Time limit:	100 ms
Memory limit:	128 M

Степан вирішив додатково позайматись програмуванням і записався на факультатив з інформатики. Він записав у щоденник час початку заняття (години, хвилини і секунди) та час закінчення (години, хвилини і секунди). Тепер його цікавить скільки годин, хвилин і секунд він буде задіяний на факультативі?

Формат вхідних даних: У першому рядку записані три цілих числа A, B, C (0 ≤ A ≤ 23, 0 ≤ B ≤ 59, 0 ≤ C ≤ 59) - час початку заняття в годинах, хвилинах і секундах.
У другому рядку записані три цілих числа G, H, S (0 ≤ G ≤ 23, 0 ≤ H ≤ 59, 0 ≤ S ≤ 59) - час закінчення заняття в годинах, хвилинах і секундах. 

Формат вихідних даних: Три цілих числа - тривалість заняття в годинах, хвилинах і секундах.

Приклад

Введення	Виведення
12 30 10 13 50 15	1 20 5

Улюблена гра

Time limit:	1000 ms
Memory limit:	128 M

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

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

Гарантується, що улюблена гра єдина.

Вхідні дані: У першому рядку міститься натуральне число N (1 ≤ N ≤ 1000) - кількість записів у щоденнику Степана. У кожному з наступних N рядків містяться записи із щоденника Степана - пара чисел X_i, Y_i, які показують, що Степан провів за грою X_i рівно Y_i хвилин (1 ≤ X_i, Y_i ≤ 1000).

Вихідні дані: Виведіть одне число - номер улюбленої гри Степана.

Приклад

Введення	Виведення
3 1 10 2 20 1 5	2
4 1 10 3 31 1 20 2 25	3

Гра із сірниками

Time limit:	1000 ms
Memory limit:	128 M

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

Вхідні дані: У першому рядку задано натуральне числоN (2 ≤ N ≤ 2 000 000).

Вихідні дані: Виведіть два числа: найбільше і найменше натуральні числа, які може викласти Степан, витративши рівно N сірників на кожне з чисел.

Приклад

Введення	Виведення
5	71 2

Плагіат

Time limit:	1000 ms
Memory limit:	128 M

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

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

Більш точно, журі вирішило не порівнювати такі пари файлів, де менший файл становить менше ніж 90% від розміру більшого файлу. Нарешті, порівняльна програма має перевірити лише такі пари різних файлів(f[i], f[j]), де i ≠ j, size(f[i])≤size(f[j]) та size(f[i])≥ 0.9*size(f[j]).

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

Вхідні дані: Перший рядок містить ціле число N, кількість розв'язків, що були відправлені. Наступний рядок містить N чисел size(f[1]),.., size(f[N]), що означають розміри кожного з файлів.

Вихідні дані: Виведіть кількість пар, що потрібно окремо перевірити.

Обмеження:

1 ≤ N ≤ 100000, 1 ≤ size(f[i]) ≤ 1000000000 

Рішення, що працюють при 1 ≤ N ≤ 2000, будуть оцінюватися з 50 балів. 

Приклад

Введення	Виведення
2 2 1	0
5 1 1 1 1 1	10

Скарби та вікінги

Time limit:	1 s
Memory limit:	128 M

У Вас є карта скарбів, що являє собою сітку розміром N x M. Клітинка сітки може бути як частиною моря, так і суші. До того ж на карті вказані місце знаходження скарбів та корабля ворожих вікінгів, що займає одну клітинку моря. Також, для зручності Ви нанесли на карту своє місцезнаходження.

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

- Якщо Ви на одній лінії з кораблем вікінгів (Ви на одній вертикальній чи горизонтальній лінії, а між вами та вікінгами лише море), то Ви мертві.

- Якщо Ви не мертві та дісталися до скарбів, то вони Ваші.

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

Вхідні дані: Перший рядок містить два цілих числа N та M - розміри карти. Кожен з наступних N рядків містить по M символів. Кожен символ описує клітинку карти, це може бути .(море), I(суша), V(корабель вікінгів), Y(Ваша позиція) або T(скарби). Символи V, Y та T з'являться в точності один раз.

Вихідні дані: Єдиний рядок має містити YES, або NO, в залежності від того, чи можливо скласти безпечний маршрут. 

Обмеження:

1 ≤ N, M ≤ 700 

Система оцінювання:

В даній задачі 9 блоків, кожен блок оцінюється окремо. Бали нараховуються тільки за умови проходження усіх тестів блоку.

Перший блок - тести з умови - оцінюється в 0 балів. 

Другий блок - 1 ≤ N, M ≤ 63 - оцінюється в 12 балів. 

Третій блок - 1 ≤ N, M ≤ 122 - оцінюється в 12 балів. 

Четвертий блок - 1 ≤ N, M ≤ 180 - оцінюється в 12 балів. 

П'ятий блок - 1 ≤ N, M ≤ 200 - оцінюється в 12 балів. 

Шостий блок - 1 ≤ N, M ≤ 700 - оцінюється в 13 балів. 

Сьомий блок - 1 ≤ N, M ≤ 700 - оцінюється в 13 балів. 

Восьмий блок - 1 ≤ N, M ≤ 700 - оцінюється в 13 балів. 

Дев'ятий блок - 1 ≤ N, M ≤ 700 - оцінюється в 13 балів. 

Приклади

Введення	Виведення
5 7 Y.....V ..I.... ..IIIII ....... ...T...	YES
5 7 Y....V. ..I.... ..IIIII ....... ...T...	NO
2 3 .YT VII	NO