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 ⩽ T ⩽ 100
• Dimensiunea stringului ⩽ 100000
• Pentru 10% din punctaj dimensiunea stringului ⩽ 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

Exemplu 2

constructpalindromin.txt

40000000
aaa
abc
abdbca
abba

constructpalindromout.txt

Datele de intrare nu corespund restrictiilor impuse

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>