Codrut Borcutean: Pagină nouă: == Cerinţa == Se dă un șir '''s''' care conține litere mici ale alfabetului englez, urmat de un număr natural '''k'''. Să se afișeze câte subsecvențe ale șirului '''s''' de lungime '''1''', '''2''', … '''k''' sunt palindromuri. == Date de intrare == Fișierul de intrare '''palpalin.txt''' conține pe prima linie un șir '''s''' și pe următoarea linie un număr natural '''k'''. == Date de ieșire == Fișierul de ieșire '''palpalout.txt''' va conține '''k''' lin...

2024-01-03T15:19:55Z

Pagină nouă: == Cerinţa == Se dă un șir '''s''' care conține litere mici ale alfabetului englez, urmat de un număr natural '''k'''. Să se afișeze câte subsecvențe ale șirului '''s''' de lungime '''1''', '''2''', … '''k''' sunt palindromuri. == Date de intrare == Fișierul de intrare '''palpalin.txt''' conține pe prima linie un șir '''s''' și pe următoarea linie un număr natural '''k'''. == Date de ieșire == Fișierul de ieșire '''palpalout.txt''' va conține '''k''' lin...

New page

== Cerinţa ==
Se dă un șir '''s''' care conține litere mici ale alfabetului englez, urmat de un număr natural '''k'''. Să se afișeze câte subsecvențe ale șirului '''s''' de lungime '''1''', '''2''', … '''k''' sunt palindromuri.
== Date de intrare ==
Fișierul de intrare '''palpalin.txt''' conține pe prima linie un șir '''s''' și pe următoarea linie un număr natural '''k'''.
== Date de ieșire ==
Fișierul de ieșire '''palpalout.txt''' va conține '''k''' linii. Pe linia '''i''' ('''1 ≤ i ≤ k''') se va găsi numărul de subsecvențe de '''i''' caractere care sunt palindromuri.
== Restricţii şi precizări ==
* '''1 &les; k &les; 1000'''
* șirul '''s''' are maxim '''20000''' de caractere
* Prin subsecvență a unui șir de caractere se înțelege o succesiune de unul sau mai multe caractere din șir aflate pe poziții consecutive.
* Un șir de caractere este palindrom dacă se citește la fel de la stânga la dreapta și de la dreapta la stânga.
== Exemplu 1 ==
; palpalin.txt'
eaaebeadaebcc
5
; palpalout.txt
Datele de intrare corespund restrictiilor impuse
13
2
2
1
2
<br>
== Exemplu 2 ==
; palpalin.txt'
eaaebeadaebcc
-5
; palpalout.txt
Datele de intrare nu corespund restrictiilor impuse
<br>
== Explicatie ==
Subsecvențe palindrom de lungime 1: '''e''', '''a''', '''a''', '''e''', '''b''', '''e''', '''a''', '''d''', '''a''', '''e''', '''b''', '''c''', '''c'''.

Subsecvențe palindrom de lungime 2: '''aa''', '''cc'''.

Subsecvențe palindrom de lungime 3: '''ebe''', '''ada'''.

Subsecvențe palindrom de lungime 4: '''eaae'''.

Subsecvențe palindrom de lungime 5: '''aebea''', '''eadae'''.

== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_palindrome(s):

#Verifică dacă un șir de caractere este palindrom.

return s == s[::-1]

def count_palindromic_subsequences(s, k):

#Numără subsecvențele palindromice de lungime 1, 2, ..., k ale unui șir.

counts = [0] * k
for length in range(1, k + 1):
for i in range(len(s) - length + 1):
if is_palindrome(s[i:i+length]):
counts[length-1] += 1
return counts

def main():
with open('palpalin.txt', 'r') as fin, open('palpalout.txt', 'w') as fout:
s = fin.readline().strip()
k = int(fin.readline().strip())

# Verifică dacă datele de intrare respectă restricțiile
if len(s) > 20000 or k < 1 or k > 1000:
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return

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

# Numără subsecvențele palindromice și scrie rezultatele în fișierul de ieșire
counts = count_palindromic_subsequences(s, k)
for count in counts:
fout.write(str(count) + '\n')

if __name__ == "__main__":
main()

</syntaxhighlight>

3492 - PalPal - Revision history