Problem 2322: center

Se dau $N$ puncte pe axa OX, numerotate de la $1$ la $N$ . Fiecare punct $i$ se află la coordonata $x_i$ şi are o pondere $w_i$ . Dorim să amplasam pe axa OX un interval închis de lungime $L$ , astfel încât maximul dintre distanţele ponderate de la puncte la interval să fie minim (această valoare se numeşte distanţa mini-maximă). Distanţa de la un punct $i$ la un interval $[a,a+L]$ se defineşte în felul următor:

$0$ , dacă $a \leq x_i \leq a+L$
$w_i \cdot (a-x_i)$ , dacă $x_i<a$
$w_i \cdot (x_i-(a+L))$ , dacă $x_i>a+L$

Coordonatele şi ponderile fiecărui punct se generează conform următorului algoritm (unde $x_1=0$ şi $w_1, A, B, C_1$ şi $D$ sunt date în fişierul de intrare):

C = C1
for i = 2 to N do
    x[i] = x[i-1] + 1 + (((x[i-1]· i) xor A) modulo B)
   if (2·i <= N) then
      k = 1
   else
      k = -1
   w[i] = maxim(1, w[i-1] + k·(1 + (((w[i-1]·(i + C)) xor (D·i)) modulo D)))
   C = 1 + ((((C·C) modulo D)·i) modulo D)

Cerinţă

Determinaţi distanţa mini-maximă, precum şi valoarea capătului stânga al intervalului pentru care se obţine această distanţă.

Date de intrare

Prima linie a fişierului de intrare center.in conţine numerele întregi $N$ şi $L$ . A doua linie conţine numărul întreg $w_1$ . A treia linie conţine numerele întregi $A, B, C_1$ şi $D$ . Numerele de pe aceeaşi linie separate prin câte un spaţiu.

Date de ieșire

Prima linie a fişierului de ieşire center.out va conţine distanţa mini-maximă pentru setul de puncte generat, iar a doua linie va conţine capătul stânga al intervalului de lungime $L$ pentru care se obţine această distanţă. Afişaţi capătul stânga cu cât mai multe zecimale (cel puţin $8$ ).

Restricții și precizări

$1 \leq N \leq 1 \ 000 \ 000$ ;
$0 \leq L \leq 100 \ 000 \ 000$
$1 \leq w_1, A, B, C_1, D \leq 100$
Nu se urmăreşte găsirea vreunei proprietăţi speciale a algoritmului de generare care să vă ajute să rezolvaţi problema (însă, dacă găsiţi o astfel de proprietate, o puteţi folosi).
Primiţi punctajul corespunzător unui test dacă pentru ambele cerinţe diferenţa absolută dintre rezultatul corect şi cel afişat este cel mult $0.01$ .

Exemplu

center.in

4 2
2
1 2 3 4

center.out

2.667
1.33333333

Explicație

Coordonatele celor $4$ puncte sunt: $0, 2, 4, 6$ . Ponderile celor $4$ puncte sunt: $2, 5, 2, 1$ . Distanţa mini-maximă este $2.667$ şi se obţine pentru intervalul $[1.333, 3.333]$ (având lungimea $L=2$ ). Distanţele de la cele $4$ puncte la interval sunt: $2.667, 0, 1.333, 2.667$ .

center