Ovi a inventat un joc matematic.
El marcheaza pe axa Ox numerele naturale de la 0
la 1000 si pune la coordonata
0 un pion. Apoi considera 2
numere naturale nenule a si b
cu a>b.
In timpul jocului sunt permise doar doua tipuri de mutari: deplasarea pionului
pe axa Ox spre dreapta cu a pozitii
sau deplasarea sa spre stânga cu b
pozitii.
Astfel, daca pionul se afla in punctul de coordonata p,
atunci pionul se muta fie in punctul de coordonata p+a,
fie in punctul de coordonata p-b
(cu conditia ca p-b>=0).
Ovi a determinat pentru perechea a,
b considerata o valoare optima
c, notata optim(a,b),
ca fiind cea mai mica valoare c
cu proprietatea ca, plecând cu pionul din coordonata 0,
sa ajunga utilizând cele doua tipuri de mutari în pozitia c
si înapoi la 0, fara a depasi
prin aceste mutari intervalul [0,c].
De exemplu, optim(3,2)=4,
mutarile fiind a, b,
a, b,
b, adica din 0
salt în dreapta cu a=3 pozitii
la coordonata 3, apoi salt în
stânga la coordonata 1, salt
în dreapta la coordonata 4, salt
în stânga la coordonata 2, salt
în stânga la coordonata 0. Pentru
nicio valoare c mai mica decât
4 nu se poate ajunge de la 0
la c si înapoi la 0,
trecand doar prin puncte cu coordonate din intervalul [0,
c].
Cerinta
Dat fiind un sir de N perechi
(a1, b1),
(a2, b2),
..., (aN, bN),
precum si doua valori naturale X
si Y (X<Y),
sa se determine o secventa de Lg=Y-X+1
perechi din acest sir (sa o notam (ai,
bi), (ai+1,
bi+1), ..., (ai+Lg-1,
bi+Lg-1)) cu proprietatea
ca pentru fiecare numar natural c
din intervalul [X, Y]
exista un unic i<=j<=i+Lg-1,
astfel încât c=optim(aj,bj).
Daca exista mai multe solutii, se va determina secventa cu pozitia de început
i minima.
Date de intrare
Fisierul axa.in contine pe prima
linie numerele naturale N, X
si Y, separate prin câte un spatiu,
iar pe fiecare dintre urmatoarele N
linii câte doua numere naturale a,
b separate printr-un spatiu,
cu semnificatia din enunt.
Date de iesire
Fisierul axa.out va contine o
singura linie pe care va fi scris un singur numar natural, reprezentând pozitia
de început a secventei cerute.
Restrictii si precizari
3 <= N <= 100 000
6 <= X < Y <= 1000
Pentru orice pereche a b, 1<=
b < a<= 1000
Perechile din sir sunt numerotate de la 1
la N.
Pentru datele de intrare va exista întotdeauna solutie.
Exemplu
axa.in
axa.out
Explicatie
9 6 8
7 5
8 2
7 2
6 2
8 2
5 3
7 2
100 1
7 5
4
Se
da un sir de N=9 perechi.
Trebuie gasita o secventa de Y-X+1=8-6+1=3
perechi care au valori optime distincte din intervalul [6,8].
optim(7,5)=11
optim(8,2)=8
optim(7,2)=8
optim(6,2)=6
optim(8,2)=8
optim(5,3)=7
optim(7,2)=8
optim(100,1)=100
optim(7,5)=11
Observam ca secventa formata din perechile (6,2),
(8,2), (5,3)
este solutia problemei, pozitia de început a acestei secvente fiind 4.
Dan Pracsiu
Gr. Sc. Ind. "Stefan Procopiu" Vaslui
Contact: dpracsiu@yahoo.com