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

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

Derminati distanta mini-maxima, precum si valoarea capatului stanga 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

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.

Restrictii

• 4 ≤ n ≤ 10²⁰⁰

Exemplu

Cum se trimit solutii?