Fişierul intrare/ieşire: | palindrom.in, palindrom.out | Sursă | Cerc informatică Vianu |
Autor | Catalin Francu, Cristian Francu | Adăugată de | |
Timp execuţie pe test | 0.2 sec | Limită de memorie | 2560 kbytes |
Scorul tău | N/A | Dificultate |
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.in | palindrom.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.