Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | facebook.in, facebook.out | Sursă | Infoarena Monthly 2012, Runda 10 |
| Autor | Teodor Plop | Adăugată de |  Mihai-Alexandru Dusmanu •dushmi |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Facebook
In partea dreapta pe Facebook iti apar K sugestii de prieteni. Pentru fiecare sugestie se cunoaste numarul de prieteni comuni. Gigel vrea sa obtina la sugestii K persoane cu care sa aiba acelasi numar de prieteni in comun. El poate sa respinga o sugestie a Facebook-ului, caz in care locul acelei persoane este luat de altcineva. Stiind dinainte ordinea celor N > K sugestii pe care le are pregatitie Facebook, gasiti numarul minim de operatii astfel incat sa satisfaceti dorinta lui Gigel. In cazul in care nu exista solutie, -1.
Date de intrare
Fişierul de intrare facebook.in va contine pe prime linie numerele N si K. Pe cea de-a doua linie se vor afla N numere, reprezentand numarul de prieteni pe care Gigel ii are in comun cu fiecare dintre prietenii sugerati de Facebook, in ordinea aparitiei lor in lista de sugestii.
Date de ieşire
În fişierul de ieşire facebook.out se va afisa pe prima linie numarul minim de operatii si numarul de prieteni pe care Gigel ii are in comun cu cei care apar, dupa efectuarea operatiilor, in lista de K sugestii.
Restricţii
- 1 ≤ K ≤ N ≤ 1000000
- Gigel este foarte popular asa ca numarul de prieteni pe care ii are in comun cu sugestiile date de Facebook se incadreaza in intervalul [0, 230]
Exemplu
| facebook.in | facebook.out |
|---|---|
| 6 3 1 2 3 1 1 2 2 | 2 1 |
Explicaţie
Gigel respinge a doua sugestie, iar lista de K sugestii devine: 1 3 1.
Gigel respinge a doua sugestie din nou, iar noile sugestii sunt: 1 1 1.
