400 Taxi

[•danielp]

Aici puteţi discuta despre problema Taxi.

[•Mishu91]

Distanta dintre doua puncte este distanta geometrica (sqrt((x1-x2)² + (y1-y2)²) sau distanta Manhattan? Pentru ca la inceput scrie ca strazile impart orasul sub forma unei matrice, iar oamenii cred ca merg pe strazi. 

[•toni2007]

E distanta Manhattan.

[•Mishu91]

Mersi

Cat tre sa dea pt testul

Cod:

1
16 15 1 4 3 6

?

[•gabitzish1]

91

[•Mishu91]

Asa imi da si mie, dar nu prea inteleg de ce iau incorect pe 9 teste 

[•Detrol2k]

Imi poate da cineva o idee de rezolvare? 

[•repp4radu]

Gasesti aici solutiile oficiale.

[•Detrol2k]

Gasesti aici solutiile oficiale.

Multumesc!

L.E: Si eu iau 9 WA. E vreun truc la mijloc?  . Imi da bine pe exemplul din enunt si cel postat aici si pe altele date de mine.

[•repp4radu]

vezi cat iti da pe
1
6 6 1 1 2 3

R: 0

Probabil asta gresesti.

[•Detrol2k]

vezi cat iti da pe
1
6 6 1 1 2 3

R: 0

Probabil asta gresesti.

Intr-adevar, greseam la genul asta de teste. Am corectat programul si primesc in continuare 9 WA pe aceleasi teste 
Atunci cand sunt 0 oameni nehotarati am pus conditia:

Cod:

if(abs(x1-x2)==1 || abs(y1-y2)==1)
        {
        	g<<0<<'\n';
        	continue;
        }

[•repp4radu]

Iei in continuare 9WA pentru ca este gresita conditia. Mai gandeste-te de ce NU e asa.

[•Detrol2k]

Iei in continuare 9WA pentru ca este gresita conditia. Mai gandeste-te de ce NU e asa.

Am observat ca atunci cand distanta pe X e para si distanta pe Y trebuie sa fie para, sau invers, cand distanta pe X e impara si distanta pe Y trebuie sa fie impara, pentru a exista oameni nehotarati (A+1 sau B+1, dupa caz), dar tot degeaba...

Acum am pus conditia asa:

Cod:

if((abs(x1-x2)%2==1 && abs(y1-y2)%2==0) || (abs(x1-x2)%2==0 && abs(y1-y2)%2==1))
        {
        	g<<0<<'\n';
        	continue;
        }

si mai iau si testul 4, dar tot raman 8 WA  

[•repp4radu]

Nu ai calculat bine in cazul cand se formeaza un patrat. Uite-te acolo si vezi ce e gresit  

[•Detrol2k]

Nu ai calculat bine in cazul cand se formeaza un patrat. Uite-te acolo si vezi ce e gresit  

Ma baga in pamant problema asta.

Atunci cand taxiurile sunt pe aceasi diagonala, am pus asa:

Cod:

if(abs(x1-x2) == abs(y1-y2))
        {
  			int c = 0;
			long sum = 0;
			if(arie(0,max(y1,y2),min(x1,x2),b))
				c++;
			if(arie(max(x1,x2),0,a,min(y1,y2)))
				c++;
			sum += arie(0,max(y1,y2),min(x1,x2),b);
		 	sum += arie(max(x1,x2),0,a,min(y1,y2));
		 	sum += diag(min(x1,x2),max(x1,x2)) - c; 	
            g<<sum<<'\n';
            continue;
        }   

unde arie(x1,y1,x2,y2) returneaza numarul de oameni care asteapta in dreptunghiul cu coltul stanga jos in (x1,y1) si cu coltul dreapta sus in (x2,y2), iar diag() returneaza numarul de oameni de pe diagonala patratului determinat de cele 2 taxiuri.

Mie imi da bine. Am bagat si exemple cand patratul determinat de cele 2 taxiuri este lipit de  OX sau OY, sau cand patratul are latura 1....

Degeaba, tot 8 WA iau  

[•baTTLe4u_15]

Imi dati mai multe teste pentru dx=dy va rog !
Daca se poate si unul mic sa-l pot verifica singur..

[•dutzul]

mhm mie solutia oficiala mi se pare gresita conform solutiei in toate cazurile exista oameni nehotarati

[•repp4radu]

Intr-adevar exista un caz cand niciun om nu e nehotarat