Codrut Borcutean: Pagină nouă: 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 s...

2024-01-04T09:11:52Z

Pagină nouă: 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 s...

New page

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>

1413 - ConstructPalindrom - Revision history