== include(page="template/taskheader" task_id="poligon6") ==
Poveste şi cerinţă...
Poligonul de tragere este un teren special amenajat în cadrul căruia se fac exerciţii şi se execută trageri cu arme de foc. Comandantul plasează câte o ţintă în toate punctele aflate la distanţele $R{~i~}$, $1 ≤ i ≤ n$ faţă de punctul de tragere (origine) şi care au coordonatele carteziene numai numere naturale nenule.
Specialiştii în armament români au creat recent o nouă armă sub forma unui tun laser care îşi lansează razele pe o traiectorie rectilinie şi are capacitatea de a distruge toate ţintele aflate pe direcţia de tragere.
Ştiind că tunul laser se găseşte în originea sistemului de coordonate, să se scrie un program care să determine: numărul de ţinte, numărul minim de lovituri de tun laser necesare pentru a distruge toate ţintele precum şi numărul de ţinte doborâte la fiecare lovitură. Spre exemplu, dacă avem $n=6$ distanţe (5, 7, 10, 13, 15, 17) pentru care se încearcă plasarea ţintelor, atunci în poligon se vor plasa 10 ţinte, va fi nevoie de 6 lovituri pentru a doborî toate ţintele iar la fiecare lovitură se vor doborî respectiv 1, 1, 3, 3, 1, 1 ţinte.
h2. Date de intrare
Fişierul de intrare $poligon6.in$ ...
Fişierul de intrare $poligon6.in$ conţine pe prima linie numărul $n$ de distanţe la care vor fi plasate ţinte, iar pe a doua linie $n$ numere naturale nenule distincte separate printr-un spaţiu, ce reprezintă aceste distanţe.
h2. Date de ieşire
În fişierul de ieşire $poligon6.out$ ...
Fişierul de ieşire $poligon6.out$ va conţine 3 linii. Pe prima linie se va scrie numărul ţintelor plasate în poligon. Pe a doua linie se va scrie numărul minim de lovituri de tun laser cu care se pot doborî toate ţintele, iar pe a treia linie se va scrie numărul de ţinte doborâte la fiecare lovitură, separate printr-un spaţiu, în ordinea crescătoare a unghiurilor direcţiilor cu axa OX.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1000$
* $1 ≤ R{~i~} ≤ 1000$
* Pentru fiecare set de date de intrare, în poligon va exista cel puţin o ţintă.
* Se acordă:
** 20% din punctaj pentru determinarea corectă a numărului de ţinte.
** 40% din punctaj pentru determinarea corectă a numărului minim de lovituri.
** 40% din punctaj pentru determinarea corectă a numărului de ţinte doborâte la fiecare lovitură.
h2. Exemplu
table(example). |_. poligon6.in |_. poligon6.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|6
5 10 15 7 13 17
|10
6
1 1 3 3 1 1
|
h3. Explicaţie
...
Avem 6 distanţe: 5, 10, 15, 7, 13, 17. În poligon vor fi plasate 10 ţinte (punctele negre marcate pe figură) care pot fi doborâte din 6 lovituri iar la fiecare lovitură se vor doborî câte 1, 1, 3, 3, 1, 1 ţinte. Exemplul corespunde imaginii de mai jos.
!problema/poligon6?poligon.jpg 35%!
== include(page="template/taskfooter" task_id="poligon6") ==
