O companie fomata din n soldati (codificati prin numerele 1, 2, ..., n) are ca misiune sa pazeasca un obiectiv militar de maxima importanta.
Fiecare soldat i, i = 1 ... n are la dispozitie un anumit numar de cartuse pe care le poate folosi pentru apararea obiectivului si este plasat intr-un adapost de coordonate cunoscute (abscisa si ordonata). Intr-un adapost se afla un singur soldat.
Comandantul stabileste zonele de aparare concentrice. O zona de aparare este delimitata de acei soldati care sunt in viata si care daca sunt uniti prin transee (segmente de dreapta) formeaza un poligon convex ce contine in interiorul sau toti ceilalti soldati aflati in viata. O zona de aparare contine cel putin trei soldati si se formeaza imediat dupa ce zona anterioara a cedat. Daca numarul de soldati ramasi la sfarsit este mai mic strict decat 3, acestia mor odata cu ultima zona de aparare.
O zona de aparare cedeaza cand cel putin un soldat din ea nu mai are cartuse (in acel moment toti soldatii de pe zona de aparare respectiva sunt omorati de inamic).
Se stie ca soldatii de pe aceeasi zona de aparare trag cate un cartus la un interval de o secunda, in acelasi timp. Dupa ce o zona de aparare este distrusa, imediat intra in actiune zona de aparare urmatoare.
CerintaDate de intrare
Fisierul de intrare soldati.in contine n+1 linii. Pe prima linie se afla un numar natural n, reprezentand numarul de soldati. Pe fiecare dintre urmatoarele n linii se afla informatii despre un soldat. Mai exact, pe linia i dintre cele n se afla abscisa si ordonata adapostului in care se afla soldatul i, precum si numarul de cartuse pe care le are soldatul i. Valorile de pe aceeasi linie sunt separate prin cate un spatiu.
In fisierul soldati.out va contine o singura linie pe care se afla numarul de secunde cerut.
Restrictii| soldati.in | soldati.out |
| 11 5 0 23 0 2 100 4 3 20000 5 4 10 2 1 301 0 0 45 3 4 567 2 3 342 2 0 2123 3 2 90 4 1 20 |
30 |
Timp maxim de executie/test: 0.2 secunde.