Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | expanding.in, expanding.out | Sursă | Junior Challenge 2025 |
| Autor | Muresan Luca Valentin | Adăugată de |  andrei iorgulescu •andreiiorgulescu |
| Timp execuţie pe test | 1 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Expanding
📖 Povestea reformulată în română
În Ţinutul Ooo, Finn şi Jake descoperă un şir magic de pietre strălucitoare aşezate în linie.
Fiecare piatră are o valoare (o culoare sau o energie), iar fiecare valoare apare de cel mult două ori în tot şirul.
ake, fiind elastic, poate alege o poziţie iniţială p din şir, şi începe o călătorie de extindere:
La început:
Intervalul [l, r] = [p, p] (adică doar piatra de la poziţia p).
Jake ţine în lăbuţă energia curentă c = valoarea pietrei de la p.
Reguli magice:
Jake poate schimba energia c în orice valoare pozitivă, dar asta costă 1 poţiune magică.
Dacă în stânga există o piatră cu energia c, atunci Jake poate sări la ea şi l scade cu 1.
Dacă în dreapta există o piatră cu energia c, atunci Jake se întinde până la ea şi r creşte cu 1.
Scopul aventurii:
Jake vrea să se întindă până acoperă întregul şir de pietre, adică [l, r] = [1, n].
Costul final f(p) este numărul minim de poţiuni magice (schimbări de energie) pe care Jake trebuie să le folosească pentru a reuşi.
✨ Sarcina ta
Ţi se dă lungimea şirului n.
Apoi urmează n numere pozitive (valorile pietrelor, fiecare apărând cel mult de două ori).
După aceea primeşti un număr q, adică numărul de încercări pe care Jake le face.
Urmează q poziţii iniţiale p.
Pentru fiecare dintre ele, trebuie să spui câte poţiuni magice minime are nevoie Jake ca să se întindă pe tot şirul.
Vrei să îţi rescriu şi input-output-ul în stilul poveştii (cu „Jake primeşte un şir de pietre…”, „Jake încearcă din poziţia…”, „Răspunde cu…”) sau păstrăm partea formală (n, array, q, queries) dar doar ambalată în poveste?
Date de intrare
Fişierul de intrare sandwich.in conţine numerele N, x, y, z şi a1. Şirul a este codificat astfel:
ai = (ai-1 * x + y) % z pentru orice 2 ≤ i ≤ N
Date de ieşire
În fişierul de ieşire sandwich.out afişaţi valoarea lui S modulo 109 + 7.
Restricţii
- 1 ≤ N ≤ 5 000 000
- 1 ≤ x, y ≤ 1 000 000 000
- 0 ≤ a1 < z ≤ 1 000 000 000
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 3 | N ≤ 15 |
| 2 | 16 | N ≤ 500 |
| 3 | 15 | N ≤ 2000 |
| 5 | 10 | N ≤ 200 000 şi z = 2 |
| 5 | 41 | N ≤ 200 000 |
| 6 | 15 | N ≤ 5 000 000 |
Exemplu
| sandwich.in | sandwich.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
