Diferențe pentru problema/tombola între reviziile #11 si #26

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$.

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 $*S[~1~]*, *S[~2~]*,  ..., *S[~N~]*$. Programul respectiv primește patru numere naturale $*A*, *B*, *C*, *D*$ și primul număr din șir *S[~1~]*. Al [$i$]-lea număr generat se obține după regula $*Si* = (([*S[~i-1~]*] % *A* ) * *B* + *C*) % *D*$, unde $1 < i ≤ *N*$, iar $a % b$ reprezintă restul împărțirii lui $a$ la $b (b ≠ 0)$.

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

h2. 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 10[^18^] + 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 10[^18^] + 31.

Cunoscându-se numerele naturale *N*, *S[~1~]*, *A*, *B*, *C*, *D*, scrieți un program care rezolvă următoarele cerințe:
 
# pentru fiecare dintre termenii șirului *S[~1~]*, *S[~2~]*, ..., *S[~N~]*, 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 $10[^18^] + 31$;
# pentru fiecare dintre termenii șirului *S[~1~]*, *S[~2~]*, ..., *S[~N~]*, 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 $10[^18^] + 31$.

h2. 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.

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* *S[~1~]* *A* *B* *C* *D*, separate prin câte un spațiu.

h2. Date de ieșire

h2. Restricții

* $1 ≤ N ≤ 500000$
* $1 < S1, C, D ≤ 10[^17^]$
* $1 < A, B, ≤ 10[^9^]$

* $1$ ≤ *N* ≤ $500 000$
* $1$ < *S[~1~]*, *C*, *D* ≤ $10[^17^]$
* $1$ < *A*, *B* ≤ $10[^9^]$
* Se garantează că *S[~i~]* >1, oricare $1$ ≤ *i* ≤ *N*
* Pentru teste valorând 50 de puncte cerința este 1.
* Pentru 30% din numărul total de teste, *N* * *D* ≤ $10[^6^]$ și *N* * *S[~1~]* ≤ $10[^6^]$ (50% dintre acestea fiind pentru cerința 1)
* Pentru 60% din numărul total de teste, *N* ≤ $30000$ (50% dintre acestea fiind pentru cerința 1).

h2. Exemple

| 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 ).|

| Se rezolvă cerința 1. Avem un singur termen în șir *S[~1~]* = 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.|
 
table(example).
|_. tombola.in |_. tombola.out |

| Se rezolvă cerința 2. Avem un singur termen în șir *S[~1~]* = 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|

|12805467424792840
| 
|

|2
3 98765432109876543 999999999 123456789 12345678901234567 1020304050607080

|9912065223185559|
 

|9912065223185559
| 
|

== include(page="template/taskfooter" task_id="tombola") ==