Зимни Математически Състезания 2005, Задача B1. ПОХОД
Условието на задачата може да прочетете
тук.
Решение
От
условието на задачата става ясно, че всеки турист е с различна първоначална скорост, т.е. може
да съпоставим числата от 1 до N на туристите, в зависимост
от тяхната скорост. По този начин можем да разглеждаме туристите като една
пермутация на числата от 1 до N.
Сега, вече свели условието до конкретни
информатически данни, можем да "пристъпим" към решението на задачата.
Ще използваме метода на динамичното оптимиране. Нека F(N, P) ни връща броя на
пермутациите с N елемента, в които се образуват P на брой редици от дадения вид
(по модул 1 020 847). Важно е да се забележи, особено ако не сте срещали такива задачи до сега, че не е никаква пречка
да си пазим просто остатъка от делението с това число, всичко идва от елементарното
равенство a (mod p) + b (mod p) = (a + b) (mod p).
Тривиалният случай е F(1, 1) = 1, а именно,
пермутациите на 1 елемент, с 1 редица са точно 1 на брой. От тук трябва да
пристъпим към общия случай F(N, P), като вече сме намерили решенията за всички
F(x, y), за които x < N i y <= P. Във
този случай имаме пермутация с N елемента. Ще направим връзката с пермутация с N-1
елемента. Забележете, че ако пред който и да е член на пермутацията с N-1
елемента поставим числото N (N-тия член на новата пермутация), ние НЯМА да
получим нова редица от описаните, тъй като това е случая, в който N-тият турист
е по-бърз от всички останали и той винаги ще се "присъединява" към
вече образувана редица. От тук имаме N-1 позиции, в които отговорът е F(N-1,P)
-> (N-1)*F(N-1,P), т.е. за всяка една пермутация с N-1 елемента и P на брой
редици можем да поставим N пред всеки един член на тази пермутация, без да променяме
броя на редиците от описания вид.
Другият случай е когато поставим N след всички
други N-1 члена и тогава ще образуваме нова редица, тъй като N-тият турист е
най-бърз и той няма да бъде настигнат от нито един друг. Така може да го поставим
на една позиция (последно място) на всичките пермутации с N-1 елемента и
P-1 редици -> F(N-1,P-1). И така, получаваме рекурентната зависимост в динамичното
оптимиране:
F(N, P) =
((N-1) * F(N-1,P) + F(N-1,P-1)) mod 1 020 847
Забележете, че трябва да намерим решенията само под и
на главния диагонал, т.е. за стойности на i и j, за които j <= i, тъй
като не може да имаме повече редици отколкото елемента. Така със сложност O(N^2) попълваме
таблицата и отговорът на задачата стои във F[N, P].
В приложения код на Паскал аз ползвам матрицата F за
стойностите на динамичното оптимиране.
Примерна реализация:
program march;
const
MAXN = 2000;
MODULO = 1020847;
var
F : Array [0 .. MAXN, 0 .. MAXN] of LongInt;
N, P, i, j, m : LongInt;
function max(a, b: LongInt): LongInt;
begin
if (a > b) then max := a
else max := b;
end;
begin
for i := 0 to MAXN do{ inicializirane na tablicata na DP }
for j := 0 to MAXN do
F[i, j] := 0;
readln(N, P); { input }
F[1, 1] := 1; { trivialen sluchai na DP }
for i := 2 to N do begin { DP }
m := max(i, P);
for j := 1 to m do
F[i, j] := ((i - 1) * F[i - 1, j] +
F[i - 1, j - 1])
mod MODULO;
end;
writeln(F[N, P]); { output }
end.
Автор: Момчил Иванов
обратно към брой 27
|