Fişierul intrare/ieşire:numerediv.in, numerediv.outSursăOlimpiada Cunoasterii
AutorBunget MihaiAdăugată demihaibunBunget Mihai mihaibun
Timp execuţie pe test0.1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.innumerediv.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 sa te autentifici pentru a trimite solutii. Click aici