== include(page="template/taskheader" task_id="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 A{~i~} şi, respectiv, B{~i~}_. 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.
h2. Cerinţă
Cunoscând informaţiile furnizate de pitici, determinaţi numărul maxim de pitici ale căror informaţii nu se contrazic.
Poveste şi cerinţă...
h2. 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 A{~i~} şi B{~i~} corespunzătoare afirmaţiilor făcute de pitici.
Fişierul de intrare $pitici4.in$ ...
h2. 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.
În fişierul de ieşire $pitici4.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 200 000$
* $0 ≤ A{~i~}, B{~i~} ≤ 10^6^$
* Pentru 20% din teste, $N ≤ 18$
* Pentru 50% din teste, $N ≤ 5 000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. 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
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. 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).
...
== include(page="template/taskfooter" task_id="pitici4") ==
