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
În Ţinutul 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.
În mod important, 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 intr-o pozitie adiacenta, daca aceasta exista in sir, aceasta putand fi vizitata sau nu anterior.
- pentru un ban, ei pot schimba puterea potiunii c la orice valoare pozitiva.
- o mutare intr-o pozitie vizitata este mereu posibila si nu are niciun efect
- pentru a vizita o pozitie nevizitata, trebuie sa aiba puterea potiunii c egala cu valoarea pozitiei in care merg.
- cand ajung intr-o pozitie noua, ei colecteaza piatra din acea pozitie.
Definim f(p) ca fiind numarul minim de bani de care au nevoie cei doi pentru a putea colecta toate pietrele, daca pornesc in pozitia p cu c = ap.
Vi se dau n, sirul a de n elemente si q query-uri, la fiecare primind o pozitie p si trebuind sa afisati 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 | 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
🤡🤡🤡
