Dupa ce a dat o petrecere
la el acasa, Gigel impreuna cu colegii sai de gradinita trebuie sa duca toate
jucariile din sufragerie la el in camera. Pentru a ajunge din sufragerie in
camera lui Gigel, copiii trebuie sa strabata un hol de lungime
L.
Gigel are N
prieteni (pe care i-a numerotat de la 1
la N) si mai are de mutat M
jucarii. Prietenii sai au inceput deja treaba si se gasesc undeva intre sufragerie
si camera lui Gigel. Unii dintre ei au deja o jucarie de transportat, ceilalti
se intorc in sufragerie pentru a lua o noua jucarie.
Vom identifica pozitia de pe hol a unui copil prin distanta la care se afla
copilul de camera lui Gigel. Mai exact, pentru fiecare copil i
vom determina doua valori di
si ti, cu semnificatia:
di reprezinta distanta
la care se afla fata de camera lui Gigel copilul i,
iar ti=1, in cazul
in care copilul i transporta
o jucarie din sufragerie spre camera lui Gigel, respectiv ti=0
in cazul in care copilul i se
intoarce din camera lui Gigel catre sufragerie, fara nici o jucarie.
Fiecare copil duce
o jucarie in camera lui Gigel, apoi se intoarce in sufragerie pentru a lua o
noua jucarie repetand acest proces pana cand toate jucariile vor fi transportate.
Gigel analizeaza configuratia celor N
prieteni si observa ca d1=S
si t1=1 (adica primul
copil se afla la distanta S de
camera lui Gigel si transporta o jucarie). Pentru ceilalti copii (i=2,
3, ..., N)
valorile di si ti
se pot determina cu urmatoarele formule (in care valorile X,
Y, Z,
V sunt cunoscute):
di
= ( X * di-1 + Y * ( i - 1 ) ) % ( L - 1 ) + 1
ti = ( Z * di-1
+ V * ( i - 1 ) ) % 2
Prin a % b se intelege restul
impartirii lui a la b.
Cerinta
Ajutati-l pe Gigel sa determine
timpul minim in care toate jucariile vor fi duse inapoi in camera sa.
Date de intrare
Pe prima linie a fisierului
de intrare toys.in sunt scrise trei numere naturale: N, L si M
separate prin cate un spatiu. Pe urmatoarea linie se afla cinci numere naturale
S,X,Y,Z,V separate prin cate
un spatiu, avand semnificatia din enunt.
Date de iesire
Fisierul toys.out
va contine o singura linie pe care va fi scris timpul minim in care toate jucariile
vor fi transportate in camera lui Gigel.
Restrictii
1
<= M <= 2 000 000 000
0 <= N <= 2
000 000
0 <= L <= 2
000 000
0 <= X, Y, Z,
V <= 2 000 000
0 <= S <= L
Rezultatul se va incadra
in tipuri de date intregi pe 64 de biti.
Copiii se deplaseaza
o unitate de distanta intr-o unitate de timp, iar lasatul sau luatul unei
jucarii nu consuma timp.
Exemplu
toys.in
toys.out
Explicatie
5
101 100
84 89 79 17 97
4124
Exista
5 copii, lungimea holului
este 101, iar numarul de
jucarii este 100.Configuratia
initiala a celor 5 copii
este: d1=
84 t1=1
d2=(89*84+79*1)%100+1=56 t2=(17*84+97*1)%2=1
d3=(89*56+79*2)%100+1=43 t3=(17*56+97*2)%2=0
d4=(89*43+79*3)%100+1=65 t4=(17*43+97*3)%2=0
d5=(89*65+79*4)%100+1=2 t5=(17*43+97*4)%2=1
Diaconu
Adrian Paul Universitatea
Bucuresti, Facultatea de Matematica si Informatica ditzone@gmail.com