Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Взлом хеш-функции

(Время: 1 сек. Память: 16 Мб Сложность: 35%)

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

Пусть дана строка S = s1s2 ... sl, состоящая из цифр от 0 до 9. Тогда значение полиномиальной хеш-функции p(S, x, m) вычисляется следующим образом:

Хеш-функция

(a mod b обозначает остаток от деления числа a на число b). Например, пусть S = 0123, тогда p(S, 2, 5) = (0 ∙ 1 + 1 ∙ 2 + 2 ∙ 4 + 3 ∙ 8) mod 5 = 4.

Одним из способов применения хеш-функций является хранение паролей. Часто бывает так, что пароли приходится хранить в незащищенной таблице базы данных, поэтому вместо них хранят хеш-функции от них. При проверке пароля вычисляется хеш-функция от введенной строки и сравнивается со значением, хранящимся в таблице.

Ваша задача состоит в том, чтобы по заданным числам x, m, L и v найти строку S из цифр от 0 до 9 длины L, значение полиномиальной хеш-функции p(S, x, m) равно v.

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

Входной файл INPUT.TXT содержит четыре целых числа: x (x – простое число, 5 ≤ x ≤ 100), m (m является степенью двойки, 1 ≤ m ≤ 256), L (10 ≤ L ≤ 100) и v (0 ≤ v ≤ m-1).

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

В выходной файл OUTPUT.TXT выведите искомую строку или NO SOLUTION, если такой строки не существует. Если решений несколько, выведите любое.

Пример

INPUT.TXTOUTPUT.TXT
15 16 10 90422207956

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ