Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | pitici4.in, pitici4.out | Sursă | Algoritmiada 2010, Runda 1 |
| Autor | Paul-Dan Baltescu | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pitici4
Laura locuieşte împreună cu cei N pitici. Într-una din zilele trecute, piticii au facut o plimbare prin pădurea din jurul căsuţei lor. În timpul plimbării piticii au format mai multe grupuri, fiecare pitic formând un grup cu prietenii lui cei mai apropiaţi. Cum cărările pădurii sunt destul de înguste, două grupuri de pitici nu puteau merge în paralel. Din păcate, în astfel de situaţii când piticii se pun pe povestit se întâmplă să-şi uite bunele maniere şi curând au devenit atât de gălăgioşi încât au ajuns să le deranjeze pe restul vieţuitoarelor din pădure. Laura a aflat aceste lucruri si s-a hotărât să îi certe, dar mai întâi a dorit să afle cum erau aceştia aşezaţi în grupuri. Piticii nu doresc să-şi trădeze prietenii apropiaţi şi, de aceea, tot ce sunt de acord să-i spună Laurei sunt fraze de tipul următor: Numărul total de pitici din alte grupuri ce se aflau în faţa mea şi în spatele meu este Ai şi, respectiv, Bi. Unii pitici mai isteţi şi-au dat seama că aceste informaţii îi sunt suficiente Laurei pentru a reconstitui aşezarea lor pe grupuri şi, pentru a o încurca, au minţit. Cum socoteala nu a ieşit, Laura şi-a dat seama că unii pitici au minţit-o. Cum nu mai poate reconstitui aşezarea piticilor, ea doreşte să ştie care este numărul maxim de pitici ale căror informaţii nu se contrazic.
Cerinţă
Cunoscând informaţiile furnizate de pitici, determinaţi numărul maxim de pitici ale căror informaţii nu se contrazic.
Date de intrare
Fişierul de intrare pitici4.in va conţine, pe prima linie, numărul întreg N. Pe următoarele N linii se găsesc câte două numere întregi Ai şi Bi corespunzătoare afirmaţiilor făcute de pitici.
Date de ieşire
În fişierul de ieşire pitici4.out va conţine un singur număr întreg reprezentând numărul maxim de pitici ale căror informaţii nu se contrazic.
Restricţii
- 1 ≤ N ≤ 200 000
- 0 ≤ Ai, Bi ≤ 106
- Pentru 20% din teste, N ≤ 18
- Pentru 50% din teste, N ≤ 5 000
Exemplu
| pitici4.in | pitici4.out |
|---|---|
| 9 6 4 0 4 4 4 6 0 5 3 0 4 0 4 6 0 7 0 | 6 |
| 4 0 1 0 1 0 1 0 1 | 3 |
Explicaţie
Exemplul 1:
Putem presupune că există 3 grupuri: primul de 5 pitici, al doilea de 1 pitic şi ultimul de 3 pitici. Pentru această aşezare pe grupuri, piticii ale căror informaţii nu se contrazic sunt 2, 4, 5, 6, 7 şi 8. Piticii 2, 6 şi 7 ar aparţine primului grup, piticul 5 formează al doilea grup, iar piticii 4 şi 8 ar aparţine celui de-al treilea grup. Această aşezare pe grupuri corespunde numărului maxim de pitici ale căror informaţii nu se contrazic. Pe acest exemplu, mai observăm că afirmaţia primului pitic nu va fi niciodată adevărată (el susţinând că în total există minim 6+1+4=11 pitici).
Exemplul 2:
Putem presupune că există două grupuri: unul de 3 pitici şi unul format dintr-un singur pitic. Putem considera că oricare 3 pitici spun adevărul, însă cel de-al patrulea obligatoriu minte (deoarece nu se poate afla în acelaşi grup cu ceilalţi 3, aceştia susţinând că un pitic se află într-un alt grup în spatele lor).
