Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | mincinosi.in, mincinosi.out | Sursă | Algoritmiada 2012, Runda 1 |
| Autor | Andrei Ciupan | Adăugată de |  Andrei Parvu •andrei.12 |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mincinosi
HM are destul de mulţi prieteni (în număr de N, mai exact), dar nu ştie în care dintre ei să se încreadă, deoarece o mare parte sunt nişte mincinoşi notorii. Ca sa afle acest lucru, el pune urmatoarea întrebare: ”Câţi mincinoşi există în grupul meu de N prieteni?” şi notează pentru fiecare răspunsul pe care l-a dat.
HM trebuie să decidă acum care este numărul maxim de prieteni care ar fi putut răspunde adevărat la acesată întrebare (adică răspunsurile lor să nu se contrazica şi să precizeze un număr posibil corect de mincinoşi), şi care ar fi aceştia.
Date de intrare
Fişierul de intrare mincinosi.in conţine pe prima linie N, numărul de prieteni ai lui HM.
Următoarea linie conţine răspunsurile celor N prieteni, al i-lea număr reprezentând răspunsul prietenului i.
Date de ieşire
În fişierul de ieşire mincinosi.out se află pe prima linie numarul maxim de prieteni care ar fi putut răspunde adevărat la întrebare.
Pe următoarele linii se află indicii (din ordinea datelor de intrare) ai acestor prieteni.
Restricţii
- 1 ≤ N ≤ 1.000.000
- În caz în care există mai multe soluţii cu număr maxim de prieteni, se poate afişa oricare.
- Răspunsul unui prieten este în intervalul [1, N]
Exemplu
| mincinosi.in | mincinosi.out |
|---|---|
| 5 4 3 3 0 0 | 2 2 3 |
Explicaţie
Prietenii care spun adevărul sunt cei cu indici 2 şi 3, care menţioneaza ca există 3 mincinoşi (prietenii cu indicii 1, 4, 5).
Se observă ca o soluţie cu număr nemaxim de prieteni ar fi fost ca prietenul 1 să spună adevărul.
