Fişierul intrare/ieşire:puncte3.in, puncte3.outSursăONIS 2014, Runda 3
AutorTudose Vlad Andrei, Vlad ManeaAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.4 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Puncte3

Avem N puncte pe o dreaptă orizontală. Vrem să desenăm M segmente pe această dreaptă astfel încât fiecare punct să fie conţinut de cel puţin un segment.
Care este lungimea minimă posibilă pentru segmentul de lungime maximă?

Date de intrare

Fişierul de intrare puncte3.in conţine pe prima linie T, numărul de teste. În contiunare, fiecare test are o singură linie ce conţine numerele naturale N, M, A, B, C. N şi M au semnificaţia din enunţ. Coordonatele celor N puncte vor fi generate folosind următoarele relaţii ( Xi fiind coordonata celui de-al i-lea punct i = 1..N):

X1 = 1, Xi = (Xi-1 * A + B * i) mod C pentru i = 2..N

Date de ieşire

În fişierul de ieşire puncte3.out se va afişa pe câte o linie rezultatul cerut pentru fiecare din cele T teste.

Restricţii

  • T = 5
  • 1 ≤ M < N ≤ 105
  • 1 ≤ A ≤ 1000
  • 1 ≤ B ≤ 1010
  • 1 ≤ C ≤ 1015

Exemplu

puncte3.inpuncte3.out
1
5 2 2 1 9
3

Explicaţie

Coordonatele punctelor sunt: 1, 4, 2, 8, 3. O soluţie posibilă este să folosim segmentele [1, 4] si [8, 8]. Lungimea segmentului maxim este 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content