Editing 1413 - ConstructPalindrom

Mai sunt câteva săptămâni și vine Crăciunul. Ajuns într-un magazin de jucării, Robert îl roagă pe tatăl său să-i cumpere cea mai frumoasă mașină cu telecomandă. Tatăl său îi spune că nu a fost cuminte în timpul anului și nu merită această jucărie, însă după dispute intense acesta hotaraste să-i mai acorde o sansă, doar dacă va rezolva următoarea problema:

Având un string '''S''', putem să obținem un palindrom din acest șir ștergând un singur caracter?

Robert nu se prea descurca la algoritmică așa că vă roagă foarte mult să-i rezolvați problema pentru a se putea juca cu mașina cu telecomandă. În schimbul acestei mașini el vă va recompensa cu 100 puncte.
== Cerinţa ==
Find dat un string '''S''', se poate obține un palindrom din șirul inițial ștergând doar un singur caracter ?
== Date de intrare ==
Fişierul de intrare '''constructpalindromin.txt''' conţine pe prima linie o valoare '''T''' reprezentând numărul de teste. Pe următoarele T linii vom avea cate un string reprezentând întrebarea adresata lui Robert de către tatăl sau.
== Date de ieșire ==
Fişierul de ieşire '''constructpalindromout.txt''' va conține '''T''' linii cu răspunsul '''YES''' daca se poate obține un palindrom ștergând un singur caracter și '''NO''' dacă nu se poate obține.
== Restricţii şi precizări ==
* '''1 &les; T &les; 100'''
* Dimensiunea stringului '''&les; 100000'''
* Pentru 10% din punctaj dimensiunea stringului '''&les; 1000'''
* String-ul conține caractere de la '''a''' la '''z'''.
* Dimensiunea string-ului după ștergerea unui caracter va fi mai mică decât a fost înainte.
== Exemplu 1 ==
; constructpalindromin.txt
 4
 aaa
 abc
 abdbca
 abba
; constructpalindromout.txt
 Datele de intrare corespund restrictiilor impuse
 YES
 NO
 YES
 YES
<br>
== Exemplu 2 ==
; constructpalindromin.txt
 40000000
 aaa
 abc
 abdbca
 abba
; constructpalindromout.txt
 Datele de intrare nu corespund restrictiilor impuse
<br>
== Explicatie ==
Pentru primul exemplu ('''aaa'''): Putem șterge orice '''a''', string-ul rezultat este '''aa''', care este palindrom.

Pentru al doilea exemplu ('''abc'''): Nu este posibil să eliminăm exact un caracter și să obtinem un palindrom.

Pentru al treilea exemplu ('''abdbca'''): ștergem caracterul '''c''', string-ul rezultat este '''abdba''' care este palindrom.

Pentru exemplul al patrulea ('''abba'''): Ștergem '''b''', obținem '''aba''' care este palindrom.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_palindrome(s):
    # Funcția verifică dacă un șir este palindrom.

    return s == s[::-1]


def can_form_palindrome(s):
    # Funcția verifică dacă se poate forma un palindrom ștergând un singur caracter din șirul s.

    for i in range(len(s)):
        t = s[:i] + s[i + 1:]
        if is_palindrome(t):
            return True
    return False


def main():
    with open('constructpalindromin.txt', 'r') as fin, open('constructpalindromout.txt', 'w') as fout:
        t = int(fin.readline().strip())

        # Verificăm dacă numărul de teste respectă restricțiile
        if not (1 <= t <= 100):
            fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
            return

        fout.write("Datele de intrare corespund restrictiilor impuse\n")

        for _ in range(t):
            s = fin.readline().strip()

            # Verificăm dacă șirul respectă restricțiile
            if len(s) > 100000:
                fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
                return

            # Verificăm dacă se poate forma un palindrom și scriem rezultatul în fișierul de ieșire
            fout.write('YES\n' if can_form_palindrome(s) else 'NO\n')


if __name__ == "__main__":
    main()

</syntaxhighlight>