Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

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

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

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483



Решетка радиатора Toyota. eBay - тойота запчасти. Кузовные запчасти, оптика DAF.