Fișierul intrare/ieșire interval1.in, interval1.out Sursă Olimpiada pe scoala 2015
Autor Valentina Preda Adăugată de avatar vmanz Victor Manz vmanz
Timp de execuție pe test 0.1 sec Limită de memorie 2048 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 .

Interval 1 (clasa a 10-a)

Pe axa 0X avem o mulțime cu N puncte cu abscisele numere naturale nenule. Pentru un număr natural nenul M să se determine lungimea minimă a unui interval închis care are capetele în două puncte distincte din mulțimea dată, cele două puncte având abscise care dau același rest la împarțirea cu M. (lungimea unui interval [a,b] este b-a).

Date de intrare

Din fișierul text interval1.in se citesc de pe prima linie două numere N și M cu semnificația din enunț și de pe urmatoarele N linii abscisele celor N puncte din mulțime.

Date de ieșire

În fișierul de ieșire interval1.out se va scrie pe prima linie lungimea minimă a unui interval cu capetele două numere distincte (din mulțime) care dau același rest la împarțirea cu M.

Restricții

  • 2 ≤ N ≤ 100 000
  • 2 ≤ M ≤ 100 000
  • 1 ≤ x[i] ≤ 1 000 000 000, unde x[i] sunt abscisele punctelor date
  • Pentru toate testele există două abscise care dau același rest la împarțirea cu M.

Exemplu

interval1.in interval1.out
7 3
17
3
25
5
26
9
28
3

Explicație

Intervalul de lungime minimă este [25, 28], de lungime 3. (25 si 28 dau acelasi rest la împarțirea la 3)

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

Indicii de rezolvare

Arată 5 categorii