1. Оценка вычислительных ресурсов
Прежде всего, наложим ограничение на величину k.
Известно, что
и понятно, что номинал пшиллинга уровня k не может превышать значения n. Известна и рекуррентная формула для подсчета номинала пшиллинга любого уровня.
Решить такое уравнение мы не сможем, поэтому поступим следующим образом.
Поскольку 1!=1, очевидно, что значения k, большие 15, смысла не имеют.
В то же время известно, что целочисленный тип, который обеспечивает в PascalABC.Net максимальную разрядность, это int64. Максимальное значение, которое может принимать переменная этого типа, равно 9223372036854775807, т.е. примерно
, так что тут все нормально. Если же мы будем использовать тип longint, то придется ограничиться максимальным значением n=2147483647, что нарушает условия задачи.
Номиналы пшиллингов всех уровней мы будем вычислять и заносить в массив Psh[0..15]. Мы будем оценивать выполнение записанного выше неравенства, что позволит вовремя остановить процесс заполнения массива номиналов и не вычислять ненужных коэффициентов.
2. Алгоритм
Задачу можно решать, например, методом динамического программирования, и этот метод тут подходит в максимальной степени. Но его реализация требует предварительной теоретической подготовки (например, ссылки на известную "Задачу о размене"), а описание алгоритма будет достаточно громоздким.
С учетом написанного выше, было принято решение использовать простой и понятный "жадный алгоритм", а "расплатой" будет вероятность не всегда получать самое оптимальное решение.
Текст программы (PascalABC.Net)
var
Psh:array[0..15] of int64;
n,f,d:int64;
i,km:integer;
begin
Psh[0]:=1;
i:=1; d:=100000*sqr(100000); f:=1;
repeat
f:=f*i; d:=d div 10;
Psh[i]:=10*i*Psh[i-1];
Inc(i)
until f>d;
km:=i-1;
Read(n);
i:=km;
while n>0 do begin
d:=n div Psh[i];
if d>0 then Writeln(d,' ',i);
n:=n mod Psh[i];
Dec(i)
end
end.
Тестовое решениe:
7777
1 3
8 2
17 1
7 0
6030
1 3
3 1
324533234
27 5
2 4
8 3
26 2
3 1
4 0