Текущ брой на Списание ИнфоМан
 


Зимни Математически Състезания 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