infoarena

TAXE

Într-o ţară în care corupţia este în floare şi economia la pământ, pentru a obţine toate aprobările necesare în scopul demarării unei afaceri, investitorul trebuie să treacă prin mai multe camere ale unei clădiri în care se află birouri.
Clădirea are un singur nivel în care birourile sunt lipite unele de altele formând un caroiaj pătrat de dimensiune nxn. Pentru a facilita accesul în birouri, toate camerele vecine au uşi între ele. În fiecare birou se află un funcţionar care pretinde o taxă de trecere prin cameră (taxă ce poate fi, pentru unele camere, egală cu 0). Investitorul intră încrezător prin colţul din stânga-sus al clădirii (cum se vede de sus planul clădirii) şi doreşte să ajungă în colţul opus al clădirii, unde este ieşirea, plătind o taxă totală cât mai mică.

Cerinţă
Ştiind că el are în buzunar S euro şi că fiecare funcţionar îi ia taxa de cum intră în birou, se cere să se determine dacă el poate primi aprobările necesare şi, în caz afirmativ, care este suma maximă de bani care îi rămâne în buzunar la ieşirea din clădire.

Date de intrare
Fişierul de intrare taxe.in conţine pe prima linie cele două numere S şi n despărţite printr-un spaţiu, iar pe următoarele n linii câte n numere separate prin spaţii ce reprezintă taxele cerute de funcţionarii din fiecare birou.

Date de ieşire
Fişierul de ieşire taxe.out conţine o singură linie pe care se află numărul maxim de euro care îi rămân în buzunar sau valoarea –1 dacă investitorului nu-i ajung banii pentru a obţine aprobarea.

Restricţii şi precizări
   3<=N<=100
   1<=S<=10000
   Valorile reprezentând taxele cerute de funcţionarii din birouri sunt numere naturale, o taxă nedepăşind valoarea de 200 de euro.
   La încheierea programului nu se va solicita apăsarea unei taste

Exemple

taxe.in   taxe.out
10 3
1 2 5
1 3 1
0 8 1   3

Timp maxim de executare/test: 1 secundă



am inceput din dreapta jos si fac sumele mergand in sus sau in stanga (unde e mai convenabil) problema apare la testul urmator:

93 7
1 99 1 1  1 1 1
1 99 1 1  1 1 1
1 99 1 99 9 1 1
1 99 1 99 1 1 1
1 99 1 99 1 2 1
1 99 1 99 1 1 1
1 1  1 99 9 1 1                  

is cam fraged in ale programarii ma lamuriti careva? un exemplu miar prinde bine.. daca nu toata rezolvarea :D

problema se rezolva usor folosind cunostinte de teoria grafurilor, insa probabil cauti o solutie care sa nu necesite asta. Ideea e ca prin fiecare camera treci cel mult 1 singura data, deci poti aplica urmatoare rezolvare folosind algoritmul lui lee:

- mentii o coada cu pozitiile la care ai ajuns la un moment dat
- scoti un element din coada, si daca obtii ceva mai bun pt vecinii sai ii inserezi in coada
- te opresti cand nu mai sunt elemente in coada

Complexitatea e cam mare, dar faci urmatoarea observatie:
- daca la un moment dat scoti elementul cu valoarea cea mai mica din coada
sigur nu o sa ajungi sa il mai inserezi inca o data
Deci acum, de fiecare data cand introduci elemente in coada, le sortezi
Nici aceasta metoda nu este ideala, dar intra in timp pt testele propuse (problema a fost data la oji2003, cred ca stiai asta)

Daca vrei o rezolvare mai buna, cauta informatii despre grafuri, heap`uri

mersi ! de la oji 2003 ii problema. pe rezolvarea mea iau 60 de pct. da sper sa ma calific anu asta la oni asa ca trebuie mai mult :)

care mai sunteti de a 10a? ziceti-mi si mie cam ce stiti?:)

Pai te-ai apucat de treaba cu 4-5 zile inainte ?
S-ar putea sa fii dezamagit.

nui asa mare concurenta in salaj..
depinde si de solutia de moment .. si de subiect.. acum 2 ani la clasa a 10a locu 1 a avut 10 pct ;)

hihi, ce misto e sa ajungi asa usor la oni..
btw daca te apuci de (sau stii deja) grafuri, problema se rezolva calculand drumul minim intre nodul (1,1) si (n,n). (consideri fiecare camera un nod intr-un graf neorientat, si ai muchie intre camerele care se invecineaza)
un algoritm cat-de-cat simplu si clasic (care se da pe la OJI-uri) e "dijkstra" si il gasesti prin toate cartile de programare in care sunt prezentate grafuri

merge de 100 problema asta cu varianta neimbunatatita de dijkstra.

mersi mersi :)
am 2 ore de info pe sapt.. in programa de anu asta nam nici backtracking dapoi grafuri.. sper sa ne vedem la oni  8-[

Si eu am primit acelasi tip de manual, dar nu-l mai am pentru ca l-am inapoiat scolii :P!  Cred ca oricat de "jaf" ar fi manualul tau tot iti arata cum se implementezi o coada de prioritati, asa ca poti sa te uiti in revista GInfo, numarul 15/2 din februarie 2005, pentru ca e un articol despre algoritmul lui Lee si problema Taxe rezolvata ca la  :book: !


Cum spunea si Mircea (domino) in ghid: "Din fericire pentru unii si din nefericire pentru altii, majoritatea examenelor nu iti cer sa dovedesti ca esti bine pregatit, ci ca esti mai bine pregatit decat altii."  Anul viitor ma mut in Salaj! :)

Problema e cel mai bun exemplu de Lee de cost minim intr-o matrice folosind ca structura de date coada.
Pentru coada uita-te intr-adevar in numarul de GInFo de februarie din 2005 sau daca nu cauta in culegerea lui Tudor Sorin de a X-a aceea galbena la Capitolul 4 -> Structuri de date.
Daca ai Cormenul e si mai bine -> pagina 172.Pentru implementare manualele de info.(cred.....si sper! :-k)

 :peacefingers: