| Fișierul intrare/ieșire | palindrom.in, palindrom.out | Sursă | Cerc informatică Vianu |
|---|---|---|---|
| Autor | Cătălin Frâncu | Cristian Frâncu | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 0.2 sec | Limită de memorie | 2560 KB |
| Scorul tău | N/A | Dificultate |
  4
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
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.
