Завдання № 29
відбірково-тренувальних зборів
команди міста Києва


за матеріалами ІІІ (міського) етапу 2012 року

1. Числа

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

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

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

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

      Приклади

numbers.innumbers.out
2 0
10
2

2 1
20
3

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

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

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

2. Гра

Максимальна оцінка: 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} — призводить до його програшу.

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

      Для Free Pascal модуль має такі складові:

      Для C++ бібліотека має такі складові:

Використання модуля gamelib

  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 знаків десяткового запису після коми і підсумовано за всіма тестами. Отримана сума, округлена до найближчого цілого, і буде остаточною оцінкою Вашої програми. Програми членів журі участі в оцінюванні не беруть.