Diferente pentru problema/secvente3 intre reviziile #6 si #9

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="secvente3") ==
Fie A ~i~ un şir de numere naturale nenule definit astfel:
Fie {**A{~i~}**} un şir de numere naturale nenule definit astfel:
A ~1~ = a
A ~i~ = (A ~i-1~ × b) modulo P, pentru orice i > 1
A{~1~} = {**a**}
A{~i~} = (A{~i-1~} × {**b**} ) modulo {**P**} , pentru orice i > 1
Astfel şirul A poate fi definit de trei numere constante cunoscute: a, b şi P.
Astfel şirul A poate fi definit de trei numere constante cunoscute: {**a**}, {**b**} şi {**P**}.
h2. Cerinta
Pentru un şir cunoscut A să se raspundă la M întrebări (st, S) cu semnificaţia:
„Care este cel mai mare indice dr(≥st) astfel încât A ~st~ + A ~st+1~ + A ~st+2~ + … + A ~dr~ ≤ S ?”
Pentru un şir cunoscut A să se raspundă la {**M**} întrebări ({**st**}, {**S**}) cu semnificaţia:
„Care este cel mai mare indice {**dr**} (≥st) astfel încât A ~st~ + A ~st+1~ + A ~st+2~ + … + A ~dr~ ≤ S ?”
h2. Date de intrare
Fişierul de intrare $secvente3.in$ conţine pe prima linie numerele a, b, P şi M separate prin spaţiu. Următoarele M linii contin parametrii pentru fiecare întrebare st şi S separaţi prin spaţiu.
Fişierul de intrare $secvente3.in$ conţine pe prima linie numerele {**a**}, {**b**}, {**P**} şi {**M**} separate prin spaţiu. Următoarele {**M**} linii contin parametrii pentru fiecare întrebare {**st**} şi {**S**} separaţi prin spaţiu.
h2. Date de ieşire
În fişierul de ieşire $secvente3.out$ va conţine pe prima linie M numere: răspunsurile dr la întrebări în ordine, valori separate prin spaţiu.
În fişierul de ieşire $secvente3.out$ va conţine pe prima linie {**M**} numere: răspunsurile dr la întrebări în ordine, valori separate prin spaţiu.
h2. Restricţii
* M ≤ 10^4^
* 1 ≤ st ≤ 10^6^
* 0 < dr ≤ 10^7^, pentru orice întrebare
* 1 < a < b < P ≤ 10^9^
* 0 < S ≤ 10^15^
* 0 < dr ≤ 10^7^, pentru orice întrebare
* Pentru orice test numerele a, b şi P asigură că orice A ~i~ este nenul
* Pentru orice întrebare A ~st~ ≤ S
* Pentru orice test numerele a, b şi P asigură că orice A{~i~} este nenul
* Pentru orice întrebare A{~st~} ≤ S
* Atentie la limita de memorie
* Atentie la folosirea long long (C++) sau int64 (Pascal)
h3. Explicaţie
A = (2, 6, 4, 5, 1, 3 …)
A ~2~ + A ~3~ + A ~4~ = 6 + 4 + 5 = 15 ≤ 15
A ~4~ + A ~5~ = 5 + 1 = 6 ≤ 8
dar A ~4~ + A ~5~ + A ~6~ = 5 + 1 +  3 = 9 e deja > 8
A{~2~} + A{~3~} + A{~4~} = 6 + 4 + 5 = 15 ≤ 15
A{~4~} + A{~5~} = 5 + 1 = 6 ≤ 8
dar A{~4~} + A{~5~} + A{~6~} = 5 + 1 +  3 = 9 e deja > 8

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.