1. Поліклініка

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

      На прийом до лікаря щодня приходить чимало людей. Кожен пацієнт перебуває на прийомі цілу кількість хвилин, але різних пацієнтів лікар може приймати різну кількість часу. Лікар починає прийом у момент часу t₁ хвилин і закінчує прийом у момент часу t₂ хвилин. Це означає, що будь-який пацієнт незалежно від того, скільки часу його прийматиме лікар, може зайти на прийом у моменти t₁, t₁ + 1, …, t₂ – 1. Заходити на прийом до лікаря в інший час або тоді, коли лікар приймає іншого пацієнта, заборонено. Якщо пацієнт приходить у поліклініку в момент t, він чекає на перший момент часу s ≥ t такий, що на цей момент лікар веде прийом, причому вже встиг оглянути всіх пацієнтів, які прийшли у поліклініку раніше, тобто до моменту t. Якщо лікар не встигає оглянути всіх до кінця прийому, решта пацієнтів має прийти наступного дня.

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

      Вхідні дані
      У першому рядку вхідного файлу вказано три числа: кількість охочих потрапити на прийом n, час початку прийому t₁ і час завершення прийому t₂, що більший за t₁.
      У другому рядку перераховані n чисел a₁, a₂, …, a_n — час, коли у поліклініку зайшли відповідно перший, другий, …, n-й охочий потрапити до лікаря. Числа a₁, a₂, …, a_n попарно різні й розташовані у порядку зростання.
      У третьому рядку вхідного файлу перераховані n чисел b₁, b₂, …, b_n — час, необхідний лікарю на огляд відповідно першого, другого, …, n-го пацієнта.
      Усі числа у вхідному файлі натуральні. Кількість пацієнтів n не більша за 10⁵, решта чисел не перевищують 10⁹.
      Доба на планеті, де мешкає Петрик П’яточкін, триває значно довше, ніж на Землі, тому час початку прийому t₁, час завершення прийому t₂, а також числа a₁, a₂, …, a_n та b₁, b₂, …, b_n можуть бути більшими за 1440 — кількість хвилин у земній добі.

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

      Приклади

Пояснення
      В усіх чотирьох прикладах лікар запускає на прийом із 10-ї до 19-ї хвилини включно.
      У першому прикладі пацієнт, що прийшов у момент часу 7 хв, зайде до лікаря першим, тобто о 10-й хвилині, а вийде через 5 хвилин. Відразу після цього — о 15-й хвилині — в кабінет зайде пацієнт, що прийшов у момент часу 14 хв. Він вийде з кабінету через 2 хвилини, відразу після чого ні в кабінеті, ні в черзі нікого не буде. Отже, якщо Петрик П’яточкін прийде в поліклініку о 17-й хвилині, він не чекатиме ні хвилини. Зауважимо: якби Петрик прийшов о 18-й чи о 19-й хвилині, він би також не чекав. Але вивести потрібно 17, бо це перший з усіх моментів часу, коли Петрик може прийти, щоб не чекати на прийом.
      У другому прикладі Петрик повинен чекати не менше ніж 5 хвилин незалежно від того, коли він прийде в поліклініку. Найвигідніший варіант — прийти о 9-й хвилині, щоб зайти в кабінет другим о 14-й хвилині. У цьому випадку одночасно з хлопцем прийде ще один пацієнт. Але згідно з умовою задачі цей пацієнт пропустить Петрика вперед.
      У третьому прикладі єдиний спосіб для Петрика потрапити до лікаря у перший день прийому — прийти не пізніше за іншого пацієнта.
      У четвертому прикладі хлопцю достатньо прийти у момент початку прийому — він одразу потрапить до лікаря.

2. Фарбування

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

      На заняттях шкільного гуртка Євгенію навчили виготовляти з паперу моделі правильних многогранників (платонових тіл) і напівправильних многогранників (архімедових тіл). Вона запам’ятала такі означення:

1. Платоновим тілом називають (опуклий) многогранник, у якому всі грані — правильні однакові многокутники, а многогранні кути при всіх вершинах однакові.

2. Архімедовим тілом називають (опуклий) многогранник, у якому всі грані — правильні многокутники (не обов’язково з однаковою кількістю сторін), а многогранні кути при всіх вершинах однакові. При цьому є щонайменше дві різні грані.

      Таким чином, в архімедовому тілі грані кожного виду зустрічаються в тій самій кількості й у тій самій послідовності при обході навколо кожної вершини (чи для однакових, чи для протилежних напрямів обходу, якщо «дивитися ззовні»).
      Кілька моделей многогранників Євгенія виготовила для оформлення кабінету математики і прихопила додому, щоб вразити своїх рідних. Враження, звичайно, вона справила. Але, вечеряючи, недогледіла, як молодша сестра Марічка взялася розфарбовувати грані: кожну грань лише однією фарбою. При цьому кілька граней могли бути й одного кольору, навіть якщо вони були суміжними, тобто мали спільне ребро. Євгенія задумалась… Її, як майбутнього математика, зацікавило питання: скількома способами можна розфарбувати грані тіла, маючи певну кількість фарб, з точністю до симетрій — рухів простору, що залишають многогранник на тому самому місці. Інакше кажучи, коли не розрізняють розфарбування, отримані одне з іншого взаємно однозначним відображенням граней при збереженні відношення суміжності.

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

      Вхідні дані
      У першому рядку вхідного файлу вказано натуральну кількість фарб m, m < 6.
      Кількість рядків вхідного файлу на 1 перевищує кількість граней многогранника і менша від 24. Усі грані многогранника занумеровано послідовними натуральними числами, починаючи з 1. При j > 1 j-й рядок містить (невпорядкований) перелік номерів граней, суміжних з гранню ( j – 1).
      Вхідні дані гарантують, що кількість симетрій многогранника не перевищує 120.

      Вихідні дані
      Вихідний файл має містити кількість розфарбувань граней тіла, виконаних за допомогою m фарб і різних з точністю до симетрій многогранника.

      Приклад

      Пояснення
      Різні розфарбування двома фарбами правильного 4-гранника, який є трикутною пірамідою, розрізняють лише за кількістю граней одного кольору.

3. Істотні інверсії

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

      Розглянемо довільну послідовність чисел x₁, x₂, …, x_n. Пару індексів (j, k) називають інверсією (порушенням порядку), якщо j < k та x_j > x_k. Для довільного невід’ємного числа t пару індексів (j, k) назвемо t-істотною інверсією, якщо j < k та x_j > x_k + t.

      Завдання
      Підрахувати кількість t-істотних інверсій у послідовності x₁, x₂, …, x_n.

      Вхідні дані
      Перший рядок містить записи двох цілих чисел n та t при 1 ≤ n ≤ 50000, 0 ≤ t ≤ 10⁹. У другому рядку записано цілі числа x₁, x₂, …, x_n, які за модулем не перевищують 10⁹.

      Вихідні дані
      Єдиний рядок вихідного файлу має містити кількість t-істотних інверсій у послідовності x₁, x₂, …, x_n.

      Приклади

      Пояснення до прикладів
      У прикладі 1 інверсії такі: (4, 5), (4, 6) і (5, 6). Усі ці інверсії — 0-істотні.
      У прикладі 2 інверсії такі: (3, 4) і (3, 5). Але x₃ ≤ x₅ + 2, тобто інверсія (3, 5) не є 2-істотною. Такою є лише пара (3, 4).

4. Фортеця

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

      На полі потрібно збудувати фортецю. План її вигляду згори повинен мати форму невиродженого опуклого многокутника, сторони якого зображують вали, а вершини — вежі. Також вежі можна розташовувати на валах. Місцевість, де треба збудувати фортецю, є дуже різноманітною з гео- та гідрологічної точки зору. Тому будувати вежі можна лише у певних точках. На відміну від веж, прямолінійні вали можна насипати довільно. Чим більше веж розташовано вздовж огорожі фортеці, тим краще.

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

      Вхідні дані
      Перший рядок містить запис цілого числа n (1 ≤ n ≤ 100) — кількості точок, де можна будувати вежі. У кожному з наступних n рядків записано по два цілих числа x_j та y_j — координати точки, де можна будувати вежу (| x_j | ≤ 10000, | y_j | ≤ 10000). Усі точки (x₁, y₁), (x₂, y₂), ..., (x_n, y_n) є різними.

      Вихідні дані
      Єдиний рядок вихідного файлу має містити запис найбільшої кількості веж фортеці. Якщо побудувати фортецю неможливо, то потрібно записати 0.

      Приклади

5. Вкладені множини

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

      Петрик нещодавно дізнався про поняття множини і вкладення множин. Він зацікавився послідовностями:

у яких кожний наступний елемент — підмножина попереднього, S₀ — певна скінченна множина {a₁, a₂, …, a_M}. Петрик зауважив: кожній з вкладених множин можна поставити у відповідність ціле число:

Таким чином, H(S₀) = 2^M – 1, H(∅) = 0.
      Петрик випадковим чином обрав N чисел: h₁, h₂, …, h_N . Йому стало цікаво: скільки існує різних наборів вкладених множин S₁, S₂, …, S_N при
H(S₁) = h₁ (mod 41),
H(S₂) = h₂ (mod 41), …,
H(S_N) = h_N (mod 41)?
      На жаль, Петрик збився з рахунку, тому просить вас про допомогу.

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

      Вхідні дані
      Перший рядок вхідного файлу містить два цілих числа N і M: 1 ≤ N ≤ 5, 1 ≤ M ≤ 20.
      Другий рядок містить N цілих чисел h₁, h₂, …, h_N , кожне з яких задовольняє умову: 0 ≤ h_j ≤ 40.

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

      Приклади

1. Існує лише один варіант: S₁ = {a₁, a₂, a₃}, S₂ = S₃ = {a₁, a₂}. H(S₁) = 7, H(S₂) = H(S₃) = 3.
2. Такої послідовності вкладених множин не існує.
3. H({a₁, a₂}) = 2^{1 – 1} + 2^{2 – 1} = 3,
   H({a₃, a₄, a₆, a₂}) = 2² + 2³ + 2⁵ = 4 + 8 + 32 = 44 = 41 + 3,
   H({a₁, a₃, a₅, a₇}) = 2⁰ + 2² + 2⁴ + 2⁶ = 1 + 4 + 16 + 64 = 85 = 2∙41 + 3,
   H({a₂, a₃, a₄, a₅, a₆, a₇}) = 2¹ + 2² + 2³ + 2⁴ + 2⁵ + 2⁶ =
   = 2 + 4 + 8 + 16 + 32 + 64 = 126 = 3∙41 + 3.

6. Портали

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

      Деякі планети галактики, куди нещодавно переїхав Петрик П’яточкін, сполучено порталами. Якщо планети А і Б сполучено, це означає, що на кожній із планет стоїть спеціальний пристрій — портал — для телепортації між ними. Істота, що входить у портал на планеті А, миттєво опиняється на планеті Б і навпаки.
      Один і той самий портал не можна використовувати для телепортації на різні планети. Якщо між парою планет ще немає сполучення, їх можна сполучити, але лише побудувавши на кожній із них по новому порталу. Будівництво порталів вимагає чималих витрат і може коштувати по-різному на різних планетах.
      Будемо казати, що між двома планетами існує шлях телепортації, якщо з однієї планети можна потрапити на іншу, телепортувавшись один або кілька разів (використовуючи проміжні планети). На жаль, поки що не між кожними двома планетами існує шлях телепортації.

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

      Вхідні дані
      У першому рядку вхідного файлу вказано два натуральних числа:
n — кількість планет галактики, n ≤ 1000;
m — кількість пар планет, безпосередньо сполучених між собою порталами.
      У другому рядку перераховані n натуральних чисел p₁, p₂, …, p_n — вартості будівництва нового порталу відповідно на першій, другій, …, n-й планеті. Жодна з вартостей не перевищує 10⁶.
      У кожному з наступних m рядків записано по два натуральних числа a_j та b_j, 1 ≤ a_j < b_j ≤ n, 1 ≤ j ≤ m, які задають пару сполучених між собою планет. Кожну пару записано у вхідному файлі лише один раз.

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

      Приклад

      Пояснення
Можна сполучити четверту планету або з першою, або з третьою, задоволь­нив­ши умову задачі і витративши 3 + 7 = 10 грошових одиниць. Легко зрозуміти, що меншою кількістю витрачених грошей обійтися не вдасться.