1. Кулі (автор — Данило Мисак)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: bullets.in
Вихідний файл: bullets.out
Програма: bullets.*

У скрині лежать кулі n кольорів: c₁ куль першого кольору, c₂ куль другого, …, c_n куль n-го кольору.

Завдання
Знайти найменшу кількість куль, які необхідно наосліп витягти зі скрині, щоб серед них напевне опинилися принаймні d₁ куль першого кольору, принаймні d₂ куль другого, …, хоча б d_n куль n-го кольору.

Вхідні дані
Перший рядок вхідного файла містить одне натуральне число n — кількість кольорів, якими пофарбовано кулі.
У другому рядку файла перераховано n натуральних чисел: c₁, c₂, …, c_n.
У третьому рядку файла перелічено n невід’ємних цілих чисел: d₁, d₂, …, d_n.
Для довільного натурального j при 1 ≤ j ≤ n справджується нерівність: d_j ≤ c_j.
Вхідний файл не містить чисел, що перевищують 1000.

Вихідні дані
Вихідний файл повинен містити єдине число — шукану кількість.

Приклад

2. Магічний лабіринт (автор — Михайло Рибак)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: magiclab.in
Вихідний файл: magiclab.out
Програма: magiclab.*

Магічний лабіринт є прямокутною таблицею з H рядків та W стовпчиків (0 < H < 100, 0 < W < 100), кожна клітина якої містить нуль або одиницю. Нулі відповідають вільним клітинам, одиниці — стінам. Магічний він через те, що вміст клітин змінюється щосекунди. Протягом першої секунди кожна клітина містить одиницю. Вміст кожної клітини змінюється з відповідним їй періодом а: протягом перших (а – 1) секунд клітина містить 1, протягом наступної секунди — 0, протягом наступних (а – 1) секунд — знову 1, протягом наступної секунди — знову 0, і так далі. Число a для кожної клітини своє (1 < a < 24).

Шляхом у лабіринті назвемо послідовність клітин, кожна з яких містить нуль, та кожні дві послідовні клітини якої мають спільну сторону.

Завдання
Визначити найменше додатне t, при якому протягом t-тої секунди справджуються такі дві умови:
1) клітинки (1, 1) та (H, W) містять нулі;
2) існує шлях у лабіринті, що сполучає ці дві клітини.

Вхідні дані
У першому рядку вхідного файла записано натуральні числа H та W.

Кожен з наступних Н рядків містить по W чисел: j-те число k-го рядка задає величину а для клітини у j-му стовпчику та k-му рядку.

Вихідні дані
Вихідний файл має містити лише одне ціле число — шукане t. У випадку, якщо такого t не існує, відповіддю вважають число нуль.

Приклади

Примітка
В останньому прикладі вміст магічного лабіринту змінюється так.

3. Шаховий клуб (автор Дмитро Кордубан)

Максимальна оцінка: 100 балів
Обмеження на час: 2 сек.
Обмеження на пам'ять: 32 МБ
Вхідний файл: cclub.in
Вихідний файл: cclub.out
Програма: cclub.*

Петрик регулярно відвідує шаховий клуб. До клубу ходить багато шахістів, кожного з яких характеризують за допомогою двох чисел: віком та рівнем гри. Кожен з гравців прагне підвищити свій рівень гри, тому він хоче грати білими фігурами лише з одночасно досвіченішим і сильнішим партнером. Якщо таких кандидатів декілька, він вибирає того, чий рівень гри найменший. Якщо невизначеність зберігається, він вибирає наймолодшого.

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

Вхідні дані
Перший рядок вхідного файлу містить єдине натуральне число N — кількість подій, N ≤ 200 000.

Наступні N рядків містять опис подій в порядку зростання часу:

• рядок „P x y” означає, що прийшов гравець віком x секунд і з рівнем гри y. Ці параметри гравців натуральні й менші за 2³². Гарантовано, що жодна пара гравців не може бути одночасно одного віку та сили гри;

• рядок „G p” означає, що гравець p хоче зіграти гру білими фігурами (гравців нумерують у порядку їхнього приходу). Гарантовано, що всі такі події коректні, тобто номер гравця не перевищує кількість гравців, що прийшла.

Вихідні дані
Для кожної події другого типу (гравець хоче зіграти гру білими фігурами) виведіть номер гравця (в порядку приходу), з яким би хотів зіграти відповідний гравець, або 0 у випадку якщо такого немає.

Приклад

4. Шахи (автор Сергій Могильний)

Максимальна оцінка: 100 балів
Обмеження на час: 5 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: chess.in
Вихідний файл: chess.out
Програма: chess.*

Петрик зацікавився шахами. Проте традиційні шахи йому наскучили досить швидко — одразу після того, як він зайняв перше місце з шахів серед юніорів. Тепер він цікавиться варіаціями на тему шахових фігур на різноманітних дошках. Наразі, Петрика цікавіть кількість варіантів розташування довільної (можливо, нульової) кількості шахових коней на дошці 4×N так, щоб вони не атакували один одного. Проте він не любить працювати з великими числами, і тому Петрику достатньо знайти остачу від ділення цієї кількості на деяке число P. Допоможіть йому у цьому нелегкому завданні.

Завдання
Обчислити остачу від ділення на P кількості можливих розміщень шахових коней на дошці 4×N, при яких вони не атакують один одного.

Вхідні дані
В єдиному рядку вхідного файлу записано два натуральних числа — довжина дошки N (2 ≤ N ≤ 10⁹) і дільник P (2 ≤ P ≤ 10⁹).

Вихідні дані
Єдиний рядок вихідного файлу має містити одне ціле число — остачу від ділення на P кількості можливих розміщень шахових коней на дошці 4 на N, при яких вони не атакують один одного.

Примітка
Шаховий кінь (на рисунку позначено літерою К) атакує до 8 клітин (на цьому самому рисунку позначено літерою А).

Для 15% тестів N ≤ 7.
Для 70% тестів N ≤ 10000.

Приклади

5. Факторіали (автор — Юрій Знов'як)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: factrl.in
Вихідний файл: factrl.out
Програма: factrl.*

Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.

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

• при N = 7 кодом буде 504, бо 7! = 5040;
• при N = 17 кодом буде 096, бо 17! = 355687428096000.

Завдання
За даним натуральним числом N знайти три послідовні цифри числа N!, що записують безпосередньо перед нулями наприкінці запису числа N! .

Вхідні дані
Вхідний файл містить єдине ціле число N (7 ≤ N ≤1 000 000 000).

Вихідні дані
Вихідний файл має містити рівно три цифри — шуканий код.

Приклади

Примітка
У 20% вхідних файлів N не перевищує 10 000 000.
У 35% вхідних файлів N не перевищує 100 000 000.

6. Школа (автор — Данило Мисак)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: school.in
Вихідний файл: school.out
Програма: school.*

Петро П’яточкін учиться в школі. Торік він їздив до школи тролейбусами, але після подорожчання проїзних квитків збагнув, що швидше і зручніше діставатись туди пішки. Місто Ідеальне, де мешкає Петрик,— це прямокутник завбільшки m на n кварталів, складений з однакових квадратних блоків. Межа міста проходить не вздовж межі кварталів, а ділить їх навпіл або «відрізає» від кутових кварталів чвертинки — див. схему міста на рис 1.

Рис. 1. Схема міста Ідеальне. Межі міста позначено грубою чорною лінією.

Петрик вирушає до школи з найпівденнішого та водночас найзахіднішого з кутів кварталів, що належать місту, та прямує до найпівнічнішого та найсхіднішого кута, де розташовано вхід до школи. Початковий та кінцевий пункти позначено на рис. 1 міста жирними крапками. Хлопець може пересуватися лише межами кварталів (самі квартали, ясна річ, забудовано) та переходити з вершини одного кварталу на вершину сусіднього лише перпендикулярно до напряму вулиці — паралельно межам міста. Для кожного перехрестя визначено тривалість t горизонтального (зі сходу на захід і навпаки) та вертикального (з півночі на південь і назад) руху. Кожний світлофор працює так: протягом перших t секунд світлофор дозволяє горизонтальний рух і забороняє вертикальний, протягом наступних t дозволяє вертикальний (та забороняє горизонтальний), з 2(t + 1)-ої секунди до 3t-ої знову дозволяє горизонтальний і т. д. Для різних перехресть ця величина t може бути різною. Пройти один бік кварталу Петрик може за хвилину. Вулицю хлопець переходить за секунду — коли світлофори це дозволяють. Переходити ж на червоне світло та виходити за межі міста Петрик не хоче — це надто небезпечно.

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

Вхідні дані
У першому рядку вхідного файла вказано натуральні числа m та n — ширину й висоту міста. Ці числа не перевищують 250.

Подальший уміст файла — n рядків. При i та j таких, що 1 ≤ i ≤ n, 1 ≤ j ≤ m, j-те число (i + 1)-го рядка — тривалість руху на відповідному перехресті. Це число натуральне й не перевищує 500. В кожному рядку перераховано перехрестя від найзахіднішого до найсхіднішого, в першому рядку описано найпівнічніші перехрестя, в останньому — найпівденніші.

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

Приклад

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

Легко побачити, що швидше ніж за 187 секунд хлопець до школи не потрапить. Справді, якби Петрику взагалі не доводилось чекати на зелене світло, він міг би дістатись до школи щонайшвидше за 185 секунд (він мав би тричі пройти вздовж кварталів та п’ять разів перейти вулицю). З іншого боку, перед тим як уперше перейти вулицю в північному напрямі — хай скільки кварталів він пройде в східному — хлопцю потрібно чекати щонайменше 2 секунди.

Рис. 2. Один з оптимальних шляхів Петрика до школи
для поданого прикладу вхідних даних.