Статья Автор: Лебедев Дмитрий Алексеевич

8 класс

Магическое число
Вася уже знает о  магическая силе трех простых чисел 7, 11, 13. Из произведение равно 1001.
Также Вася знает, что такое факториал числа ( \(N! = 1\cdot 2\cdot ... \cdot N\)) и умеет записывать числа в системах счисления с различными основаниями
Ещё Вася придумал название для "самой правой ненулевой" цифре числа - он решил назвать её "копчиком" и ему очень понравилось, что при записи числа в различных системах счисления "копчики" будут разные
Например для числа 1001 в системе счисления с основарием 7 и 11 "копчик" равен 3 (1001 = 26307 = 83011), для основания 13 "копчик" равен С (1001 = 5С013)  
Вася решил назвать натуральное число N "интересным", если равны "копчик" числа  равен "копчику" факториала числа, причем это условие должно выполняться при записи в системах счисления с основанияии 7, 11, 13
Поскольку Вася плохо программирует, то он попросил Вас найти все интересные числа для заданного отрезка
 

На информатике Вася научился записывать натуральные числа в системах счисления с основаниями меньшими 10, а на математике он узнал о факториале числа.
Вася решил найти "стабильные числа". Для этого он придумал понятие "копчик записи числа" - это самая правая ненулевая цифра числа. при его записи в системе счисления с некоторым основанием.
Вася решил, что число можно назвать "стабильным числом", если:
  • "копчики записи числа" в системах счисления с основаниями 3, 5, 7 будут одинаковыми
  • " копчики записи факториала числа" в системах счисления с основаниями 3, 5, 7 также будут одинаковыми и равны "копчикам записи числа" 
Поскольку Вася плохо программирует, то он попросил Вас найти все интересные числа для заданного отрезка
Входные данные 
два числа - границы отрезка
Выходные данные
числа удовлетворяющие заданию (в порядке возрастания, в десятичной системе счисления)


Шесть зеркал Тронного зала

Заблудившись в бесконечных лабиринтах Зазеркалья, Алиса отчаянно искала дорогу домой. Когда надежда уже почти покинула её, на ветке высокого дерева возникла знакомая широкая улыбка, а следом появился и сам Чеширский кот.

— Мур-мяу, ищешь выход домой? — спросил Кот, лениво потягиваясь. — Твоя дорога лежит в Тронный зал. Там находится портал выхода, который сторожат шесть волшебных зеркал. Они пропустят только того, кто назовёт правильное натуральное число-ключ.

Кот подробно объяснил Алисе дорогу в Тронный зал и прошептал на ухо заветное число. Попрощавшись, Алиса со всех ног бросилась по указанному пути. Но на крутом повороте она зацепилась за корень, упала и больно ударилась. Когда она добралась до Тронного зала, оказалось, что от удара заветное число вылетело у неё из головы! Алиса смогла вспомнить только то, сколько в этом числе было цифр в десятичной записи и какая цифра стояла на самом первом месте.

Зато Алиса отлично запомнила правило шести зеркал-стражей, окружавших портал:

  1. Первые три зеркала — это Тройное, Пятерное и Семеричное зеркала Числа. Когда Алиса произносит вслух любое натуральное число N, каждое из них переводит это число в систему счисления с соответствующим основанием (3, 5 или 7), но оставляет на поверхности только отблеск — самую правую ненулевую цифру получившейся записи.
  2. Следующие три зеркала — это Тройное, Пятерное и Семеричное зеркала Факториала. Услышав число N, они сначала вычисляют его факториал (N! = 1 · 2 · … · N), затем переводят результат в системы счисления с основаниями 3, 5 и 7 и тоже показывают лишь отблеск — самую правую ненулевую цифру этой записи.

Портал выхода откроется только тогда, когда все шесть отблесков во всех шести зеркалах окажутся абсолютно одинаковыми!

Помогите Алисе вернуться домой: найдите и выпишите все натуральные числа-ключи, которые подходят под её воспоминания и откроют портал в Тронном зале.

Формат входных данных

В первой строке вводится натуральное число K (1 ≤ K ≤ 5) — количество цифр в десятичной записи числа-ключа, которое вспомнила Алиса.
Во второй строке вводится цифра D (1 ≤ D ≤ 9) — первая (самая левая) цифра этого числа.

Формат выходных данных

Выведите в порядке возрастания в десятичной системе счисления все подходящие натуральные числа-ключи, которые откроют портал выхода (каждое число с новой строки). Если среди воспоминаний Алисы подходящих чисел нет, выведите -1.

Примеры входных и выходных данных

Входные данные Выходные данные Пояснение
1
1
1
Проверяем однозначные числа, начинающиеся на 1 (только число 1).
Для N = 1: записи 13, 15, 17 и записи 1! = 1 дают все шесть отблесков, равных 1.
2
1
-1
Проверяем двузначные числа, начинающиеся на 1 (от 10 до 19).
Ни одно из них не даёт шести одинаковых отблесков (например, для N = 10: отблески числа равны 1, 2, 3, а отблески 10! равны 1, 2, 1).
4
1
1506
Проверяем четырёхзначные числа, начинающиеся на 1 (от 1000 до 1999).
Единственное подходящее число на этом отрезке — 1506.

Как работают зеркала: простые примеры и разбор числа 1506

1. Простые примеры поиска отблеска (самой правой ненулевой цифры):

  • Возьмём число N = 12. В троичной системе 12 = 1103 (отбрасываем ноль справа → отблеск 1). В пятеричной 12 = 225 (отблеск 2). В семеричной 12 = 157 (отблеск 5). Уже первые три отблеска разные (1 ≠ 2 ≠ 5), поэтому 12 не подходит.
  • Возьмём число N = 2. Записи самого числа: 23, 25, 27 → отблески 2, 2, 2. Факториал 2! = 2: записи 23, 25, 27 → отблески 2, 2, 2. Все 6 отблесков равны 2 — число 2 открывает портал!

2. Полный разбор числа N = 1506:

  • Шаг 1 (Зеркала Числа): переводим 1506 в нужные системы счисления:
    • 150610 = 20012103 → самая правая ненулевая цифра (отблеск) равна 1.
    • 150610 = 220115 → самая правая ненулевая цифра (отблеск) равна 1.
    • 150610 = 42517 → самая правая ненулевая цифра (отблеск) равна 1.
  • Шаг 2 (Зеркала Факториала): вычисляем отблески числа 1506! в системах с основаниями 3, 5 и 7 (отбрасывая при умножении множители, кратные основанию системы, и оставляя остаток от деления на основание):
    • Отблеск 1506! в троичной системе счисления равен 1.
    • Отблеск 1506! в пятеричной системе счисления равен 1.
    • Отблеск 1506! в семеричной системе счисления равен 1.
  • Итог: все шесть зеркал показали одинаковый отблеск 1, поэтому 1506 является верным ключом.

Четыре зеркала Тронного зала

Заблудившись в бесконечных лабиринтах Зазеркалья, Алиса отчаянно искала дорогу домой. Когда надежда уже почти покинула её, на ветке высокого дерева возникла знакомая широкая улыбка, а следом появился и сам Чеширский кот.

— Мур-мяу, ищешь выход домой? — спросил Кот, лениво потягиваясь. — Твоя дорога лежит в Тронный зал. Там находится портал выхода, который сторожат четыре волшебных зеркала. Они пропустят только того, кто назовёт правильное натуральное число-ключ.

Кот подробно объяснил Алисе дорогу в Тронный зал и прошептал на ухо заветное число. Попрощавшись, Алиса со всех ног бросилась по указанному пути. Но на крутом повороте она зацепилась за корень, упала и больно ударилась. Когда она добралась до Тронного зала, оказалось, что от удара заветное число вылетело у неё из головы! Алиса смогла вспомнить только то, сколько в этом числе было цифр в десятичной записи и какая цифра стояла на самом первом месте.

Зато Алиса отлично запомнила правило четырёх зеркал-стражей, окружавших портал:

  1. Первые два зеркала — это Тройное и Семеричное зеркала Числа. Когда Алиса произносит вслух любое натуральное число N, каждое из них переводит это число в систему счисления с соответствующим основанием (3 или 7), но оставляет на поверхности только отблеск — самую правую ненулевую цифру получившейся записи.
  2. Следующие два зеркала — это Тройное и Семеричное зеркала Факториала. Услышав число N, они сначала вычисляют его факториал (N! = 1 · 2 · … · N), затем переводят результат в системы счисления с основаниями 3 и 7 и тоже показывают лишь отблеск — самую правую ненулевую цифру этой записи.

Портал выхода откроется только тогда, когда все четыре отблеска во всех четырёх зеркалах окажутся абсолютно одинаковыми!

Помогите Алисе вернуться домой: найдите и выпишите все натуральные числа-ключи, которые подходят под её воспоминания и откроют портал в Тронном зале.

Формат входных данных

В первой строке вводится натуральное число K (1 ≤ K ≤ 5) — количество цифр в десятичной записи числа-ключа, которое вспомнила Алиса.
Во второй строке вводится цифра D (1 ≤ D ≤ 9) — первая (самая левая) цифра этого числа.

Формат выходных данных

Выведите в порядке возрастания в десятичной системе счисления все подходящие натуральные числа-ключи, которые откроют портал выхода (каждое число с новой строки). Если среди воспоминаний Алисы подходящих чисел нет, выведите -1.

Примеры входных и выходных данных

Входные данные Выходные данные Пояснение
1
1
1
Однозначное число, начинающееся на 1 — это только число 1.
Записи 13, 17 и записи 1! = 1 дают все четыре отблеска, равных 1.
2
1
-1
Двузначные числа, начинающиеся на 1 (от 10 до 19), не дают четырёх одинаковых отблесков.
2
2
22
23
Среди двузначных чисел на цифру 2 (от 20 до 29) портал открывают два числа: 22 и 23 (разбор числа 22 приведён ниже).

Примеры вычисления отблесков и полный разбор

1. Как находить отблеск (примеры для отдельных чисел):

  • Возьмём число 12. В троичной системе 1210 = 1103. Отбрасываем ноль справа и получаем отблеск 1. В семеричной системе 1210 = 157 — последняя цифра ненулевая, поэтому отблеск равен 5.
  • Возьмём число 21. В троичной системе 2110 = 2103 (отблеск 1), в семеричной 2110 = 307 (отблеск 3).

2. Полный разбор подходящего числа N = 22:

  • Зеркала Числа: переводим 22 в троичную и семеричную системы счисления:
    • 2210 = 2113 → самая правая ненулевая цифра (отблеск) равна 1.
    • 2210 = 317 → самая правая ненулевая цифра (отблеск) равна 1.
  • Зеркала Факториала: вычисляем 22! = 1 124 000 727 777 607 680 000 и переводим в нужные системы счисления:
    • 22!10 = 1010211001211200221201000122112201210000000003 → отбрасываем нули справа, отблеск равен 1.
    • 22!10 = 56032405312153442455110007 → отбрасываем нули справа, отблеск равен 1.
  • Итог: все четыре зеркала показали одинаковый отблеск 1, поэтому число 22 является верным ключом.

Квадрат четырёх зеркал

Заблудившись в бесконечных лабиринтах Зазеркалья, Алиса отчаянно искала дорогу домой. Когда надежда уже почти покинула её, на ветке высокого дерева возникла знакомая широкая улыбка, а следом появился и сам Чеширский кот.

— Мур-мяу, ищешь выход домой? — спросил Кот, лениво потягиваясь. — Твоя дорога лежит в квадратный Тронный зал. В самом центре пола там скрыт портал выхода, а по четырём углам стоят волшебные зеркала. Они пропустят только того, кто назовёт правильное натуральное число-ключ.

Кот подробно объяснил Алисе дорогу в Тронный зал и прошептал на ухо заветное число. Попрощавшись, Алиса со всех ног бросилась по указанному пути. Но на крутом повороте она зацепилась за корень, упала и больно ударилась. Когда она добралась до Тронного зала, оказалось, что от удара заветное число вылетело у неё из головы! Алиса смогла вспомнить только то, сколько в этом числе было цифр в десятичной записи и какая цифра стояла на самом первом месте.

Зато она отлично запомнила правило четырёх зеркал: если встать точно в центре зала и произнести вслух любое натуральное число N, зеркала в углах сработают так:

  • Два зеркала Числа (Тройное и Семеричное) переведут число N в системы счисления с основаниями 3 и 7, оставив на поверхности только отблеск — самую правую ненулевую цифру получившейся записи.
  • Два зеркала Факториала (Тройное и Семеричное) сначала вычислят факториал этого числа (N! = 1 · 2 · … · N), затем переведут результат в системы счисления с основаниями 3 и 7 и тоже покажут лишь отблеск — самую правую ненулевую цифру этой записи.

Если все четыре отблеска по углам квадрата окажутся абсолютно одинаковыми, из каждого зеркала ударит луч света — лучи сойдутся точно в центре зала и откроют портал домой!

Помогите Алисе вернуться домой: найдите и выпишите все натуральные числа-ключи, которые подходят под её воспоминания и откроют портал в Тронном зале.

Формат входных данных

В первой строке вводится натуральное число K (1 ≤ K ≤ 5) — количество цифр в десятичной записи числа-ключа, которое вспомнила Алиса.
Во второй строке вводится цифра D (1 ≤ D ≤ 9) — первая (самая левая) цифра этого числа.

Формат выходных данных

Выведите в порядке возрастания в десятичной системе счисления все подходящие натуральные числа-ключи, которые откроют портал выхода (каждое число с новой строки). Если среди воспоминаний Алисы подходящих чисел нет, выведите -1.

Примеры входных и выходных данных

Входные данные Выходные данные Пояснение
1
1
1
Однозначное число, начинающееся на 1 — это только число 1.
Записи 13, 17 и записи 1! = 1 дают все четыре отблеска, равных 1.
2
1
-1
Двузначные числа, начинающиеся на 1 (от 10 до 19), не дают четырёх одинаковых отблесков.
2
2
22
23
Среди двузначных чисел на цифру 2 (от 20 до 29) лучи сойдутся в центре для двух чисел: 22 и 23 (разбор числа 22 приведён ниже).

Примеры вычисления отблесков и полный разбор

1. Как находить отблеск (примеры для отдельных чисел):

  • Возьмём число 12. В троичной системе 1210 = 1103. Отбрасываем ноль справа и получаем отблеск 1. В семеричной системе 1210 = 157 — последняя цифра ненулевая, поэтому отблеск равен 5.
  • Возьмём число 21. В троичной системе 2110 = 2103 (отблеск 1), в семеричной 2110 = 307 (отблеск 3).

2. Полный разбор подходящего числа N = 22:

  • Зеркала Числа: переводим 22 в троичную и семеричную системы счисления:
    • 2210 = 2113 → самая правая ненулевая цифра (отблеск) равна 1.
    • 2210 = 317 → самая правая ненулевая цифра (отблеск) равна 1.
  • Зеркала Факториала: вычисляем 22! = 1 124 000 727 777 607 680 000 и переводим в нужные системы счисления:
    • 22!10 = 1010211001211200221201000122112201210000000003 → отбрасываем нули справа, отблеск равен 1.
    • 22!10 = 56032405312153442455110007 → отбрасываем нули справа, отблеск равен 1.
  • Итог: во всех четырёх углах зала зажёгся одинаковый отблеск 1 — лучи сошлись в центре и открыли портал!

Четыре стрелки Тронного зала

Спеша на приём к Чёрной Королеве, Белый Кролик заглянул на Безумное чаепитие, но так увлёкся спором со Шляпником, что совершенно потерял счёт времени и сильно опоздал. Чтобы Королева не заметила опоздания (ведь она не прощает нарушений расписания!), Кролику нужно перевести назад Главные часы. Шляпник, который постоянно ремонтировал их, записал ключ доступа к хронометру Тронного зала.

Заветное натуральное число-код он аккуратно вписал в записную книжку Кролика. Пока Кролик убирал книжку в карман жилета, он случайно опрокинул чашку с горячим чаем прямо на страницу. Чернила расплылись, и Кролик смог разглядеть только количество цифр в десятичной записи числа-кода и самую первую его цифру.

К счастью, Кролик отлично помнил, как устроен защитный механизм Тронного зала: по четырём углам квадрата вокруг хронометра лежат четверо старинных карманных часов. Если встать у хронометра в центре и назвать вслух любое натуральное число N, часы в углах сработают так:

  • Двое часов Числа (Троичные и Пятеричные) переведут число N в системы счисления с основаниями 3 и 5, а их стрелки укажут только на отблеск — самую правую ненулевую цифру получившейся записи.
  • Двое часов Факториала (Троичные и Пятеричные) сначала вычислят факториал этого числа (N! = 1 · 2 · … · N), затем переведут результат в системы счисления с основаниями 3 и 5 и тоже укажут стрелками лишь на отблеск — самую правую ненулевую цифру этой записи.

Если все четыре отблеска на часах по углам квадрата окажутся абсолютно одинаковыми, раздастся тихий щелчок, и крышка хронометра в центре откроется!

Помогите Белому Кролику перевести время: найдите и выпишите все натуральные числа-коды, которые подходят под уцелевшие записи в книжке и откроют хронометр Тронного зала.

Формат входных данных

В первой строке вводится натуральное число K (1 ≤ K ≤ 5) — количество цифр в десятичной записи числа-кода.
Во второй строке вводится цифра D (1 ≤ D ≤ 9) — первая (самая левая) цифра этого числа.

Формат выходных данных

Выведите в порядке возрастания в десятичной системе счисления все подходящие натуральные числа-ключи, которые откроют хронометр (каждое число с новой строки). Если среди уцелевших записей подходящих чисел нет, выведите -1.

Примеры входных и выходных данных

Входные данные Выходные данные Пояснение
1
1
1
Однозначное число, начинающееся на 1 — это только число 1.
Записи 13, 15 и записи 1! = 1 дают все четыре отблеска, равных 1.
2
1
-1
Двузначные числа, начинающиеся на 1 (от 10 до 19), не дают четырёх одинаковых отблесков на часах.
2
2
25
Среди двузначных чисел на цифру 2 (от 20 до 29) хронометр открывает только число 25 (подробный разбор приведён ниже).

Примеры вычисления отблесков и полный разбор

1. Как находить отблеск (примеры для отдельных чисел):

  • Возьмём число 15. В троичной системе 1510 = 1203. Отбрасываем ноль справа и получаем отблеск 2. В пятеричной системе 1510 = 305 — отбрасываем ноль справа, отблеск равен 3.
  • Возьмём число 14. В троичной системе 1410 = 1123 (отблеск 2), в пятеричной 1410 = 245 (отблеск 4).

2. Полный разбор подходящего числа N = 25:

  • Часы Числа: переводим 25 в троичную и пятеричную системы счисления:
    • 2510 = 2213 → самая правая ненулевая цифра (отблеск) равна 1.
    • 2510 = 1005 → отбрасываем два нуля справа, самая правая ненулевая цифра (отблеск) равна 1.
  • Часы Факториала: вычисляем 25! = 15 511 210 043 330 985 984 000 000 и переводим в нужные системы счисления:
    • 25!10 = 210121101002021212012120220102010202221122100000000003 → отбрасываем нули справа, отблеск равен 1.
    • 25!10 = 10131100041411243434343332434010000005 → отбрасываем нули справа, отблеск равен 1.
  • Итог: на всех четырёх часах по углам квадрата стрелки указали на одинаковый отблеск 1 — хронометр Тронного зала открыт!

Шесть зеркал Зазеркалья

Заблудившись в бесконечных лабиринтах Зазеркалья, Алиса отчаянно искала дорогу домой. Когда надежда уже почти покинула её, на ветке высокого дерева возникла знакомая широкая улыбка, а следом появился и сам Чеширский кот.

— Мур-мяу, ищешь выход домой? — спросил Кот, лениво потягиваясь. — Твоя дорога лежит в Тронный зал. Там находится портал выхода, который сторожат шесть волшебных зеркал. Они пропустят только того, кто назовёт натуральное число, дающее правильный ключ-отблеск.

Кот подробно объяснил Алисе дорогу в Тронный зал и прошептал на ухо заветное число. Попрощавшись, Алиса со всех ног бросилась по указанному пути. Но на крутом повороте она зацепилась за корень, упала и больно ударилась. Когда она добралась до Тронного зала, оказалось, что от удара заветное число вылетело у неё из головы! Алиса смогла вспомнить только то, сколько в этом числе было цифр в десятичной записи, какая цифра стояла на самом первом месте и каким должен быть ключ-отблеск.

Зато Алиса отлично запомнила правило шести факториальных зеркал-стражей, окружавших портал:

  1. Зеркала стоят в строгом порядке и настроены на простые основания систем счисления: 3, 5, 7, 11, 13 и 17 соответственно.
  2. Когда Алиса произносит вслух любое натуральное число N, каждое зеркало сначала вычисляет его факториал (N! = 1 · 2 · … · N), затем переводит результат в систему счисления со своим основанием и оставляет на поверхности только отблеск — самую правую ненулевую цифру получившейся записи (для систем с основаниями больше 10 используются стандартные латинские буквы: A = 10, B = 11, C = 12, D = 13, E = 14, F = 15, G = 16).
  3. Шесть отблесков, прочитанных слева направо, складываются в шестизначный ключ-отблеск портала (например, 111111 или 246ACG).

Портал выхода откроется, если названное натуральное число сформирует на зеркалах заданный ключ-отблеск. Помогите Алисе вернуться домой: найдите наименьшее натуральное число N, которое подходит под её воспоминания о длине и первой цифре числа, а также даёт нужный ключ-отблеск на зеркалах.

Формат входных данных

  • В первой строке вводится количество цифр K в десятичной записи числа N и его первая цифра D (1 ≤ K ≤ 6, 1 ≤ D ≤ 9).
  • Во второй строке вводится шестисимвольный ключ-отблеск, который должны показать зеркала. Гарантируется, что хотя бы одно подходящее натуральное число N существует.

Формат выходных данных

  • Выведите одно число — наименьшее натуральное N, удовлетворяющее всем условиям.

Примеры

Входные данные Выходные данные
1 2
222222
2

Пояснение к первому примеру: Алиса помнит, что число состоит из 1 цифры и начинается на 2 — единственным кандидатом является N = 2. Вычислим 2! = 2. Во всех шести системах счисления (3, 5, 7, 11, 13, 17) число 2 записывается одинаково как 2. Самая правая ненулевая цифра в каждом зеркале равна 2, что даёт ключ-отблеск 222222.

Входные данные Выходные данные
1 4
2432B7
4

Пояснение ко второму примеру: Для N = 4 получаем 4! = 24. Переведём число 24 в системы счисления каждого из шести зеркал и найдём последнюю ненулевую цифру:

  • Основание 3: 2410 = 2203 → отблеск 2.
  • Основание 5: 2410 = 445 → отблеск 4.
  • Основание 7: 2410 = 337 → отблеск 3.
  • Основание 11: 2410 = 2211 → отблеск 2.
  • Основание 13: 2410 = 1B13 (1 · 13 + 11 = 24, цифра 11 обозначается буквой B) → отблеск B.
  • Основание 17: 2410 = 1717 (1 · 17 + 7 = 24) → отблеск 7.

Собрав отблески слева направо, получаем ключ-отблеск 2432B7.

Входные данные Выходные данные
2 1
246ACC
12

Пояснение к третьему примеру: Алиса ищет двузначное число, начинающееся с единицы (из диапазона от 10 до 19). При проверке чисел по возрастанию первым подходит N = 12. Число 12! = 479 001 600 после отбрасывания нулей на конце в соответствующих системах счисления заканчивается на цифры 2, 4, 6, A (10), C (12) и C (12), что формирует ключ-отблеск 246ACC.


Шесть зеркал Отдела тайн

Чтобы забрать важный артефакт из глубины Отдела тайн, Гермионе Грейнджер нужно было проникнуть в Зал пророчеств. Перед самой вылазкой профессор Дамблдор прошептал ей секретное натуральное число-пароль, которое отпирает входную дверь, и объяснил, как устроена древняя магическая защита.

Однако в тёмных коридорах Министерства магии Гермиона наткнулась на патруль Пожирателей смерти. Вспыхнула дуэль, и случайный рикошет заклинания забвения «Обливиэйт» вскользь задел её. Врагов удалось обезвредить, но когда Гермиона добежала до двери в Зал пророчеств, выяснилось, что заклятие частично стёрло её память! Она смогла вспомнить только то, сколько цифр было в десятичной записи заветного числа, какая цифра стояла на самом первом месте и каким должен быть магический ключ-отблеск.

К счастью, правила работы шести древних арифмантических зеркал, встроенных в дверь Зала пророчеств, Гермиона помнила наизусть:

  1. Зеркала расположены в строгом порядке слева направо и зачарованы на простые основания систем счисления: 3, 5, 7, 11, 13 и 17 соответственно.
  2. Когда волшебник произносит вслух любое натуральное число N, каждое зеркало сначала вычисляет его факториал (N! = 1 · 2 · … · N), затем переводит результат в систему счисления со своим основанием и оставляет на поверхности только отблеск — самую правую ненулевую цифру получившейся записи (для систем с основаниями больше 10 используются стандартные латинские руны-буквы: A = 10, B = 11, C = 12, D = 13, E = 14, F = 15, G = 16).
  3. Шесть отблесков, прочитанных слева направо, складываются в шестизначный ключ-отблеск двери (например, 111111 или 246ACG).

Тяжёлая дверь распахнётся, если названное натуральное число сформирует на зеркалах правильный ключ-отблеск. Помогите Гермионе открыть Зал пророчеств: найдите наименьшее натуральное число N, которое подходит под её воспоминания о длине и первой цифре числа, а также даёт нужный ключ-отблеск на зеркалах.

Формат входных данных

  • В первой строке вводится количество цифр K в десятичной записи числа N и его первая цифра D (1 ≤ K ≤ 6, 1 ≤ D ≤ 9).
  • Во второй строке вводится шестисимвольный ключ-отблеск, который должны показать зеркала. Гарантируется, что хотя бы одно подходящее натуральное число N существует.

Формат выходных данных

  • Выведите одно число — наименьшее натуральное N, удовлетворяющее всем условиям.

Примеры

Пример 1

Входные данные Выходные данные
1 2
222222
2

Пояснение: Гермиона помнит, что число состоит из 1 цифры и начинается на 2 — единственным кандидатом является N = 2. Вычислим 2! = 2. Переведём число 2 во все шесть систем счисления:

  • Основание 3: 210 = 23 → самая правая ненулевая цифра 2.
  • Основание 5: 210 = 25 → самая правая ненулевая цифра 2.
  • Основание 7: 210 = 27 → самая правая ненулевая цифра 2.
  • Основание 11: 210 = 211 → самая правая ненулевая цифра 2.
  • Основание 13: 210 = 213 → самая правая ненулевая цифра 2.
  • Основание 17: 210 = 217 → самая правая ненулевая цифра 2.

Собрав отблески слева направо, получаем ключ-отблеск 222222.

Пример 2

Входные данные Выходные данные
1 4
2432B7
4

Пояснение: Для N = 4 получаем 4! = 24. Переведём число 24 в системы счисления каждого из шести зеркал и найдём самую правую ненулевую цифру:

  • Основание 3: 2410 = 2203 → отблеск 2.
  • Основание 5: 2410 = 445 → отблеск 4.
  • Основание 7: 2410 = 337 → отблеск 3.
  • Основание 11: 2410 = 2211 → отблеск 2.
  • Основание 13: 2410 = 1B13 (так как 1 · 13 + 11 = 24, цифра 11 обозначается буквой B) → отблеск B.
  • Основание 17: 2410 = 1717 (так как 1 · 17 + 7 = 24) → отблеск 7.

Собрав отблески слева направо, получаем ключ-отблеск 2432B7.

Пример 3

Входные данные Выходные данные
2 1
246ACC
12

Пояснение: Гермиона проверяет двузначные числа, начинающиеся с единицы (из диапазона от 10 до 19). При проверке по возрастанию первым подходит N = 12. Вычислим 12! = 479 001 600 и переведём это число в системы счисления всех шести зеркал:

  • Основание 3: 479 001 60010 = 10201010222102000003 → отблеск 2 (последняя цифра перед пятью нулями).
  • Основание 5: 479 001 60010 = 14401110224005 → отблеск 4 (последняя цифра перед двумя нулями).
  • Основание 7: 479 001 60010 = 146043060607 → отблеск 6 (последняя цифра перед нулём).
  • Основание 11: 479 001 60010 = 226424AA011 → отблеск A (последняя цифра перед нулём).
  • Основание 13: 479 001 60010 = 783123CC13 → отблеск C.
  • Основание 17: 479 001 60010 = 12E61CGC17 → отблеск C.

Собрав отблески слева направо, получаем ключ-отблеск 246ACC.


Шесть кристаллов рождественского сейфа

В канун Рождества Рон Уизли решил подготовить для Гермионы Грейнджер особенный сюрприз и заранее заказал у Фреда и Джорджа редкий магический артефакт из их лавки. Чтобы Гермиона и никто из домашних не нашли подарок раньше времени, близнецы положили коробку в свой зачарованный сейф в «Норе» с шестью арифмантическими кристаллами и шепнули Рону на ухо секретное натуральное число — код сейфа.

Однако накануне праздника во время весёлой игры в снежки во дворе «Норы» в Рона угодил заколдованный снежок близнецов с лёгким эффектом забывчивости. Когда наступило рождественское утро и Рон подбежал к сейфу, чтобы забрать подарок для Гермионы, оказалось, что точный числовой код вылетело у него из головы! Рон смог вспомнить только то, сколько цифр было в десятичной записи этого числа, какая цифра стояла на самом первом месте и каким должен быть магический код-знак.

Зато правило работы шести арифмантических кристаллов, которое Фред и Джордж нацарапали прямо на крышке сейфа, было у него перед глазами:

  1. Кристаллы расположены в строгом порядке слева направо и зачарованы на простые основания систем счисления в порядке убывания: 17, 13, 11, 7, 5 и 3 соответственно.
  2. Когда волшебник произносит вслух любое натуральное число N, каждый кристалл сначала вычисляет его факториал (N! = 1 · 2 · … · N), затем переводит результат в систему счисления со своим основанием и высвечивает внутри грани только знак — самую правую ненулевую цифру получившейся записи (для систем с основаниями больше 10 используются стандартные латинские руны-буквы: A = 10, B = 11, C = 12, D = 13, E = 14, F = 15, G = 16).
  3. Шесть знаков, прочитанных слева направо, складываются в шестизначный код-знак замка (например, 111111 или GCA642).

Сейф откроется, если названное натуральное число сформирует на кристаллах правильный код-знак. Помогите Рону достать рождественский подарок для Гермионы: найдите наибольшее натуральное число N, которое подходит под его воспоминания о длине и первой цифре кода сейфа, а также даёт нужный код-знак на кристаллах.

Формат входных данных

  • В первой строке вводится количество цифр K в десятичной записи числа N и его первая цифра D (1 ≤ K ≤ 6, 1 ≤ D ≤ 9).
  • Во второй строке вводится шестисимвольный код-знак, который должны показать кристаллы. Гарантируется, что хотя бы одно подходящее натуральное число N существует.

Формат выходных данных

  • Выведите одно число — наибольшее натуральное N, удовлетворяющее всем условиям.

Примеры

Пример 1

Входные данные Выходные данные
1 2
222222
2

Пояснение: Рон помнит, что код состоит из 1 цифры и начинается на 2 — единственным кандидатом является N = 2. Вычислим 2! = 2. Переведём число 2 во все шесть систем счисления:

  • Основание 17: 210 = 217 → самая правая ненулевая цифра 2.
  • Основание 13: 210 = 213 → самая правая ненулевая цифра 2.
  • Основание 11: 210 = 211 → самая правая ненулевая цифра 2.
  • Основание 7: 210 = 27 → самая правая ненулевая цифра 2.
  • Основание 5: 210 = 25 → самая правая ненулевая цифра 2.
  • Основание 3: 210 = 23 → самая правая ненулевая цифра 2.

Собрав знаки слева направо, получаем код-знак 222222.

Пример 2

Входные данные Выходные данные
1 4
7B2342
4

Пояснение: Для N = 4 получаем 4! = 24. Переведём число 24 в системы счисления каждого из шести кристаллов (в порядке 17, 13, 11, 7, 5, 3) и найдём самую правую ненулевую цифру:

  • Основание 17: 2410 = 1717 (так как 1 · 17 + 7 = 24) → знак 7.
  • Основание 13: 2410 = 1B13 (так как 1 · 13 + 11 = 24, цифра 11 обозначается буквой B) → знак B.
  • Основание 11: 2410 = 2211 → знак 2.
  • Основание 7: 2410 = 337 → знак 3.
  • Основание 5: 2410 = 445 → знак 4.
  • Основание 3: 2410 = 2203 → знак 2.

Собрав знаки слева направо, получаем код-знак 7B2342.

Пример 3

Входные данные Выходные данные
2 1
GA9642
18

Пояснение: Рон проверяет двузначные числа, начинающиеся с единицы (из диапазона от 10 до 19), двигаясь по убыванию — от 19 вниз к 10:

  • Для N = 19 получается код-знак F86212, что не подходит.
  • Следующим проверяется N = 18. Вычислим 18! = 6 402 373 705 728 000 и переведём это число в системы счисления всех шести кристаллов:
    • Основание 17: 6 402 373 705 728 00010 = AGDD765B933G017 → знак G (последняя цифра перед нулём).
    • Основание 13: 6 402 373 705 728 00010 = 181A58332C7C2A013 → знак A (последняя цифра перед нулём).
    • Основание 11: 6 402 373 705 728 00010 = 1594AA249338859011 → знак 9 (последняя цифра перед нулём).
    • Основание 7: 6 402 373 705 728 00010 = 36343631436024066007 → знак 6 (последняя цифра перед двумя нулями).
    • Основание 5: 6 402 373 705 728 00010 = 232031324423221312440005 → знак 4 (последняя цифра перед тремя нулями).
    • Основание 3: 6 402 373 705 728 00010 = 10110021202202211211220222000000003 → знак 2 (последняя цифра перед восемью нулями).

Собрав знаки слева направо, получаем нужный код-знак GA9642. Так как мы идём по убыванию, N = 18 является наибольшим подходящим числом.

Печать