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):

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

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.

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.

h2. Date de iesire

Fisierul de iesire $euclid4.out$ va contine pe prima linie numarul maxim de pasi determinat. A doua linie va contine un numar natural $a$ reprezentand primul numar al perechii minime identificate, iar pe a treia linie se va scrie numarul $b$ reprezentand al doilea numar din pereche.

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

h2. Exemplu

table(example). |_. euclid4.in |_. euclid4.out |
| 8
| 5
  5
  8
|
| 12345678910
| 48
  4807526976
  7778742049

table(example). |_. center.in |_. center.out |
| 4 2
  2
  1 2 3 4
| 2.667
  1.33333333

|

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

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$.
 
== include(page="template/taskfooter" task_id="center") ==

public

task: center

3789