== include(page="template/taskheader" task_id="tricouri") ==
Poveste și cerință...
p>. _„Munca bate talentul, când talentul nu muncește.”_
- T. Notke
h2. Date de intrare
Înainte de finala campionatului regional de fotbal, antrenorul echipei „Sahtior Maramu”, domnul Andrei, împreună cu analiștii echipei, John și Bob, au analizat formația de joc. Pentru aceasta, ei au așezat pe teren [*N*] jucători în linie.
Fișierul de intrare $tricouri.in$ ...
Fiecare jucător poartă un tricou pe care este imprimată o singură cifră (de la 0 la 9). Întrucât bugetul echipei este unul restrâns, mai mulți jucători pot purta tricouri cu același număr. Privind de la stânga la dreapta, cifrele de pe tricourile jucătorilor formează un număr natural.
h2. Date de ieșire
!{width:600px}problema/tricouri?tricouri.jpg!
De exemplu, tricourile jucătorilor de mai sus formează numărul natural 529738.
Analiștii John și Bob au observat că pentru a stabili tactica de joc pentru finala campionatului, domnul Andrei respectă următorii pași:
* Din cei [*N*] jucători chemați în teren inițial, el trebuie să elimine exact [*K*] jucători ([*K*] < [*N*]) cerându-le să meargă pe banca de rezerve. Jucătorii rămași în teren se vor apropia unul de celălalt, păstrându-și ordinea initială;
* Pentru a asigura succesul echipei, Andrei va elimina cei [*K*] jucători astfel încât numărul format din cifrele de pe tricourile jucătorilor rămași în teren să fie cel mai mare număr posibil. Acest număr reprezintă _*valoarea tactică*_ a echipei;
* Apoi, pentru înscrierea în sistemul electronic al federației, Andrei trebuie să calculeze _*stabilitatea*_ echipei, definită de cel mai mare număr natural [*X*], al cărui pătrat nu depășește valoarea tactică [*V*] a echipei ([*X*][^2^] ≤ [*V*]).
La unele meciuri, din cauza numărului foarte mare de jucători chemați pe teren, echipa nu dispune de suficiente tricouri cu cifre diferite. În aceste situații speciale, toți jucătorii poartă tricouri pe care sunt imprimate doar cifrele 0 sau 1. În acest caz (în care cifrele de pe tricouri sunt doar valori de 0 și 1), valoarea tactică este interpretată în baza 2. De exemplu, dacă în teren rămân jucătorii cu tricourile 1, 1, 1, valoarea tactică este 111 (în baza 2), adică numărul 7 (în baza 10).
În fișierul de ieșire $tricouri.out$ ...
Cum timpul până la marea finală este limitat, John și Bob vă roagă să îl ajutați pe antrenorul Andrei să înscrie echipa în sistemul electronic al federației.
h2. Restricții
h2. Cerințe
* $... ≤ ... ≤ ...$
Se cunosc [*C*] (numărul cerinței, 1 sau 2), [*N*] numărul inițial de jucători, [*K*] numărul de jucători ce trebuie eliminați, precum și cele [*N*] cifre de pe tricourile jucătorilor. Ajutați-l pe antrenorul Andrei să determine:
# Valoarea tactică a echipei, dacă [*C*]=1.
# Stabilitatea echipei, dacă [*C*]=2.
h2. Date de intrare
Fișierul de intrare $tricouri.in$ contine pe prima linie trei numere naturale separate prin spațiu: [*C*], [*N*] și [*K*], cu semnificația din enunț. Pe a doua linie, separate prin câte un spațiu, se află cele [*N*] cifre (valori de la 0 la 9) de pe tricourile jucătorilor, în ordinea în care aceștia sunt asezați inițial în teren.
h2. Date de ieșire
h2. Exemplu
Fișierul de iesire $tricouri.out$ va conține:
table(example).
|_. tricouri.in |_. tricouri.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* Un singur număr natural scris în baza 10 reprezentând valoarea tactică obținută, dacă [*C*]=1.
* Un singur număr natural scris în baza 10 reprezentând stabilitatea echipei ([√[*V*]], unde [*V*] este valoarea tactică), dacă [*C*]=2.
h3. Explicație
h2. Restricții și precizări
...
* 1 ≤ [*N*] ≤ 5 · 10[^4^]
* 0 ≤ [*K*] < [*N*]
* Pentru [*C*]=2, 1 ≤ [*N*]-[*K*] ≤ 18 · 10[^3^]
* Prima cifră a șirului initial este întotdeauna diferită de 0
* Zerourile nesemnificative de la începutul unui număr trebuie să *nu* fie afișate
table(){width:auto}.
|_. # |_. Punctaj |_. Restricții |
| 1 | 14 | [*C*]=1 si [*N*] ≤ 1000 |
| 2 | 26 | [*C*]=1 si [*N*] > 1000 |
| 3 | 10 | [*C*]=2 și [*N*]-[*K*] ≤ 9 |
| 4 | 10 | [*C*]=2 si [*N*]-[*K*] ≤ 18 |
| 5 | 27 | [*C*]=2, cifrele de pe tricouri ∈ {0, 1, ..., 9}, [*N*]-[*K*] ≤ 5000 și există cel puțin un jucător cu cifra de pe tricou ∈ {2, 3, ..., 9} |
| 6 | 13 | [*C*]=2, cifrele de pe tricouri ∈ {0, 1} și nu există restricții suplimentare. |
h2. Exemple
table(example).
|_. tricouri.in |_. tricouri.out |_. Explicații |
| 1 6 2
5 2 9 7 3 8
| 9738
| Eliminăm 2 jucători din cei 6 din teren. Dacă trimitem pe bancă jucătorii cu
tricourile 5 și 2, rămânem cu cel mai mare număr posibil format de ceilalți:
9738.
Aceasta este valoarea tactică.
|
| 2 6 2
5 2 9 7 3 8
| 98
| Valoarea tactică maximă este 9738 (ca în exemplul 1). Stabilitatea echipei
este [√9738]=98, deoarece 98[^2^]=9604 ≤ 9738 < 9801=99[^2^].
|
| 2 4 0
1 2 3 4
| 35
| [*K*]=0, deci nu se elimină niciun jucător. Valoarea tactică este 1234.
Coeficientul de stabilitate este [√1234]=35, deoarece
35[^2^]=1225 ≤ 1234 < 1296=36[^2^]
|
| 2 4 0
1 0 1 1
| 3
| Toate cifrele sunt 0 sau 1, deci valoarea tactică se interpretează în baza 2:
1011[~2~]=11[~10~]. Stabilitatea echipei este [√11]=3, deoarece
3[^2^]=9 ≤ 11 < 16=4[^2^]
|
| 2 6 2
1 0 1 1 0 1
| 3
| Eliminăm 2 jucători, maximizând numărul format de cifrele rămase: 1111.
Deoarece cifrele sunt doar 0 și 1, interpretăm 1111[~2~]=15[~10~]. Stabilitatea
este [√15]=3, deoarece 3[^2^]=9 ≤ 15 < 16=4[^2^].
|
== include(page="template/taskfooter" task_id="tricouri") ==
