Imprimă pagina - 400 Taxi

Titlul: 400 Taxi
Scris de: Daniel Pasaila din Aprilie 04, 2007, 19:48:12

Aici puteţi discuta despre problema Taxi (http://infoarena.ro/problema/taxi).

Titlul: Răspuns: 400 Taxi
Scris de: Andrei Misarca din Ianuarie 27, 2009, 19:28:11

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. :?

Titlul: Răspuns: 400 Taxi
Scris de: Pripoae Teodor Anton din Ianuarie 27, 2009, 19:41:11

E distanta Manhattan.

Titlul: Răspuns: 400 Taxi
Scris de: Andrei Misarca din Ianuarie 29, 2009, 14:09:21

Mersi :D

Cat tre sa dea pt testul

Cod:

1
16 15 1 4 3 6

Titlul: Răspuns: 400 Taxi
Scris de: Gabriel Bitis din Ianuarie 29, 2009, 17:35:13

Titlul: Răspuns: 400 Taxi
Scris de: Andrei Misarca din Ianuarie 29, 2009, 17:36:39

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

Titlul: Răspuns: 400 Taxi
Scris de: Guianu Leon din Noiembrie 30, 2012, 20:57:16

Imi poate da cineva o idee de rezolvare? :?

Titlul: Răspuns: 400 Taxi
Scris de: Radu-Andrei Szasz din Noiembrie 30, 2012, 22:01:50

Gasesti aici (http://www.ginfo.ro/revista/14_1/solutii2.pdf) solutiile oficiale.

Titlul: Răspuns: 400 Taxi
Scris de: Guianu Leon din Decembrie 10, 2012, 18:31:50

Citat din mesajul lui: Szasz Radu din Noiembrie 30, 2012, 22:01:50

Gasesti aici (http://www.ginfo.ro/revista/14_1/solutii2.pdf) 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.

Titlul: Răspuns: 400 Taxi
Scris de: Radu-Andrei Szasz din Decembrie 11, 2012, 21:25:13

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

R: 0

Probabil asta gresesti.

Titlul: Răspuns: 400 Taxi
Scris de: Guianu Leon din Decembrie 12, 2012, 12:19:35

Citat din mesajul lui: Szasz Radu din Decembrie 11, 2012, 21:25:13

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;
        }

Titlul: Răspuns: 400 Taxi
Scris de: Radu-Andrei Szasz din Decembrie 12, 2012, 13:45:04

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

Titlul: Răspuns: 400 Taxi
Scris de: Guianu Leon din Decembrie 14, 2012, 21:17:26

Citat din mesajul lui: Szasz Radu din Decembrie 12, 2012, 13:45:04

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 ](*,)

Titlul: Răspuns: 400 Taxi
Scris de: Radu-Andrei Szasz din Decembrie 14, 2012, 22:03:57

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

Titlul: Răspuns: 400 Taxi
Scris de: Guianu Leon din Decembrie 15, 2012, 20:28:56

Citat din mesajul lui: Szasz Radu din Decembrie 14, 2012, 22:03:57

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

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 ](*,) :fighting: :annoyed: :fool:

Titlul: Răspuns: 400 Taxi
Scris de: Nita Iulian din Ianuarie 08, 2013, 15:37:47

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

Titlul: Răspuns: 400 Taxi
Scris de: Bodnariuc Dan Alexandru din Februarie 01, 2013, 15:50:35

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

Titlul: Răspuns: 400 Taxi
Scris de: Radu-Andrei Szasz din Februarie 01, 2013, 20:12:42

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

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Daniel Pasaila din Aprilie 04, 2007, 19:48:12