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