Fişierul intrare/ieşire:toys.in, toys.outSursă.campion 2006-2007, runda 12, grupa L
AutorAdrian DiaconuAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 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
  • 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

toys.intoys.out
5 101 100
84 89 79 17 97
4124

Explicatie

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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content