025 Munte

[VladS]

Poti folosi int64 cu incredere. De fapt scrie si in enunt.

[•wefgef]

nu stiu de ce dar tot iau WA pe 8 teste...

ptr:

Cod:

25 100 20
3
8
9
5
3
3
2
4
6
3
8
9
5
3
3
2
4
6
3
8

va da 75500211146359 ?

[VladS]

Da, iti da bine. Vezi poate gresesti la afisare sau chestii din astea marunte.

[•pocaitu]

la mine am calculat pe foaie pt exemplu 4 si mi-au  iesit mult mai multe solutii :vreo 15 . oare ce nu am luat in calcul?

[•pocaitu]

de fapt sunt un prost  n-am citit prea bine problema . am facut pentru cazul in care punctele obiectivele sunt vizitate in orice ordine 

[•nash]

ok... probabil ca sunt prea obosit dar chiar si asa devine enervant... la problema asta am facut o dinamca la care am ajuns la urmatoarea recurenta :

Cod:

#include <stdio.h>

#define NRPUNCT 64
#define DIST 128
#define HMAX 64
#define T true
#define F false
#define SAFE(i) ((i)>=(0)?(i):(63))

int h,n,p,k;
int punct[NRPUNCT];
int sol[DIST][HMAX][2][NRPUNCT];


int main() {
	
	freopen("munte.in","r",stdin);
	freopen("munte.out","w",stdout);
	
	scanf("%d %d %d",&h,&n,&k);
	
	for(int i = 1 ; i <= k ; i++)
		scanf("%d",&punct[i]);
	
	sol[n][0][F][k+1] = 1;
	
	for(int i = n - 1 ; i >= 1 ; i--)
		for(int j = 0 ; j <= h ; j++)
			for(int p = k ; p>= 1 ; p--) {
				sol[i][j][T][p] = 
								sol[i+1][j+1][T][p] + 
								sol[i+1][j  ][T][p] + 
								sol[i+1][SAFE(j-1)][T][p] +
				
								sol[i+1][j+1][F][p] * (h==j) +
								sol[i+1][j  ][F][p] * (h==j) +
								sol[i+1][SAFE(j-1)][F][p] * (h==j) +
				
								sol[i+1][SAFE(j-1)][T][p-1] * (punct[p] == j) +
								sol[i+1][j  ][T][p-1] * (punct[p] == j) +
								sol[i+1][j+1][T][p-1] * (punct[p] == j) +
				
								sol[i+1][SAFE(j-1)][F][p-1] * (punct[p] == j) * (h == j) +
								sol[i+1][j  ][F][p-1] * (punct[p] == j) * (h == j) +
								sol[i+1][j+1][F][p-1] * (punct[p] == j) * (h == j);
				
				sol[i][j][F][p] =
								sol[i+1][SAFE(j-1)][F][p] +
								sol[i+1][j  ][F][p] +
								sol[i+1][j+1][F][p] +
								
								sol[i+1][j+1][F][p-1] * (punct[p] == j) +
								sol[i+1][j  ][F][p-1] * (punct[p] == j) +
								sol[i+1][SAFE(j-1)][F][p-1] * (punct[p] == j);
			}
	printf("%d",sol[1][0][T][1]);
	
	return 0;
}

totusi nu imi da rezultatul dorit... nicio data si nu inteleg de ce... si nu cred ca am pierdut vre-un caz (stiu ca sparg cache-ul... la modul in care am pus acolo niste indici... dar ideea este ca nu da rezultat corect si nu ca iese din timp )

[•astronomy]

Trebuie sa gandesti din nou recurenta si sa obtii o recurenta mult mai simplificata decat ce ai scris tu acolo. Cand ai 15 cazuri e foarte usor sa gresesti.

[•nash]

Chiar 18

Nu imi vine in minte cum as putea sa pun in recurenta mai simplu asa ca o sa incerc sa ma explic ca sa fie mai clar ce fac acolo:

sol[ i ][ j ][ T ][ P ] -> inseamna numarul de moduri in care pot sa ajung de la pozitia "i" la pozitia "n" ( lungimea pe verticala a muntelui este "n" ) aflandu-ma la inaltimea "j" si daca am reusit sa trec prin inaltimea maxima ( T de la true ) trecand prin punctul special "p" .

sol[ i ][ j ][ F ][ P ] -> aproape la fel doar ca in loc de T avem F adica "inca nu am reusit sa trecem prin punctul maxim al muntelui.


si acum cum se formeaza este exact ca in recurenta care am precizat-o
pentru  sol[ i ][ j ][ T ][ P ] avem posibilitatile :

- sa venim din pozitia "i+1"(din fata) cu inaltimile "j+1" ,"j" sau "j-1" dintr-o pozitia care face parte dintru-un sir care a trecut prin punctul maxim ( deci cu  "T" ) si care a trecut prin punctul obligatoriu "p" ( adica punct[p] )  :  sol[i+1][j+1][T][p]  sol[i+1][j  ][T][p]  sol[i+1][SAFE(j-1)][T][p]

- sa venimla fel ca mai innainte doar ca dintr-o pozitia care inca nu a trecut prin innaltimea maxima ( deci "F" (false) in loc de T) si care la pozitia actuala se va afla la inatimea maxima adica "j = h" : sol[i+1][j+1][F][p] * (h==j) sol[i+1][j  ][F][p] * (h==j) sol[i+1][SAFE(j-1)][F][p] * (h==j)

- sa venim ca in primul caz doar ca sa nu fi trecut prin punctul "p" inca sol[i+1][SAFE(j-1)][T][p-1] * (punct[p] == j)
   sol[i+1][j  ][T][p-1] * (punct[p] == j)     sol[i+1][j+1][T][p-1] * (punct[p] == j)

-sa venim la fel ca in cazul 2 doar ca inca sa nu fi atins punctul de "h" maxim : sol[i+1][SAFE(j-1)][F][p-1] * (punct[p] == j) * (h == j)     sol[i+1][j  ][F][p-1] * (punct[p] == j) * (h == j)     sol[i+1][j+1][F][p-1] * (punct[p] == j) * (h == j);



pentru cazul : sol[ i ][ j ][ F ][ P ] se merge pe acesi idee doar ca singurul mod in care se poate ajunge intr-o stare care inca nu a trecut prin punctul maxim deci cu  "F" este sa vina tot din stari care inca nu au trecut prin punctul maxim.


Am facut o modificare : peste tot unde este"p-1" trebuia "p+1"... poti sa ajungi la punctul "p" din "p+1" ca mergi invers de la "n" la "1" cu "i-ul" rezultatul este acelas ( adica tot nu imi da nimic corect )

[•astronomy]

Poate te ajuta cum am retinut eu starile la problema asta: A(i,j,k,t) = numarul de posibilitati sa ajung la inaltimea i, la distanta j pe orizontala, trecand prin primele k puncte speciale; t = 1 sau 0 daca am atins pana aici intaltimea N sau nu. Solutia se va afla in A(1, D, K, 1).

[•nash]

Avem fix aceasi recurenta si acelas mod de a retine... doar ordinea difera si tu pleci de la 1 la n eu invers . O diferenta este faptul ca eu am solutia in punctul in care inaltimea este "0" .

"heorghe avand toate aceste informatii, N (inaltimea maxima a muntelui, presupunand ca muntele incepe la nivelul 0 si se termina la nivelul 0)......."

[•Florian]

Tii cont ca nu poti sa atingi nivelul 0 decat la inceput si sfarsit?

[•nash]

Nu, nu tineam cont... merci:)

[•SpiderMan]

Este gresit la specificatii . In loc de 1 <= N <= 50, trebuie 1 <= N <= 100 .

[•pauldb]

Toate testele respecta restrictiile specificate in enunt.

Citesti tu datele de intrare in alta ordine. Verifica-te si tu de doua ori inainte sa postezi. In atata timp, sigur ar fi sesizat cineva mai repede daca era vreo greseala.

[•SpiderMan]

Am pus codul asta si am primit SIGABRT. L-am scos si am primit KBS 11 ( fiindca aveam matricea doar 50 ) .

Cod:

assert ( 1 <= N && N <= 50 ) ;

[LE] Scuze, am avut o eroare in cod, nu stiu de ce si l-a schimbat pe N cu D .

[•mrares]

Pentru 3 8 4 si punctele 2, 2, 3, 1 o parcurgere de genul
- urc 2 bete in sus, 2 bete la dreapta, un bat in sus si 3 in jos

e corecta?

[•pauldb]

Da.

[•mitza23]

Am incercat cu numerele lui Catalan si am obtinut 20 de puncte, sfaturi?