Fișierul intrare/ieșire numerediv.in, numerediv.out Sursă Olimpiada Cunoasterii
Autor Mihai Bunget Adăugată de avatar mihaibun Bunget Mihai mihaibun
Timp de execuție pe test 0.1 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii