|
Titlul: 1236 Controlor Scris de: Andrei Grigorean din Februarie 26, 2012, 14:39:20 Aici puteti discuta despre problema Controlor (http://infoarena.ro/problema/controlor).
Titlul: Răspuns: 1236 Controlor Scris de: Sorin Rita din Februarie 26, 2012, 18:05:33 Imi explica si mie cineva de ce pentru 2,1 raspunsul e 15 ? E destul de ambiguu enuntul.
Titlul: Răspuns: 1236 Controlor Scris de: Andrei Grigorean din Februarie 26, 2012, 18:12:07 Ce este ambiguu in enunt?
Cati calatori se afla in tren intre statiile 2 si 3? Cati dintre ei se aflau deja in tren inainte de statia 2? Titlul: Răspuns: 1236 Controlor Scris de: George Marcus din Februarie 26, 2012, 18:16:28 La (2,1) trebuie sa spui cate persoane se afla in tren intre statiile (2,3) si trebuie sa iei in considerare doar persoanele care au urcat dupa sau la statia 2. La statia 2 urca 5+6+4=15 persoane si doar pe acestea le luam in considerare.
Titlul: Răspuns: 1236 Controlor Scris de: Andrei F. din Martie 14, 2012, 22:45:14 Am o intrebare... imi explicati va rog frumos cum se face pentru linia i=2?
Eu am ca la m[2][1]=15 si m[2][2]=20 m[2][3]=13... nu inteleg cum se face calculul... Titlul: Răspuns: 1236 Controlor Scris de: FII Florea Toma Eduard din August 30, 2012, 16:05:40 In primul rand,la aceasta problema tu nu trebuie sa abordezi cu o rezolvare pe linii,ci pe coloane...
Trebuie sa utilizezi o matrice dp[ i ][ j ] care sa semnifice numarul de calatori prezenti in tren la statia i + j ,presupunand ca Miruna verifica biletele la statia i. Este destul de intuitiv faptul ca pentru coloana 1,adica pentru dp[ 1 ][ 1 ], dp[ 2 ][ 1 ]...vom aduna numarul tuturor calatorilor de pe linia respectiva.Iar pentru coloanele 2, 3....respectiv n - 1 vom avea urmatoarea relatie: dp[ i ][ j ] = dp[ i ][ 1 ] - ( a[ i ][ 1 ] + a[ i ][ 2 ] + ........ + a[ i ][ j ] ) + dp[ i + 1 ][ j - 1 ];Mentionez ca in matricea a tu citesti valorile respective din fisierul de intrare. Bineinteles...se poate reduce complexitatea cu o alta matrice de sume partiale.Dar aici te las pe tine :D. Titlul: Răspuns: 1236 Controlor Scris de: Rares Cheseli din Septembrie 14, 2013, 23:53:27 Pentru cei care iau 70p cu TLE pe ultimele 3 teste, afisati cu cstdio.
|