Есенен турнир 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;
}
Автор: Слави Маринов
обратно към брой 27
|