Fişierul intrare/ieşire:mutari.in, mutari.outSursăAlgoritmiada 2013, Runda 1
AutorVlad IonescuAdăugată dedushmiMihai-Alexandru Dusmanu dushmi
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inmutari.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?