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

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

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

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

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

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

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

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

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

      Приклад

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

2. Фортеця

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 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.

      Приклади

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

Максимальна оцінка: 100 балів
Обмеження на час: 1,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.