Fişierul intrare/ieşire:	center.in, center.out	Sursă	Lot Iasi 2008, Baraj 4
Autor	Mugurel Ionut Andreica	Adăugată de	Pripoae Teodor Anton •toni2007
Timp execuţie pe test	0.4 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Center

Se dau N puncte pe axa OX, numerotate de la 1 la N. Fiecare punct i se afla la coordonata x_i si are o pondere w_i. Dorim sa amplasam pe axa OX un interval inchis de lungime L, astfel incat maximul dintre distantele ponderate de la puncte la interval sa fie minim (aceasta valoare se numeste distanta mini-maxima). Distanta de la un punct i la un interval [a,a+L] se defineste in felul urmator:

• 0, daca a ≤ x_i ≤ a+L
• w_i·(a-x_i), daca x_i < a
• w_i·(x_i-(a+L)), daca x_i > a+L

Coordonatele si ponderile fiecarui punct se genereaza conform urmatorului algoritm (unde x1=0 si w1, A, B, C1 si D sunt date in fisierul 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)

Cerinta

Determinati distanta mini-maxima, precum si valoarea capatului stang al intervalului pentru care se obtine aceasta distanta.

Date de intrare

Prima linie a fisierului de intrare center.in contine numerele intregi N si L. A doua linie contine numarul intreg w1. A treia linie contine numerele intregi A, B, C1 si D. Numerele de pe aceeasi linie sunt separate prin cate un spatiu.

Date de iesire

Prima linie a fisierului de iesire center.out va contine distanta mini-maxima pentru setul de puncte generat, iar a doua linie va contine capatul stang al intervalului de lungime L pentru care se obtine aceasta distanta. Afisati capatul stang cu cat mai multe zecimale (cel putin 8).

Restrictii

• 1 ≤ N ≤ 1 000 000
• 0 ≤ L ≤ 100 000 000
• 1 ≤ w1, A, B, C1, D ≤ 100
• Nu se urmareste gasirea vreunei proprietati speciale a algoritmului de generare care sa va ajute sa rezolvati problema (insa, daca gasiti o astfel de proprietate, o puteti folosi).
• Primiti punctajul corespunzator unui test daca pentru ambele cerinte diferenta absoluta dintre rezultatul corect si cel afisat este cel mult 0.01.

Exemplu

Explicatie

Coordonatele celor 4 puncte sunt: 0, 2, 4, 6. Ponderile celor 4 puncte sunt: 2, 5, 2, 1. Distanta mini-maxima este 2.667 si se obtine pentru intervalul [1.333, 3.333] (avand lungimea L=2). Distantele de la cele 4 puncte la interval sunt: 2.667, 0, 1.333, 2.667.

Cum se trimit solutii?