Fişierul intrare/ieşire:tombola.in, tombola.outSursăONI 2019 baraj gimnaziu
AutorDana LicaAdăugată demircea_007Mircea Rebengiuc mircea_007
Timp execuţie pe test4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Tombola (baraj gimnaziu)

Aflat într-o vizită cu părinţii, Iliuţă primeşte un bilet la tombolă pe care este scris un număr natural S. Pentru a câştiga un premiu, Iliuţă trebuie să afle, plecând de la numărul S, un număr câştigător X. Pentru a-l ajuta să ghicească numărul câştigător, mama îi spune lui Iliuţă că numărul S de pe biletul său este suma dintre numărul câştigător X şi toate numerele obţinute plecând de la numărul câştigător X, prin ştergerea cifrei unităţilor numărului X, apoi, succesiv, prin ştergerea cifrei unităţilor numărului obţinut la pasul anterior, până se ajunge la un număr de o singură cifră.

De exemplu, dacă numărul X este 2019, atunci din X se pot obţine după regula de mai sus trei numere: 201, 20 şi 2. Suma tuturor acestor numere este S = 2019 + 201 + 20 + 2 = 2242. Deci, dacă pe biletul lui Iliuţă se află numărul S = 2242, atunci numărul câştigător corespunzător lui S este X = 2019.

Din păcate, nu toate numerele naturale permit determinarea unui număr câştigător. De exemplu, pentru numărul 21 nu există niciun număr natural X din care să putem obţine 21 după regula descrisă de mama lui Iliuţă.

Cu ajutorul unui program a fost generat automat un şir de N numere, numerotate în ordinea generării S1, S2, ..., SN. Programul respectiv primeşte patru numere naturale A, B, C, D şi primul număr din şir S1. Al i-lea număr generat se obţine după regula Si = ((Si-1 % A) * B + C) % D, unde 1 < i ≤ N, iar a % b reprezintă restul împărţirii lui a la b (b ≠ 0).

Cerinţă

Cunoscându-se numerele naturale N, S1, A, B, C, D, scrieţi un program care rezolvă următoarele cerinţe:

  1. pentru fiecare dintre termenii şirului S1, S2, ..., SN, determină cel mai mare număr natural mai mic strict decât termenul respectiv, pentru care există un număr câştigător; programul va afişa restul împărţirii sumei numerelor obţinute la 1018 + 31;
  2. pentru fiecare dintre termenii şirului S1, S2, ..., SN, determină câte numere naturale mai mici sau egale cu termenul respectiv NU au număr câştigător; programul va afişa restul împărţirii sumei rezultatelor obţinute la 1018 + 31.

Date de intrare

Fişierul de intrare tombola.in conţinepe prima linie numărul natural p, reprezentând cerinţa care trebuie rezolvată (1 sau 2). Pe a doua linie se află, în această ordine, numerele naturale N S1 A B C D, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire tombola.out va conţine un singur număr natural care reprezintă rezultatul la cerinţa p.

Restricţii

  • 1N500 000
  • 1 < S1, C, D1017
  • 1 < A, B109
  • Se garantează că Si >1, oricare 1iN
  • Pentru teste valorând 50 de puncte cerinţa este 1.
  • Pentru 30% din numărul total de teste, N * D106 şi N * S1106 (50% dintre acestea fiind pentru cerinţa 1)
  • Pentru 60% din numărul total de teste, N30000 (50% dintre acestea fiind pentru cerinţa 1).

Exemple

tombola.intombola.outExplicatii
1
1 22 3 3 3 3
20
Se rezolvă cerinţa 1. Avem un singur termen în şir S1 = 22.
Numărul 20 este cel mai mare număr strict mai mic decât 22
care acceptă un număr câştigător ( X = 19 deoarece 20 = 19 + 1 ).
2
1 22 3 3 3 3
2
Se rezolvă cerinţa 2. Avem un singur termen în şir S1 = 22.
Există două numere mai mici sau egale cu 22
care NU acceptă număr câştigător, 10 şi respectiv 21.
1
3 12345678901234567 999999999 123456789 98765432109876543 1020304050607080
12805467424792840
 
2
3 98765432109876543 999999999 123456789 12345678901234567 1020304050607080
9912065223185559
 
Trebuie sa te autentifici pentru a trimite solutii. Click aici