Fișierul intrare/ieșire | numerediv.in, numerediv.out | Sursă | Olimpiada Cunoasterii |
---|---|---|---|
Autor | Mihai Bunget | Adăugată de | Bunget Mihai • mihaibun |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Numerediv (clasele 5-6)
Dorel avea N numere naturale și nu știa ce să facă cu ele. Noroc cu Tinel care i-a mai oferit un număr P și i-a adresat următoarea întrebare: Care este cel mai mic număr K de numere ce trebuie luate (la întâmplare) dintre cele N date astfel încât să fim siguri că printre numerele luate există două având diferența divizibilă cu P? Dorel a răspuns : Nu știu ! Vă rog să-l ajutați pe Dorel să afle răspunsul.
Date de intrare
Fișierul de intrare numerediv.in conține pe prima linie numerele N și P separate prin spațiu, iar pe linia a doua cele N numere ale lui Dorel separate prin spațiu.
Date de ieșire
În fișierul de ieșire numerediv.out se va scrie numărul K cerut.
Restricții
- 3 ≤ N ≤ 100.000
- 2 ≤ P < 10.000
- P < N
- numerele lui Dorel sunt mai mici decât 2.000.000.000
Exemplu
numerediv.in | numerediv.out |
---|---|
5 2 17 876 3425 240 9880 |
3 |
Explicație
Trebuie să fim siguri că printre numerele luate se găsesc două cu diferența divizibilă cu 2. Dacă luăm numai două numere, de exemplu pe 17 și 876, diferența lor nu este divizibilă cu 2. Dacă luăm trei numere vom avea sigur două numere pare, deci diferența lor va fi divizibilă cu 2. Astfel că avem K=3.