Fişierul intrare/ieşire:pitici4.in, pitici4.outSursăAlgoritmiada 2010, Runda 1
AutorPaul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inpitici4.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content