| Fișierul intrare/ieșire | gadfadar.in, gadfadar.out | Sursă | CPPI Craiova |
|---|---|---|---|
| Autor | David Curcă | Adăugată de |
David Curca
•
divaddd
|
| Timp de execuție pe test | 0.2 sec | Limită de memorie | 1256 KB |
| Scorul tău | N/A | Dificultate |
   3.5
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Gadfadăr (clasa 6-7)
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.
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 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.
Cerință
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
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ă tripleți de forma precizată mai sus in cerință.
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 (în ordine lexicografică).
Restricții
- 1 ≤ N ≤ 3⋅103
- 1 ≤ id ≤ 1012
- 1 ≤ lungimea numelor ≤ 30
- 1 ≤ nr_soldați ≤ 264-1
- 1 ≤ K ≤ 100
Subtask-uri
- Subtask 1: N ≤ 10 și id ≤ 106 (10 puncte)
- Subtask 2: N ≤ 3⋅102 și id ≤ 109 (30 puncte)
- Subtask 3: N ≤ 3⋅102 și id ≤ 1012 (20 puncte)
- Subtask 4: Restricțiile inițiale (40 puncte)
Exemplu
| gadfadar.in | gadfadar.out |
|---|---|
| 5 Michele 18 39 DonVito 43 44 Sonny 45 78 Emilio 38 45 Fredo 32 63 |
1 Emilio |
| 20 Michele 262 396 DonVito 68 116 Sonny 267 360 Emilio 20 32 Fredo 82 116 Virgil 39 46 Peter 34 44 Johnny 199 200 Carlo 238 432 Lucy 175 248 Carmela 200 465 Connie 175 248 Paulie 222 456 Bonasera 105 182 Moe 171 260 Cardinal 58 80 Nazorine 19 10 Fabrizio 96 242 Cuneo 187 216 Bruno 79 70 |
10 Bonasera Bruno Cardinal DonVito Emilio Fabrizio Fredo Nazorine Peter Virgil |
Explicație
În primul exemplu intrusul este Emilio deoarece divizorii lui 38 sunt 1, 2, 19 si 38. Suma acestora este 60 care este diferită de 45. Celelalte valori pot fi verificate după aceeași metodă.
