Fişierul intrare/ieşire:mincinosi.in, mincinosi.outSursăAlgoritmiada 2012, Runda 1
AutorAndrei CiupanAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 [0, N]

Exemplu

mincinosi.inmincinosi.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content