Брой 26 на Списание Инфоман
 


Есенен турнир 2004, Задача А3. ТРАЕКТОРИЯ

Уловието на задачата може да прочетете тук.

Решение

Решението на задачата се извършва на два етапа – кодиране/декодиране на траектории и след това намиране на броя на всички траектории, които във всяка координата са не по-ниско от дадената. Първо ще кодираме дадената траектория с цяло число, което показва реда и в сортираната лексокографски наредба на траекториите, след което ще декодираме следващата по номер траектория.

Кодирането на траектории ще направим по следния начин. Нека имаме функция, която по даден модел от нули и единици до дадена позиция ни връща колко маршрута можем да конструрираме оттук нататък. Например, ако досега сме построили 1 0 и N = 6, то на останалите 4 позиции можем да поставим или 1 0 1 0, или 1 1 0 0, тоест нашата функция ще върне резултат 2. Нещо повече, можем да изискаме от функцията по дадена височина H в точката T да върне колко коректни траектории могат да се построят. Наистина, понеже за това колко варианта следват не е никак съществено как сме стигнали до точката T на височина H, стига да е било коректно.За нашия случай, в точката T = 2 сме били на височина H = 1, тогава от точка3 нататъкследват 2 наредби, т.е. V[2][1] = 2. Височината в дадена точка можем лесно да намерим като от броя на изкачванията извадим броя на слизанията. Използвайки тази функция, лесно можем да кодираме и декодираме траектории. Тъй като една траектория е последователност от 0 и 1, една траектория предхожда друга (според условието), ако до дадена позиция двете са еднакви, а след това в едната имаме 0, а в другата 1. Оттук следва, че ако на дадена позиция T сме на височина H имаме 1 във входа, тоест ще се изкачваме, тогава всички траектории, които до позиция T съвпадат с дадената, а на позиция T имат 0 ще предхождат нашата. Използвайки горепосочената функция, това ще е точно броят V[T+1][H-1]. Когато направим това за всички единици от входа и натрупваме тази сума, накрая ще получим точно колко маршрута предхождат дадения, а прибавяйки към това число 1 ще получи истинския му номер (ако един маршрут бива предхождан от 0 други, то той е на първо място). Декодирането се извршва по схема, аналогична с тази от кодирането. Нека да декодираме числото X, т.е. да получим траекторията, която е предхождана от X-1 траектории в сортираната последователност. Започваме от първия момент да “симулираме” движението и проверяваме, дали ако слезем надолу вариантите (които пресмятаме, използвайки функцията, която описахме по-горе), които следват от това, ще надвишат X. В случай, че това е изпълнено, на поредната позиция слагаме числото 0. Ако ли не, тогава намаляваме X с броя на така пресметнатите траектории, поставяме 1 на съответната позиция и продължаваме нататък. По този начин в крайна сметка ще получим последователност от 0 и 1, която е на позиция X в сортираната последователност. За да завършим първия етап от решението на задачата е достатъчно да формулираме как се получават стойностите V[T][H]. Тъй като от тази позиция можем или да слезем надолу, или да се качим, то получаваме, че:

V[T][H] = V[T+1][H+1] + V[T+1][H-1]

По този начин лесно може да получим стойностите на функцията за всяко T и H. Важно е да отбележим, че при T>N, при H < 0, както и при T = N,H ≠ 0 стойността на функцията е 0, а при T=N и H=0 стойността на функцията е 1.

Втората част на задачата може много лесно да се реши като се модифицира начина на изчисляване на функцията като променим само още едно от ограничителните условия, а именно V[T][H] = 0 при H < D[T]. Тук с D[T] е отбелязано на каква височина се намира точката при движението си по траекторията, описана във входа, в момент на движение T. Тогава V[0][0] ще ни даде точно колко траектории съществуват, които в никой момент не слизат под дадената.

Операциите, които описаният алгоритъм извършва, имат сложност O(N2).

Примерна реализация:

#include <stdio.h>

#define UNDEF -1

__int64 m[64][64]; // w tozi masiw shte si pazim stoinostite na 
// rekursiata, za da ne iz4isliawame edna i sy6ta situacia 2 pyti
int N;
int d[64]; // wisochinite na dadenata wyw whoda traektoria
int is_limited=0; // shte ogranichawame li rekursiata?

__int64 var(int place,int diff) {
// kolko traektorii mojem da konstruirame, takiwa che na koordinata
// place sa na wiso4ina diff, i sled towa mojem da se dwijim wsiakak,
// stiga da ne narushwamae postawenite uslowia?

	if (is_limited) { // ako shte ogranichawame dinami4noto,
	// iskame da ne slizame pod dadenata ni traektoria. ako sme slezli =>
	// imame 0 takiwa traektorii
		if (diff<d[place])
			return 0;
	}
	if (diff<0) // ako sme slezli pod osta Ox
		return 0;
	if (place==N) { // ako sme na pozicia N, triabwa da sme na wisochina 0
		if (diff)
			return 0;
		return 1;
	}
	if (m[place][diff]!=UNDEF) // izchislawali li sme weche tazi stoinost?
		return m[place][diff];
	return m[place][diff] = (var(place+1,diff+1) + var(place+1,diff-1));
}

void init() { //obiaviava vsichki wyzmojni situacii za neposeshtawani
int i,j;
	for (i=0;i<64;i++)
		for (j=0;j<64;j++)
			m[i][j] = UNDEF;

}

int main () {
int diff = 0,i,t;
__int64 code = 1;
__int64 all;
__int64 v_0;
__int64 bcode;


	scanf("%d",&N);
	init(); // inicializirame masiwa za dinami4noto s UNDEF
	all = var(0,0); // kolko sa obshto wsi4ki traektorii, bez ogranichenia
	
	// chetem whoda i codirame tekushtata traektoria
	for (i=0;i<N;i++) {
		d[i] = diff; // zapazwame wisochinata na tekushtata traektoria
		// w tochkata i
		scanf("%d",&t);
		if (t) { // ako e 1 => wsichki traektorii s 0 na tazi pozicia
			// predhojdat dadenata
			code+=var(i+1,diff-1);
			diff++;
		} else
			diff--;		
	}
	bcode = code;
	code++; // iskame da dekodirame sledwashtata traketoria
	diff = 1;
	printf("1"); // zadyljitelno zapo4wa s 1	
	
	for (i=1;i<N-1;i++) {
		v_0 = var(i+1,diff-1);
		if (v_0<code) { // ako traektoriite s 0 na tazi pozicia
			// sa po-malko ot nashia kod, 
			// togawa na tazi pozicia imame 1
			code-=v_0;
			printf(" 1");
			diff++;
		} else { // inache slagame 0
			printf(" 0");
			diff--;
		}
	}

	is_limited = 1; // weche shte iskame traektoriite, 
	// koito broim da sa samo takiwa, che da ne 
	// slizat pod dadenata ni traektoria
	init(); // shte puskame dinami4noto nanowo =>
	// inicializirame masiwa, koito pomni stoinostite ot dinami4noto
	printf(" 0\n%I64d\n",var(0,0));
	return 0;
}
	

Автор: Слави Маринов


обратно към брой 26