Задача Интересное число

Имя входного файла input.txt

Имя выходного файла output.txt

Максимальное время работы на одном тесте: 2 секунды

Для заданного числа n найдите наименьшее положительное целое число с суммой цифр n, которое делится на n.

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

Во входном файле содержатся целое число n (1 ≤ n ≤ 1000).

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

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

Пример

input.txt	output.txt

Код программы:

program Number;

const max = 1 shl 12;

inf = 1 shl 30;

y = 10;

var

a: array[0..max - 1, 0..max] of boolean;

b, c: array[0..max - 1, 0..max] of integer;

red: array[0..max - 1, 0..y - 1] of integer;

qx, qy, s: array[0..max * (max + 1) - 1] of integer;

front, rear, n, u, v, k, i, j: integer;

begin

reset(input, 'input.txt');

rewrite(output, 'output.txt');

read(n);

for i:= 0 to n - 1 do

for j:= 0 to y - 1 do

red[i][j]:= (i * y + j) mod n;

for i:= 0 to n - 1 do

for j:= 0 to n do

a[i][j]:= false;

a[0][0 ]:= true;

qx[0]:= 0;

qy[0]:= 0;

front:= 0;

rear:= 1;

while front < rear do

begin

i:= qx[front];

j:= qy[front];

inc(front);

if (i = 0) and (j = n) then

begin

i:= 0;

j:= n;

k:= 0;

while j > 0 do

begin

u:= b[i][j];

v:= c[i][j];

s[k]:= j -v;

inc(k);

i:= u;

j:= v;

end;

for i:= k -1 downto 0 do write(s[i]);

writeln;

exit

end;

for k:= 0 to y - 1 do

begin

u:= red[i][k];

v:= j + k;

if v > n then break;

if not a[u][v] then

begin

a[u][v]:= true;

b[u][v]:= i;

c[u][v]:= j;

qx[rear]:= u;

qy[rear]:= v;

inc(rear);

end;

end;

end;

assert(false);

end.