Олимпиадная информатика-2012

Задача « Сумма цифр»

Школьник Петя любит числа. Возьмёт какое-нибудь число и подсчитает сумму его цифр, а потом пытается найти наименьшее число с такой же суммой цифр. Помогите ему. Вам нужно для заданного целого числа N найти наименьшее натуральное число X, у которого сумма цифр равна N. Формат входного файла input.txt Входной файл содержит единственное целое число N (1< =N< =10⁵ ). Формат выходного файла output.txt Выходной файл содержит искомое натуральное число X.

var
 i, n: longint;
begin
 assign(input, 'input.txt');
	reset(input);
 assign(output, 'output.txt');
	rewrite(output);
 read(n);
 if n Mod 9 >
	 0 then write(n mod 9);
 for i : = 1 to n div 9 do
 write(9);
 close(input);
 close(output);
end.

close
 

Разбор задачи №1 "Сумма цифр"

Чтобы при фиксированной сумме цифр, само число было минимальным, нужно, чтобы количество цифр было как можно меньше. Это достигается, если значение каждой цифры максимально, т.е . "9". Поделив число на 9, найдём, сколько раз в числе встречается девятка.

Если при этом получился остаток, записываем его перед девятками.