problema/center

Center

== include(page="template/taskheader" task_id="center") ==

Se dau $N$ puncte pe axa $OX$, numerotate de la $1$ la $N$. Fiecare punct $i$ se afla la coordonata $xi$ si are o pondere $wi$. 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:

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 ≤ xi ≤ a+L$
* $wi·(a-xi)$, daca $xi < a$
* $wi·(xi-(a+L))$, daca $xi > a+L$

* $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):
== code(pas) |

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

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)

   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)

==
h2. Cerinta

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

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

h2. Date de intrare

h2. 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 stanga al intervalului de lungime L pentru care se obtine aceasta distanta. Afisati capatul stanga cu cat mai multe zecimale (cel putin 8).

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$).

h2. Restrictii

* $4 ≤ n ≤ 10^200^$
* 1 ≤ N ≤ 1 000 000
* 0 ≤ L ≤ 100 000 000
* 1 ≤ w1, A, B, C1, D ≤ 100

* $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.

* Primiti punctajul corespunzator unui test daca pentru ambele cerinte diferenta absoluta dintre rezultatul corect si cel afisat este cel mult $0.01$.

h2. Exemplu

h3. 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.

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$.

== include(page="template/taskfooter" task_id="center") ==

public

task: center

3789