Fişierul intrare/ieşire:aniversare.in, aniversare.outSursăad-hoc
AutorTeodor PlopAdăugată deteodor94Teodor Plop teodor94
Timp execuţie pe test0.1 secLimită de memorie1024 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Aniversare

Cu ocazia aniversarii sale, Amalia doreste sa isi serveasca prietenii dintr-o cutie cu N bomboane. Cutia este impartita in 1xN patratele ( 1 linie, N coloane ), iar bomboanele sunt de doua feluri: albe si negre.

Avand simtul estetic dezvoltat, Amalia se gandeste sa aranjeze frumos aceste bomboane. Ea isi doreste ca imaginea cutiei de bomboane sa fie una "palindromica". Mai precis, cutia de bomboane trebuie sa arate la fel si in cazul in care este rotita cu 180 grade.

Pentru a isi etala abilitatile de estetician profesionist, Amalia are la dispozitie urmatoarea operatie:

  • Se interschimba o bomboana alba de pe pozitia i cu o bomboana neagra de pe pozitia j.

Fiind insa aniversarea ei, Amalia este foarte emotionata si nu isi poate duce singura la capat misiunea. De aceea, ea va roaga pe voi sa ii spuneti care este numarul minim de operatii necesare si de asemenea, ce operatii trebuie efectuate pentru a obtine o cutie de bomboane palindromica.

Operatiile vor fi afisate sub forma x y, reprezentand interschimbarea bomboanei de pe pozitia x cu cea de pe pozitia y.

Date de intrare

Fişierul de intrare aniversare.in contine pe prima linie numarul natural N. Pe urmatoarea linie se afla un sir de N valori binare ( 0 si 1 ) astfel:

  • v[i] = 0 daca pe pozitia i se afla o bomboana alba;
  • v[i] = 1 daca pe pozitia i se afla o bomboana neagra.

Date de ieşire

În fişierul de ieşire aniversare.out se va afla pe prima linie un singur numar natural MIN reprezentand numarul minim de mutari necesare pentru a obtine o aranjare panlindromica a bomboanelor. Pe urmatoarele MIN linii se vor afla cate 2 numere naturale x si y, separate intre ele printr-un spatiu, cu semnificatia din enunt. In cazul in care exista mai multe solutii se va afisa oricare dintre acestea. In cazul in care nu exista solutie, se va afisa -1.

Restricţii

  • 1 ≤ N ≤ 100.000
  • Bomboanele se numeroteaza incepand cu pozitia 1
  • Nu conteaza ordinea afisarii operatiilor

Exemplu

aniversare.inaniversare.outExplicatie
7
1 1 0 0 1 1 0
1
1 3
Se poate interschimba bomboana din prima pozitie cu cea din a treia.
Trebuie sa te autentifici pentru a trimite solutii. Click aici