== include(page="template/taskheader" task_id="gadfadar") ==
%{float:right}!problema/gadfadar?ierarhie.png!%
!>problema/gadfadar?ierarhie.png!
Ești consilierul unei organizații criminale. Aceasta are următoarea ierarhie (vezi imaginea din dreapta). Șeful organizației, Don-ul, suspectează faptul că există un intrus printre rangurile “Capo”, și îți cere să afli care este acela.
Ești consilierul unei organizații criminale. Aceasta are următoarea ierarhie (vezi imaginea din dreapta). Șeful organizației, Don-ul, suspectează faptul că există un intrus printre rangurile “Capo” și îți cere să afli care este acela.
bq. Găsește-mi intrusul nepoate, cel cu un număr de soldați diferit de cel precizat în dosarele organizației,
acela este intrusul.
bq. Găsește-mi intrusul nepoate, cel cu un număr de soldați diferit de cel precizat în dosarele organizației, acela este intrusul.
Problema este că dosarele de care ai nevoie au fost arse de intrus. Neștiind ce să faci, te duci la bar. În timp ce iți bei whisky-ul încerci să afli ce regulă urmează numărul de soldați al fiecărui “Capo”. Fiecărui “Capo” îi este atribuit un nume,un indentificator si un număr de soldați. Numărul de soldați este determinat de suma divizorilor identificatorului. Acum poți afla care este intrusul.
Problema este că dosarele de care ai nevoie au fost arse de intrus. Neștiind ce să faci, te duci la bar. În timp ce îți bei whisky-ul încerci să afli ce regulă urmează numărul de soldați al fiecărui “Capo”. Fiecărui “Capo” îi este atribuit un nume, un indentificator și un număr de soldați. Numărul de soldați este determinat de suma divizorilor identificatorului. Acum poți afla care este intrusul.
h2. Cerință
Dându-se un număr natural *[$N$]*, iar apoi $N$ perechi de forma *$nume id nr_soldați$* să se determine numărul de intruși și numele acestora
Dându-se un număr natural *[$N$]*, iar apoi *[$N$]* tripleți de forma *$nume id nr_soldați$* să se determine numărul de intruși și numele acestora
h2. Date de intrare
Fișierul de intrare $gadfadar.in$ conține pe prima linie numărul N, ce reprezintă numărul persoanelor cu rangul de “Capo”. Pe următoarele N linii se află perechi de forma precizată mai sus in cerință.
Fișierul de intrare $gadfadar.in$ conține pe prima linie numărul *[$N$]*, ce reprezintă numărul persoanelor cu rangul de “Capo”. Pe următoarele *[$N$]* linii se află tripleți de forma precizată mai sus in cerință.
h2. Date de ieșire
În fișierul de ieșire $gadfadar.out$ se află pe prima linie un număr natural *[$K$]*, ce reprezintă numărul de intruși, pe următoarele K linii se află numele intrușilor (in ordine +lexicografică+).
În fișierul de ieșire $gadfadar.out$ se află pe prima linie un număr natural *[$K$]*, ce reprezintă numărul de intruși, pe următoarele *[$K$]* linii se află numele intrușilor (în ordine +lexicografică+).
h2. Restricții
* $1 ≤ *N* ≤ 10[^4^]⋅3$
* $1 ≤ *N* ≤ 3⋅10[^3^]$
* $1 ≤ *id* ≤ 10[^12^]$
* $1 ≤ *lungimea numelor* ≤ 30$
* $1 ≤ *nr_soldați* ≤ 2[^64^]-1$
* $1 ≤ *K* ≤ 100$
h2. Subtask-uri
* $Subtask 1: *N* ≤ 10 și *id* ≤ 10[^6^] (10 puncte)$
* $Subtask 2: *N* ≤ 10[^3^]⋅3 și *id* ≤ 10[^9^] (30 puncte)$
* $Subtask 3: *N* ≤ 10[^3^]⋅3 și *id* ≤ 10[^12^] (20 puncte)$
* $Subtask 2: *N* ≤ 3⋅10[^2^] și *id* ≤ 10[^9^] (30 puncte)$
* $Subtask 3: *N* ≤ 3⋅10[^2^] și *id* ≤ 10[^12^] (20 puncte)$
* $Subtask 4: Restricțiile inițiale (40 puncte)$
h2. Exemplu
table(example).
table(example).
|_. gadfadar.in |_. gadfadar.out |
| 5
Michele 18 39
