Fişierul intrare/ieşire:palindrom.in, palindrom.outSursăCerc informatică Vianu
AutorCatalin Francu, Cristian FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.2 secLimită de memorie2560 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Palindrom

La concursul naţional de palindromuri „Ala Bala” de la Anina, informaticiana Elisa Vasile propune următorul subiect: dându-se un şir de N litere, să se insereze cât mai puţine litere în el pentru a-l transforma în palindrom. Un palindrom este un şir care are aceeaşi valoare citit de la stânga la dreapta sau de la dreapta la stânga.

Date de intrare

Fişierul de intrare palindrom.in conţine pe prima linie lungimea şirului, N. Pe a doua linie apar N litere mici ale alfabetului latin, nedespărţite.

Date de ieşire

În fişierul de ieşire palindrom.out se va scrie, pe prima linie, numărul minim de inserţii necesare, K. Pe următoarele K linii se vor indica poziţia unei inserţii şi valoarea literei inserate, despărţite printr-un spaţiu.

Restricţii

  • 1 ≤ N ≤ 5.000
  • Poziţiile în şir sunt numerotate de la 0 la N - 1;
  • O inserare pe o poziţie egală cu lungimea şirului semnifică o adăugare la sfârşitul şirului;
  • Dacă există mai multe soluţii, oricare dintre ele este acceptabilă.

Exemplu

palindrom.inpalindrom.out
7
acdecba
2
1 b
5 d
5
abcdd
3
5 a
5 b
5 c

sau

3
5 c
6 b
7 a

Explicaţii

La testul 1, prin inserarea lui b la poziţia 1 obţinem şirul abcdecba. În acest şir, prin inserarea lui d la poziţia 5 obţinem şirul abcdedcba, care este palindrom. Ambele teste admit şi alte soluţii.

Trebuie sa te autentifici pentru a trimite solutii. Click aici