Google Code Jam 2016. Задача C квалификационного раунда


Джемкойны

Джемкойн – это строка из N ≥ 2 цифр со следующими свойствами:

  • Используются только цифры 0 и 1.
  • Первая и последняя цифры: 1.
  • Интерпретация строки в любой системе счисления с основанием от 2 до 10 включительно даёт составное (не простое) число.

Не каждая строка из нулей и единиц может считаться джемкойном. Например, строка 101 не является джемкойном, т.к. в двоичной системе она даёт простое число 5. Строка 1001 – джемкойн: в системах счисления с основанием от 2 до 10 она интерпретируется как 9, 28, 65, 126, 217, 344, 513, 730 и 1001 соответственно, при этом ни одно из этих чисел не является простым.

Мы слышали, что в некоторых сообществах джемкойны используются в качестве валюты. Правила хорошего тона предписывают отправлять джемкойн вместе с доказательством его правильности, а именно нетривиальными делителями для каждой его интерпретации в системах счисления с основанием от 2 до 10. (Нетривиальным делителем положительного целого числа K является некоторое положительное число, отличное от 1 и K,  которое делит K без остатка.) Для удобства делители приводятся в десятичной системе.

Например, для джемкойна 1001 один из возможных наборов нетривиальных делителей для систем с основанием от 2 до 10 таков: 3, 7, 5, 6, 31, 8, 27, 5 и 77 соответственно.

Можете ли вы привести J разных джемкойнов длиной N вместе с доказательством их правильности?

Входные данные

Первая строка содержит количество наборов данных, T. Далее находятся T наборов данных. Каждый из них состоит из одной строки с числами N и J.

Выходные данные

Для каждого набора данных выведите J+1 строк. Первая строка имеет вид Case #x: y, где x – номер набора данных (начиная с 1). Каждая из последующих J строк должна содержать джемкойн и девять целых чисел. i-е число (начиная с 1) должно быть нетривиальным делителем числа, полученного в результате интерпретации джемкойна в системе с основанием i+1.

Все джемкойны должны быть разными. Нельзя выводить один и тот же джемкойн в двух строках даже при разных наборах делителей.

Пределы

T = 1 (только один набор). Гарантируется, что существуют, по крайней мере, J разных джемкойнов длиной N.

Малый набор данных

N = 16.
J = 50.

Большой набор данных

N = 32.
J = 500.

Обратите внимание на то, что вы заранее знаете содержимое каждого входного файла (это нетипично для задач Code Jam). Так, входной файл малого набора данных всегда будет состоять из этих строк:

1
16 50

Пример

Входные данные

1
6 3

Выходные данные

Case #1:
100011 5 13 147 31 43 1121 73 77 629
111111 21 26 105 1302 217 1032 513 13286 10101
111001 3 88 5 1938 7 208 3 20 11

В этом примере мы использовали маленькие значения N и J для простоты объяснения. Учтите, что этого примера не будет ни в малом, ни в большом наборах данных.

Это лишь одно из многих правильных решений. Можно использовать другие наборы джемкойнов, а также множество других наборов нетривиальных делителей. Некоторые замечания:

  • 110111 использовать нельзя, потому что в троичной системе это простое число 337 (1*243 + 1*81 + 0*27 + 1*9 + 1*3 + 1*1).
  • 010101 не подходит, хотя 10101 джемкойн, потому что джемкойны должны начинаться с единицы.
  • 101010 не годится, так как джемкойны заканчиваются единицей.
  • 110011 – джемкойн, однако лишний, поскольку выходные данные должны содержать ровно J примеров.
  • Для первого джемкойна первое число после строки 100011 не может быть 1 или 35, потому что это тривиальные делители числа 35 (100011 в двоичной системе).

Решение на Pascal для малого набора данных

Реклама
Запись опубликована в рубрике перевод с метками . Добавьте в закладки постоянную ссылку.

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s