Fişierul intrare/ieşire:center.in, center.outSursăLot Iasi 2008, Baraj 4
AutorMugurel Ionut AndreicaAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.8 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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

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

center.incenter.out
4 2
2
1 2 3 4
2.667
1.33333333

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content