Se dau N puncte pe axa OX, numerotate de la 1 la N. Fiecare punct i se află la coordonata xi şi are o pondere wi. 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≤xi≤a+L
• wi•(a-xi), dacă xi<a
• wi•(xi-(a+L)), dacă xi>a+L
Coordonatele şi ponderile fiecărui punct se generează conform următorului algoritm (unde x1=0 şi w1, A, B, C1 şi D sunt date în fişierul de intrare): C=C1
for i=2 to N do
xi=xi-1+1+ (((xi-1• i) xor A) modulo B)
if (2•i≤N) then
k = 1
else
k = -1
wi=maxim(1, wi-1+k•(1+(((wi-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 w1. A treia linie conţine numerele întregi A, B, C1 ş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
1 ≤ N ≤ 1 000 000
0 ≤ L ≤ 100 000 000
1 ≤ w1, A, B, C1, D ≤ 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.
Exemple
center.in
center.out
Explicaţii
4 2
2
1 2 3 4
2.667
1.33333333
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.