| 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
Î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 = ap.
- 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 = ap.
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).
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 | 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 |
Exemplu
| 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 |
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 |
