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 expanding.in conţine pe prima linie numărul n, urmat pe a doua linie de şirul a.
Pe a treia linie se găseşte q, urmat de q linii cu câte un număr, valorile p ale query-urilor.
Date de ieşire
În fişierul de ieşire expanding.out afişaţi q linii, pe linia i afişând răspunsul de la al i-lea query.
Restricţii
- 1 ≤ n ≤ 1 000 000
- 1 ≤ ai ≤ n
- 1 ≤ q ≤ 1 000 000
- 1 ≤ p ≤ n
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 10 | n ≤ 500 şi q ≤ 500 |
| 2 | 10 | n ≤ 5000 şi q ≤ 10 |
| 3 | 15 | n ≤ 5000 şi q ≤ 5000 |
| 5 | 15 | n ≤ 100 000 şi q ≤ 10 |
| 5 | 25 | n ≤ 100 000 şi q ≤ 100 000 |
| 6 | 25 | n ≤ 1 000 000 şi q ≤ 1 000 000 |
Exemplu
| sandwich.in | sandwich.out |
|---|---|
| 8 2 1 3 4 6 3 2 1 8 1 2 3 4 5 6 7 8 | 7 6 6 5 5 6 6 7 |
Explicaţie
🤡🤡🤡
