1. Перетин — об’єднання (автор — Олександр Рудик)

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

      На уроках математики Петрик ознайомився з такими поняттями:

• перетином сукупності множин називають множину усіх тих елементів, що належать до усіх множин сукупності;
• об’єднанням сукупності множин називають множину усіх тих елементів, що належать хоча б до однієї з множин сукупності.

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

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

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

• або одноелементну множину таким чином:
  «{» + десятковий запис натурального числа без коми чи крапки + «}»;
• або проміжок таким чином: «[» або «(»
  десятковий запис лівого кінця проміжку без коми чи крапки
  «;»
  десятковий запис правого кінця проміжку без коми чи крапки
  «)» або «]».

Квадратні дужки «[» або «]» вказують на належність відповідного кінця до проміжку. Круглі дужки «(» або «)» вказують на те, що відповідний кінець не належить до проміжку. Усі кінці проміжків і елементи усіх одноелементних множин натуральні й не перевищують 3(n + 4).
      Останній рядок вхідного файлу порожній.
      Передбачено перевірку для таких величин n: 2, 8, 4000, 40 000. Відповідні вхідні файли містять по 249, 249, 249 і 261 тестів, тобто по 749, 2243, 996 251 і 10 440 263 рядків.

      Вихідні дані
      Вихідний файл складається з груп по 3 рядки. Кількість груп така сама, як кількість тестів у вхідному файлі.
      Перший рядок групи має містити традиційний запис (див. вимоги до вхідних даних) перетину множин, заданих відповідною групою вхідного файлу. Якщо перетин порожній, то цей рядок містить лише два символи «{}».
      Другий рядок групи має містити традиційний запис об’єднання множин, заданих відповідною групою вхідного файлу, з використанням великої літери латиниці «U» для позначення операції об’єднання. Це об’єднання потрібно подати об’єднанням проміжків і одноелементних множин таким чином:

• об’єднання довільних двох проміжків або довільного проміжку й довільної одноелементної множини не є проміжком;

• проміжки та одноелементні множини записано у порядку руху у додатному напрямі дійсної прямої, тобто у порядку зростання кінців проміжків та елементів одно¬елемент¬них множин.

      Третій рядок групи має бути порожнім.

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

• j — кількість непорожніх рядків еталонного файлу, що збігаються з відповідними рядками вихідного файлу;

• k — кількість непорожніх рядків еталонного файлу, що збігаються з відповідними рядками вихідного файлу після вилучення додатної кількості пропусків;

• l — кількість усіх непорожніх рядків еталонного файлу.

      Приклади

2. Числа (автор — Ярослав Твердохліб)

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

      Завдання
      Дано три цілих числа N, a і b. Потрібно знайти залишок від ділення на число 1 000 000 007 (10⁹ + 7) кількості натуральних чисел X, для яких одночасно справджуються такі три умови:
1) X ≤ N;
2) X кратне 2^a;
3) сума цифр числа X кратна 2^b.

      Вхідні дані
      Перший рядок вхідного файлу містить 2 цілих числа: a та b (0 ≤ a ≤ 9, 0 ≤ b ≤ 9).
      Другий рядок містить число N (1 ≤ N ≤ 10⁵⁰⁰⁰).

      Вихідні дані
      Вихідний файл має містити одне число — залишок від ділення на число 1 000 000 007 (10⁹ + 7) кількості натуральних чисел X, для яких справджуються усі умови 1–3, подані вище.

      Приклади

      Пояснення
      Лише числа 4, 8 і 20 задовольняють умову другого прикладу.

      Зауваження щодо оцінювання

1. У 15% тестів 1 ≤ N ≤ 1 000 000.
2. Ще у 15% тестів b = 0.
3. Ще у 15% тестів a = 0.
4. Ще у 20% тестів N ≤ 10⁵⁰⁰, a ≤ 4, b ≤ 4.
5. У решті 35% тестів жодних обмежень на змінні, крім описаних у секції «Вхідні дані», не накладено.

3. Іншопланетний словник (автор — Юрій Знов’як)

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

      У віддаленому майбутньому землянами було знайдено планету, на якій раніше жили невідомі людству розумні істоти. Самих істот знайти не вдалося, але було знайдено їхню бібліотеку з великою кількістю писемних матеріалів. Вчені негайно приступили до розшифровування цих матеріалів, сподіваючись зрозуміти, де, власне, самі істоти.
      Аналіз наявних текстів встановив, що в іншопланетній системі письма використовують абетку з N літер, а кожне слово містить M літер. Вчені знайшли щось схоже на словник, який має значно допомогти в розумінні цієї мови. Слова в цьому словнику упорядковано не в лексикографічному порядку, а в порядку спадання «важливості». Якщо «важливість» двох слів однакова, то раніше записано лексикографічно менше слово.
      Для довільного слова a₁ a₂... a_M цю «важливість» знаходять як суму:

      Розглянемо такий приклад. При N = 2 (кількість літер) і M = 3 (довжина слова) у цій мові можливі 8 різних слів. Запишемо ці слова в лексикографічному порядку. Позначатимемо тут і далі k-ту літеру іншопланетної абетки k-ю літерою латиниці: aaa, aab, aba, abb, baa, bab, bba і bbb. Нехай матриця має такий вигляд:

      Тоді важливість слів буде такою:
aaa: 8 = 1 + 5 + 2;
aab: 12 = 1 + 5 + 6;
aba: 10 = 1 + 7 + 2;
abb: 14 = 1 + 7 + 6;
baa: 12 = 5 + 5 + 2;
bab: 16 = 5 + 5 + 6;
bba: 14 = 5 + 7 + 2;
bbb: 18 = 5 + 7 + 6.
У словнику порядок слів такий: bbb, bab, abb, bba, aab, baa, aba, aaa.
      Для подальшого аналізу ученим-землянам потрібно вміти швидко обчислювати, яке слово буде міститися на певному місці в такому словнику згідно з описаними правилами впорядкування: спочатку за спаданням «важливості», а при однаковій «важливості» — у алфавітному порядку.

      Завдання
      За відомими N, M, K і матрицею p_jc визначити, яке слово стоятиме на K-му місці у словнику іншопланетних істот.

      Обмеження:

• в усіх тестах 2 ≤ N ≤ 16, 1 ≤ M ≤ 10, 0 ≤ p_jc ≤ 10⁸, 1 ≤ K ≤ N ^M;
• у 15% тестів K ≤ 1000;
• ще у 15% тестів M ≤ 5;
• ще в 10% тестів M ≤ 5 і K ≤ 10 одночасно.

      Вхідні дані
      Перший рядок файлу містить три цілі числа: N, M і K. Рядки з 2-го до (M + 1)-го містять по N цілих чисел — відповідні елементи матриці p_jc.

      Вихідні дані
      Єдиний рядок файлу має містити слово, яке розташоване на K-му місці у словнику іншопланетних істот.

      Приклад

4. Флюорографія (автор — Данило Мисак)

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

      На флюорографічне обстеження зібралися n марсіан k різних статей. Усі обстежувані певним чином вишикувалися в чергу. У кабінет флюорографії запускають по m осіб одразу, але лише якщо вони однієї статі. Якщо перша на даний момент особа в черзі має стать s, запускають цю особу, а також наступних (m – 1) представника статі s із черги, навіть якщо перед кимось із них стояли представники інших статей. Якщо в черзі лишилося менше ніж m представників даної статі, в кабінет запускають їх усіх, а представники інших статей мають чекати. Кожна група марсіан, починаючи з другої, заходить через годину після попередньої (навіть якщо попередня група складалася менше ніж із m обстежуваних).

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

      Вхідні дані
      У першому рядку вхідного файлу вказано кількість марсіан у черзі n, кількість статей k і максимальний розмір групи m. Усі три числа натуральні та не перевищують 100 000. У другому рядку задано n чисел, розділених символами пропуску. Число на i-му місці — стать особи, що стоїть i-ю в черзі. Стать задано натуральним числом від 1 до k включно.
      У 40 % тестів до цієї задачі n, k та m не перевищують 1000, а ще в 20 % тестів k не більше за 10.

      Вихідні дані
      Вихідний файл повинен містити n чисел, розділених символами пропуску. Число на i-му місці — кількість годин після початку обстеження, коли i-та особа з черги потрапить у кабінет флюорографії.

      Приклади

      5. Симетричні візерунки (автор — Олександр Рибак)

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

      У місцях імовірної посадки іншопланетних космічних кораблів іноді знаходять симетричні візерунки, відомі як «кола на полях». Інколи такі візерунки підробляють жартівники. Звичайно, люди не можуть досягти того рівня симетрії, який мають справжні «кола на полях». Тому підробку можна викрити. На одному полі було помічено два візерунки. Для перевірки їхньої справжності ці візерунки сфотографували. На знімку через центри візерунків провели пряму, а на цій прямій відмітили точки, що належать візерункам. Достеменно не відомо, які точки належать якому візерунку. Але можна бути певним, що на проведеній прямій усі точки одного візерунка лежать по один бік від усіх точок іншого візерунка.

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

      Вхідні дані
      У першому рядку вхідного файлу вказана кількість тестів T, яка дорівнює 1 або 2. Кожен тест описаний у окремому рядку. На початку кожного рядка стоїть ціле число N (1 ≤ N ≤ 100 000) — кількість точок на прямій для даного тесту. Далі йдуть N різних цілих чисел x₁, x₂, ..., x_N — координати точок на прямій. Відомо, що 0 ≤ x₁ < x₂ < … < x_N ≤ 2⋅10⁹. Числа у рядку розділено пропусками.

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

      Приклади

6. Гра (автор — Дмитро Кордубан)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Модуль для отримання вхідних даних
і повідомлення вихідних даних: gamelib.pas, gamelib.h
Програма: game.*

      Сашко та Олеся грають у таку гру. Олеся загадує два різні натуральні числа від 1 до N, а Сашко намагається їх вгадати. Для цього він кілька разів називає підмножини Q множини {1, 2, …, N}, а Олеся відповідає про одне із загаданих чисел, чи належить воно до Q. При цьому вона може довільним чином вибирати число, про яке відповідає. Тобто інколи відповідати про одне, інколи — про інше. Сашко перемагає, якщо може назвати таку підмножину A множини {1, 2, …, N}, що в ній загаданих Олесею чисел більше, ніж не загаданих. Інакше кажучи, A — це:

• або одноелементна множина, що містить одне із загаданих чисел;
• або двоелементна множина, що містить обидва загадані числа;
• або триелементна множина, що містить обидва загадані числа.

      Наприклад, якщо було загадано числа 3 та 5, то одна з таких остаточних відповідей: {3}, {5}, {3, 5}, {2, 3, 5} — призводить до виграшу Сашка, а одна з таких відповідей:{5, 10} чи {2, 3, 4, 5} — призводить до його програшу.

      Завдання
      Створіть програму, яка:

• використовує модуль (бібліотеку) gamelib, наданий журі;
• грає в цю гру на боці Сашка і гарантує йому виграш.

      Для Free Pascal, Turbo Delphi Explorer 2006 модуль має такі складові:

• procedure init(var n:integer);
• function query(q: string): boolean;
• procedure finish(a: string);

      Для Visual C++ 2008 Express Edition, Dev C++ 4.9.9.2 з Mingw/GCC 3.4.2 бібліотека має такі складові:

• void init(int &n);
• bool query(char q[]);
• void finish(char a[]);

1. Оголосіть використання модуля рядками uses gamelib; або #include "gamelib.h" залежно від мови програмування.

2. Викличте процедуру (функцію) init(N) один раз на початку програми, щоб дізнатись величину N (2 ≤ N ≤ 100). Повторний виклик init призведе до оцінки 0 балів за тест.

3. Ви можете викликати функцію query(q) не більше ніж 10 000 разів, щоб отримати інформацію про загадані Олесею числа. Рядковий параметр q задає множину чисел Q. Він має складатись точно з N символів «0» та/або «1». Одиниця в i-й позиції рядка (q[i] в Pascal, q[i-1] в C++) означає, що число i належить до Q, нуль — що не належить. Функція повертає true, якщо вибране Олесею загадане нею число належить до заданої множини, а false — в іншому разі. Перевищення максимальної кількості викликів або порушення формату параметра q призведе до оцінки 0 балів за тест.

4. Викличте процедуру (функцію) finish(a) один раз в кінці програми, щоб сповістити про виграш Сашка. Параметр a має задавати виграшну множину A. Його формат збігається з форматом q для query. Повторний виклик finish або порушення формату параметра a призведе до оцінки 0 балів за тест.

      Оцінювання результатів роботи програми Програму буде перевірено на серії тестів. Для кожного тесту число N стале для всіх учасників, а загадані числа можуть відрізнятися для кожного з учасників. При цьому вони одні й ті самі для програми з детермінованим (не стохастичним, тобто без елементів випадковості) алгоритмом. Якщо при проходженні тесту програма порушила технічні умови (формат параметрів, кількість викликань тощо) або повідомила підмножину A, що не є виграшною, то присуджують 0 балів за цей тест. Інакше присуджують таку кількість балів:
m ⋅ (1 + b) / (1 + y), де:
m — максимальна кількість балів, призначена автором завдання за тест (від англ. maximum);
y — кількість викликів query, що зробила ваша програма (від англ. yours);
b — найменша кількість викликів query, що зробила програма якогось учасника на цьому тесті й повідомила виграшну множину A (від англ. best).
      Ці значення буде округлено до 6 знаків десяткового запису після коми і підсумовано за всіма тестами. Отримана сума, округлена до найближчого цілого, і буде остаточною оцінкою Вашої програми. Програми членів журі участі в оцінюванні не беруть.