== include(page="template/taskheader" task_id="puncte3") ==
== include(page=“template/taskheader" task_id="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ă?
h2. 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 ( $X{~i~}$ fiind coordonata celui de-al $i$-lea punct $i = 1..N$):
$X{~1~} = 1, X{~i~} = (X{~i-1~} * A + B * i) mod C$ pentru $i = 2..N$
Fişierul de intrare $puncte3.in$ va conţine pe prima linie $T$, numărul de teste. În contiunare, fiecare test va avea o singură linie ce conţine numerele $N, A, B, C$.
h2. 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.
În fişierul de ieşire $puncte3.out$ ...
h2. Restricţii
* $T = 5$
* $1 ≤ M < N ≤ 10^5^$
* $1 ≤ A ≤ 1000$
* $1 ≤ B ≤ 10^10^$
* $1 ≤ C ≤ 10^15^$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. puncte3.in |_. puncte3.out |
| 1
5 2 2 1 9
| 3
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. 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.
...
== include(page="template/taskfooter" task_id="puncte3") ==
