Задача 5 Теорияцифр Имя входного файла: digit

Задача 5 Теорияцифр Имя входного файла: digit.in Имя выходного файла: digit.out Максимальное время работы на одном тесте: 1 секунда Максимальный объем используемой памяти: 256 мегабайтЮный информатик стал исследовать, как изменяются суммы цифр натуральных чисел при умножении и делении на разные однозначные числа. Однажды он задался вопросом, можно ли восстановить число A, если нам известна сумма его цифр, а также сумма цифр числа D×A, где D — заданное однозначное число. Довольно быстро он установил, что для восстановления числа А этой информации недостаточно. Так, например, у чисел 9 и 45 одинаковые суммы цифр. Если же их умножить на 5, то получим числа 45 и 225, которые тоже имеют одинаковые суммы цифр. Тогда юный информатик стал искать ответ на поставленный вопрос при условии, что нам известно K — количество десятичных знаков в числе A. К сожалению, и тут его ждало разочарование. У некоторых чисел, имеющих одинаковое количество цифр и одинаковые суммы цифр, после умножения на один и тот же множитель эти суммы опять оказываются одинаковыми. Такими числами, например, являются 42 и 51 при D=3. И тогда юный информатик поставил перед собой такую задачу: найти наименьшее K‑значное натуральное число A в десятичной системе счисления, которое имеет сумму цифр, равную S, а число D×A имеет сумму цифр, равную P. Требуется написать программу, решающую поставленную задачу. Формат входных данныхВо входном файле заданы четыре натуральных числа K, S, P, D (1 ≤ K ≤ 100, 1 ≤ S ≤ 9K, 1 ≤ P ≤ 9 (K+1) , 1 ≤ D ≤ 9). Формат выходных данныхВыведите в выходной файл число A, если оно существует, или –1, в противном случае. Число A не может начинаться с нуля. Примерыdigit.indigit.out 2 9 9 5 182 8 10 3 -1