Curse de mașini

Probleme, Teme

Într-o bună zi, Vasilică a vrut să organizeze o cursă cu mai mulți piloți români de raliuri. Cum aceștia erau situați în orașe diferite, s-a hotărât ca fiecare dintre ei să parcurgă aceeași distanță, dar în propriul oraș. Dar, cum Vasilică este din România, el știe că fiecare dintre aceștia nu vor avea condiții egale de concurs datorită calității drumului (ex: gropi, serpentine, drum în lucru, etc.) deși ei sunt foarte bine pregătiți .

Cerințe

Dându-se numărul de piloți N și un număr D de sectoare pe care le au de parcurs, se cere sa se afișeze clasamentul intermediar al piloților după fiecare sector de drum parcurs de toți participanții (adică ordinea timpilor intermediari după un anumit număr de sectoare străbătut de toti piloții). Un drum este format din D sectoare (cu aceeași lungime) și este descris prin D valori Tj (1<=j<=D) care reprezintă timpul necesar unui pilot să parcurgă acest sector de drum. După terminarea cursei, Vasilică s-a gandit că ar vrea să știe cum ar fi putut să-i ajute pe fiecare dintre acești piloți ca să câștige, știind că el poate vorbi cu autoritățile locale din orice oraș pentru îmbunătățirea situației drumurilor astfel:

  • o primă reparație a sectorului j de drum reduce perioada Tj de parcurgere la jumatate (T j’ = Tj / 2);
  • o reparație ulterioară (indiferent de câte urmează) a sectorului de drum reduce perioada T j’ cu un sfert (Tj = 3* T j’ /4);

Ajutați-l pe Vasilică să calculeze numărul minim de îmbunătățiri de care are nevoie fiecare pilot pentru a obține un timp mai mic sau egal cu cel al câștigătorului actual.

Date de intrare

Pe prima linie se vor introduce doua valori întregi N și D cu semnificația din enunț, pe următoarele N linii câte D valori reale (0< Tj <1000) cu semnificația că pe linia i+1 va fi introdusa descrierea drumului pentru pilotul i.

 N D // cu semnificația din enunț

      \[T_{1}\]
 ... 
      \[T_{D}\]
 // Primul pilot
 ...

      \[T_{1}\]
 ... 
      \[T_{D}\]
 // N-lea pilot

Date de ieșire

Pe primele D linii vor fi afișate câte N valori (Ci cu semnificația că pilotul i se afla pe poziția Ci), după aceea se vor afișa N linii pe fiecare linie câte un număr (Ki cu semnificația că pilotul i are nevoie de Ki îmbunătățiri pentru a caștiga cursa).

      \[C_{1}\]
 ... 
      \[C_{N}\]
// clasamentul dupa primul sector
 ...

      \[C_{1}\]
 ... 
      \[C_{N}\]
 // clasamentul dupa al D-lea sector

      \[K_{1}\]
 //imbunătățiri pentru primul

      \[K_{2}\]

 ...

      \[K_{N}\]
 //imbunătățiri pentru al N-lea pilot

Restricții și precizări

0.000<=
      \[T_{i}\]
<1000.000
1<= N <=1000
1<= D <=10

În cazul în care după un anumit număr de sectoare doi piloți au același timp în clasamentul general atunci aceștia vor ocupa aceeași poziție, iar următorul din clasament va fi pus pe adevarata poziție . Pentru învingător numărul minim de sectoare care trebuie îmbunătățite este 0.

Exemplu:

intrare
4 3
1.2 0.5 1.3
1.1 0.6 1.1
1.9 2.1 2.0
1.1 0.6 1.1

 

ieșire:
3 1 4 1 //clasamentul după primul sector
1 1 4 1 //clasamentul după al doilea sector
3 1 4 1 //clasamentul după al treilea sector
1 //se poate îmbunătăți ultimul sector și atunci timpul total va fi 2.35 < 2.8 (câștigătorul actual)
0 //el este câștigător
4 //are nevoie de îmbunătățiri la toate cele 3 sectore în prima fază, plus o îmbunătățire ulterioară la sectorul 2: 1.9/2 + 3*(2.1/2)/4 + 2.0/2 = 0.95 + 0.7875 + 1 = 2.7375 < 2.8
0 //el este câștigător

 

Autor : Bogdan-Cristian Drutu

Data: 02.11.2009

 

Tags: ,