== include(page="template/taskheader" task_id="expanding") ==
📖 Povestea reformulată în română
!>problema/expanding?poza_expand2.png!
Î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.
În Tărâmul Ooo, Finn şi Jake descoperă un şir magic de pietre strălucitoare aşezate în linie.
Fiecare piatră are o valoare, valori pe care le vom reprezenta cu un şir $a$ de $n$ elemente. **Nu există trei pietre care să aibă aceeaşi valoare**.
Încercând să colecteze toate pietrele, cei doi se vor mişca după următoarele reguli:
* Ei pornesc la o poziţie $p$, cu o poţiune de putere $c = a{~p~}$.
* La un pas, ei se pot muta doar într-o poziţie adiacentă, dacă aceasta există în şir, aceasta putând fi vizitată sau nu anterior.
* O mutare într-o poziţie vizitată anterior este mereu posibilă şi nu are niciun efect.
* Pentru a vizita o poziţie nevizitată, trebuie să aibă puterea poţiunii $c$ egală cu valoarea poziţiei în care merg.
* Pentru un ban, ei pot schimba puterea poţiunii $c$ la orice valoare pozitivă.
* Când ajung într-o poziţie nouă, ei colectează piatra din acea poziţie.
Definim $f(p)$ ca fiind numărul minim de bani de care au nevoie cei doi pentru a putea colecta toate cele $n$ pietre, dacă pornesc în poziţia $p$ cu $c = a{~p~}$.
Se dau $n$, şirul $a$ de $n$ elemente şi $q$ query-uri; pentru fiecare primiţi o poziţie $p$ şi trebuie să afişaţi $f(p)$.
h2. 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.
h2. 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.
h2. Restricţii
* $1 ≤ n ≤ 1 000 000$
* $1 ≤ a{~i~} ≤ n$
* $1 ≤ q ≤ 1 000 000$
* $1 ≤ p ≤ n$
|_. # |_. Punctaj |_. Restricţii |
| 1 | 8 | $n ≤ 500$ şi $q ≤ 500$ |
| 2 | 9 | $n ≤ 5000$ şi $q ≤ 10$ |
| 3 | 15 | $n ≤ 5000$ şi $q ≤ 5000$ |
| 5 | 27 | $n ≤ 100 000$ şi $q ≤ 10$ |
| 5 | 18 | $n ≤ 100 000$ şi $q ≤ 100 000$ |
| 6 | 23 | $n ≤ 1 000 000$ şi $q ≤ 1 000 000$ |
h2. Exemplu
table(example). |_. expanding.in |_. expanding.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
|
h3. Explicaţie
$f(1) = 7$. Un şir de mutări posibil este:
|_. Poziţie |_. Poţiune |_. Cost|
| 1 | 2 | Costul iniţal este 0 |
| 1 | 1 | 1 (am schimbat poţiunea din 2 în 1) |
| 2 | 1 | 1 |
| 2 | 3 | 2 (am schimbat poţiunea din 1 în 3) |
| 3 | 3 | 2 |
| 3 | 4 | 3 (am schimbat poţiunea din 3 în 4) |
| 4 | 4 | 3 |
| 4 | 6 | 4 (am schimbat poţiunea din 4 în 6) |
| 5 | 6 | 4 |
| 5 | 3 | 5 (am schimbat poţiunea din 6 în 3) |
| 6 | 3 | 5 |
| 6 | 2 | 6 (am schimbat poţiunea din 3 în 2) |
| 7 | 2 | 6 |
| 7 | 1 | 7 (am schimbat poţiunea din 2 în 1) |
| 8 | 1 | 7 |
$f(4) = 5$. Un şir de mutări posibil este:
|_. Poziţie |_. Poţiune |_. Cost|
| 4 | 4 | Costul iniţal 0 |
| 4 | 6 | 1 (am schimbat poţiunea din 4 în 6) |
| 5 | 6 | 1 |
| 5 | 3 | 2 (am schimbat poţiunea din 6 în 3) |
| 6 | 3 | 2 |
| 5 | 3 | 2 (observaţi cum aici am mers la stânga, lucru care este permis deoarece am vizitat deja aceasta pozitie) |
| 4 | 3 | 2 |
| 3 | 3 | 2 |
| 3 | 1 | 3 (am schimbat poţiunea din 3 în 1) |
| 2 | 1 | 3 |
| 2 | 2 | 4 (am schimbat poţiunea din 1 în 2) |
| 1 | 2 | 4 |
| 2 | 2 | 4 |
| 3 | 2 | 4 |
| 4 | 2 | 4 |
| 5 | 2 | 4 |
| 6 | 2 | 4 |
| 7 | 2 | 4 |
| 7 | 1 | 5 (am schimbat poţiunea din 2 în 1) |
| 8 | 1 | 5 |
Jake, 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?
== include(page="template/taskfooter" task_id="expanding") ==
