Вот из книги| Код |
Порублев, И.Н., Ставровский, А.Б.
Алгоритмы и программы. Решение олимпиадных задач.
- М. Ж ООО "И.Д. Вильямс", 2007.-480 с.:ил.
ISBN 978-5-8459-1244-2(рус.) |
| Код | {
Задача 10.3
В гооде Глупове общепринята p-ричная система счисления (вместо
десятичной), а номера троллейбусных билетов состоят из 2k разрядов
(каждый разряд - одна p-ричная цифра). Билет считается счастливым,
если сумма первых k разрядов равна сумме последних k разрядов.
Вход. Значения p и k.
Выход. Количество счастливых билетов.
Примеры.
Вход: 2 2; выход: 6.
Вход: 10 3; выход: 55252.
}
PROGRAM L_10_01;
VAR
N : array [0..1] of array [0..5000] of QWord;
N_tot : QWord;
s,
s_,
k,
k_,
p : Integer;
BEGIN
{$ifndef Debug}
Write('Enter p, k > ');
ReadLn(p, k);
{$else}
p:=10;
k:=3;
{$endif}
for s_:=0 to p-1 do
N[0][s_]:=1;
for k_:=2 to k do begin
for s:=0 to k_*(p-1) do begin
N[1][s]:=0;
for s_:=0 to p-1 do
if (s-s_>=0) AND (s-s_<=(k_-1)*(p-1))
then N[1][s]:=N[1][s]+N[0][s-s_];
end;
N[0]:=N[1];
end;
N_tot:=0;
for s:=0 to k*(p-1) do
N_tot:=N_tot+sqr(N[0][s]);
WriteLn(N_tot);
END.
|
Идея в следующем.
Найдём количества чисел разрядностью k, суммы которых равны 0, 1, 2, ... k*(p-1). Очевидно, что количество комбинаций для суммы цифр равной, предположим 5, равна квдрату количества чисел, чья сумма цифр равна 5. Суммируя квадраты получим итоговое количество "счастливых" билетиков.
Для случая 2k=6 и p=10 упрощённый вариант решения (без описания переменных - только алгоритм)| Код |
var
a: array [0..27] of integer;
begin
{инициализация массива нулями}
for i:=0 to 27 do
a[i]:=0;
{в итоге в a[i] будет количество чисел, чья сумма равна i}
for i1:=0 to 9 do
for i2:=0 to 9 do
for i3:=0 to 9 do
inc(a[i1+i2+i3]);
{подсчёт "счастливых" билетиков}
s:=0;
for i:=0 to 27 do
s:=s+a[i]*a[i];
WriteLn(s);
end.
|
|
