07/04/2025 04:06:26

Рабочее место участника

Задачи

1221. Взлом кода

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (3)

Для входа в секретную лабораторию необходимо набрать код из

$n$ цифр. Путем анализа внутренней структуры замка было установлено, что для введенного кода вычисляется следующая хэш-функция:

$h_0=0$

$h_i=(h_{i-1}*a+c_i)\ mod\ b$ для

$i=1…n$

где

$c_i$ – цифры вводимого кода от 0 до 9

Если значение

$h_n$ совпадает с заданным при настройке замка значением

$g$ , то замок открывается. Удалось выяснить значения

$a$ ,

$b$ и

$g$ . Необходимо определить код, который откроет замок.

Первая строка ввода содержит четыре целых числа – длина кода

$n$ (

$2\ ≤\ n\ ≤\ 12$ ) и значения

$a$ ,

$b$ ,

$g$ (

$10\ ≤\ a,\ b\ ≤\ 10^15$ ,

$0\ ≤\ g\ <\ b$ ). Хотя бы один код, соответствующий входным данным, существует.

В первой строке вывести последовательность из

$n$ цифр – код замка. Если существует несколько вариантов решения, нужно вывести один (любой) из них.

Пример ввода

3 11 1000 146

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

21/03/2009	Южно-Уральский открытый командный чемпионат по программированию (E)
10/07/2013	Лето 2013-7 (C)
05/05/2015	Занятие 24 (C)
02/12/2015	Занятие по теме "Разбиение на подзадачи, динамическое программирование" (A)