| Fişierul intrare/ieşire: | mutari.in, mutari.out | Sursă | Algoritmiada 2013, Runda 1 |
| Autor | Vlad Ionescu | Adăugată de |  Mihai-Alexandru Dusmanu •dushmi |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mutari
In timp ce se plictisea din cauza problemelor prea usoare de pe tabla din ora de matematica, Marian a descoperit un nou joc: plecand de la un sir de N numerele naturale A(1), A(2), ..., A(N), trebuie sa ajunga la sirul A(1), 0, ..., 0 efectuand efectuand una sau mai multe mutari. O mutare consta in alegerea unei pozitii K ( 1 ≤ K < N ) si apoi scaderea din A(K + 1) a valorii lui A(K). Numerele din sir nu au voie sa devina negative pe parcursul mutarilor. Nefiind insa foarte priceput la informatica, el s-a gandit sa va roage pe voi, prietenii lui, sa-i spuneti daca exista o succesiune de mutari care sa rezolve jocul.
Date de intrare
Fişierul de intrare mutari.in va contine pe prime linie N si pe linia a doua cele N numere naturale: A(1), A(2), ..., A(N).
Date de ieşire
În fişierul de ieşire mutari.out se va afisa pe prima linie numarul de mutari T necesar rezolvarii jocului, in cazul in care este posibil. Pe urmatoarele T linii se va afla cate un numar reprezentand pozitia K alesa pentru mutarea curenta. In cazul in care jocul nu are solutie, se va afisa pe primul rand -1.
Restricţii
- 1 ≤ N ≤ 100000
- 1 ≤ A(i) ≤ 2000000000
- Se garanteaza ca va exista solutie cu T ≤ 1000000.
- Nu se cere neaparat T minim. Orice solutie corecta este acceptata.
Exemplu
| mutari.in | mutari.out |
|---|---|
| 5 2 4 2 6 8 | 8 3 4 4 3 3 1 2 1 |
Explicaţie
2, 4, 2, 6, 8 -> 2, 4, 2, 4, 8 -> 2, 4, 2, 4, 4 -> 2, 4, 2, 4, 0 -> 2, 4, 2, 2, 0 -> 2, 4, 2, 0, 0 -> 2, 2, 2, 0, 0 -> 2, 2, 0, 0, 0 -> 2, 0, 0, 0, 0
Mai exista si alte succesiuni de mutari care duc la sirul 2, 0, 0, 0, 0.
