Fişierul intrare/ieşire:	toys.in, toys.out	Sursă	.campion 2006-2007, runda 12, grupa L
Autor	Adrian Diaconu	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.125 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Toys

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 d_i si t_i, cu semnificatia: d_i reprezinta distanta la care se afla fata de camera lui Gigel copilul i, iar t_i=1, in cazul in care copilul i transporta o jucarie din sufragerie spre camera lui Gigel, respectiv t_i=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 d₁=S si t₁=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 d_i si t_i se pot determina cu urmatoarele formule (in care valorile X, Y, Z, V sunt cunoscute):

• d_i = ( X * d_i-1 + Y * ( i - 1 ) ) % ( L - 1 ) + 1
• t_i = ( Z * d_i-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
• 1 ≤ N ≤ 2.000.000
• 1 ≤ L ≤ 2.000.000
• 1 ≤ X,Y,Z,V ≤ 2.000.000
• 1 ≤ 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

Explicatie

Exista 5 copii, lungimea holului este 101, iar numarul de jucarii este 100.
Configuratia initiala a celor 5 copii este:

• d₁= 84 t₁=1
• d₂=(89*84+79*1)%100+1=56 t₂=(17*84+97*1)%2=1
• d₃=(89*56+79*2)%100+1=43 t₃=(17*56+97*2)%2=0
• d₄=(89*43+79*3)%100+1=65 t₄=(17*43+97*3)%2=0
• d₅=(89*65+79*4)%100+1=2 t₅=(17*43+97*4)%2=1

Cum se trimit solutii?