.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » center

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
center


Timp maxim de execuţie / test:
1.4s
Memorie totala disponibilă / stivă:
96MB / 32MB

Se dau N puncte pe axa OX, numerotate de la 1 la N. Fiecare punct i se află la coordonata xi şi are o pondere wi. Dorim să amplasam pe axa OX un interval închis de lungime L, astfel încât maximul dintre distanţele ponderate de la puncte la interval să fie minim (această valoare se numeşte distanţa mini-maximă). Distanţa de la un punct i la un interval [a,a+L] se defineşte în felul următor:
0, dacă a≤xi≤a+L
wi•(a-xi), dacă xi<a
wi•(xi-(a+L)), dacă xi>a+L
Coordonatele şi ponderile fiecărui punct se generează conform următorului algoritm (unde x1=0 şi w1, A, B, C1 şi D sunt date în fişierul de intrare):
C=C1
for i=2 to N do
xi=xi-1+1+ (((xi-1• i) xor A) modulo B)
if (2•i≤N) then
k = 1
else
k = -1
wi=maxim(1, wi-1+k•(1+(((wi-1•(i + C)) xor (D•i)) modulo D)))
C=1+((((C•C) modulo D)•i) modulo D)

Cerinţă

Determinaţi distanţa mini-maximă, precum şi valoarea capătului stânga al intervalului pentru care se obţine această distanţă.

Date de intrare

Prima linie a fişierului de intrare center.in conţine numerele întregi N şi L. A doua linie conţine numărul întreg w1. A treia linie conţine numerele întregi A, B, C1 şi D. Numerele de pe aceeaşi linie separate prin câte un spaţiu.

Date de ieşire

Prima linie a fişierului de ieşire center.out va conţine distanţa mini-maximă pentru setul de puncte generat, iar a doua linie va conţine capătul stânga al intervalului de lungime L pentru care se obţine această distanţă. Afişaţi capătul stânga cu cât mai multe zecimale (cel puţin 8).

Restricţii

1 ≤ N ≤ 1 000 000
0 ≤ L ≤ 100 000 000
1 ≤ w1, A, B, C1, D ≤ 100

Nu se urmăreşte găsirea vreunei proprietăţi speciale a algoritmului de generare care să vă ajute să rezolvaţi problema (însă, dacă găsiţi o astfel de proprietate, o puteţi folosi).
Primiţi punctajul corespunzător unui test dacă pentru ambele cerinţe diferenţa absolută dintre rezultatul corect şi cel afişat este cel mult 0.01.

Exemple

center.incenter.outExplicaţii
4 2 2 1 2 3 4 2.667 1.33333333 Coordonatele celor 4 puncte sunt: 0, 2, 4, 6. Ponderile celor 4 puncte sunt: 2, 5, 2, 1. Distanţa mini-maximă este 2.667 şi se obţine pentru intervalul [1.333, 3.333] (având lungimea L=2). Distanţele de la cele 4 puncte la interval sunt: 2.667, 0, 1.333, 2.667.

autor: Mugurel Ionuţ Andreica
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor