Решите задачу ** PascalABC

0 голосов
39 просмотров

Решите задачу на PascalABC


image

Информатика | 39 просмотров
Дан 1 ответ
0 голосов
Правильный ответ
1. Оценка вычислительных ресурсов
Прежде всего, наложим ограничение на величину k.
Известно, что 1 \leq n \leq 10^{15} и понятно, что номинал пшиллинга уровня k не может превышать значения n. Известна и рекуррентная формула для подсчета номинала пшиллинга любого уровня.
P_k=10\times k\times P_{k-1}, \ P_0=1, \ k\in \mathbb N \ ; \\ P_k=1\times 10\times 2\times 10\times 3\times 10\times...\times k\times 10=k!\times 10^k \ ; \\ k!\times 10^k \leq 10^{15} \ ; k! \leq 10^{15-k}
Решить такое уравнение мы не сможем, поэтому поступим следующим образом.
Поскольку 1!=1, очевидно, что значения k, большие 15, смысла не имеют.
В то же время известно, что целочисленный тип, который обеспечивает в PascalABC.Net максимальную разрядность, это int64. Максимальное значение, которое может принимать переменная этого типа, равно 9223372036854775807, т.е. примерно 9.2\cdot 10^{18}, так что тут все нормально. Если же мы будем использовать тип 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


(142k баллов)
0

Огромнейшее вам спасибо