Ramona Dragoș at 15:09, 6 January 2024

2024-01-06T15:09:02Z

← Older revision		Revision as of 15:09, 6 January 2024
Line 28:		Line 28:
	:2		:2
	<br>		<br>
			== Explicație ==
			:1. lmax(”aCCACCACaBa”)=6
			:2. lmax(”AAPAPAACCAA”)=7
			:3. lmax(”acaacc”)=4
			:4. lmax(”capac”)=5
			:5. lmax(”CACAACAACACCAACP”)=11

			Cele două secvenţe de lungime 11 sunt: (2,3) şi (5)
	== Exemplu 2 ==		== Exemplu 2 ==
	;secvpal1in.txt		;secvpal1in.txt

Ramona Dragoș: Pagină nouă: == Enunt == Pentru un şir de caractere S, vom nota cu lmax[S] lungimea maximă a unei secvenţe palindromice conţinută în şirul S. Astfel, pentru şirul S=”abAabaabC”, lmax[S]=4, iar pentru şirul S=”a”, lmax[S]=1. Prin secvenţa palindromică a unui şir S înţelegem un subşir de caractere aflate pe poziţii consecutive, ce formează un palindrom. == Cerința == Date fiind N şiruri de caractere S[1], S[2],…, S[n] şi o valoare naturală L, se cere să se d...

2023-12-31T13:52:07Z

Pagină nouă: == Enunt == Pentru un şir de caractere S, vom nota cu lmax[S] lungimea maximă a unei secvenţe palindromice conţinută în şirul S. Astfel, pentru şirul S=”abAabaabC”, lmax[S]=4, iar pentru şirul S=”a”, lmax[S]=1. Prin secvenţa palindromică a unui şir S înţelegem un subşir de caractere aflate pe poziţii consecutive, ce formează un palindrom. == Cerința == Date fiind N şiruri de caractere S[1], S[2],…, S[n] şi o valoare naturală L, se cere să se d...

New page

== Enunt ==
Pentru un şir de caractere S, vom nota cu lmax[S] lungimea maximă a unei secvenţe palindromice conţinută în şirul S. Astfel, pentru şirul S=”abAabaabC”, lmax[S]=4, iar pentru şirul S=”a”, lmax[S]=1.

Prin secvenţa palindromică a unui şir S înţelegem un subşir de caractere aflate pe poziţii consecutive, ce formează un palindrom.
== Cerința ==
Date fiind N şiruri de caractere S[1], S[2],…, S[n] şi o valoare naturală L, se cere să se determine numărul de secvenţe de şiruri de caractere de forma: S[i], S[i+1], … , S[j], cu i<=j, pentru care lmax[S[i]]+lmax[S[i+1]]+... +lmax[S[j]]=L.
== Date de intrare ==
Fișierul de intrare secvpal1in.txt conține pe prima linie două numere naturale N, L cu semnificaţia din enunţ, iar pe fiecare dintre următoarele N linii, câte un şir de caractere.
== Date de ieșire ==
Fișierul de ieșire secvpal1out.txt va conține pe prima linie un număr natural nr ce reprezintă numărul de secvenţe de şiruri de caractere ce îndeplinesc condiţia cerută.
== Restricții și precizări ==
*2 &les; N &les; 50 000;
*0 &les; nr &les; 10 000;
*1 &les; lungimea maximă a oricărui şir S[i] &les; 10 000, 1&les;i&les;N;
*1 &les; lungimea maximă a unei secvenţe palindromice lmax[S[i]] &les; 1 000;
*1 &les; (lungimea maximă şir S[i]) × N &les; 1 000 000;
*Cele N şiruri de caractere conţin doar caracterele ‘A’..’Z’, ’a’..’z’;
*Un palindrom este un şir de caractere care citit de la stânga la dreapta sau de la dreapta la stânga este acelaşi.
== Exemplu 1 ==
;secvpal1in.txt
:5 11
:aCCACCACaBa
:AAPAPAACCAA
:acaacc
:capac
:CACAACAACACCAACP
;secvpal1out.txt
:2
<br>
== Exemplu 2 ==
;secvpal1in.txt
: 0
;secvpal1out.txt
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#0713 - SecvPal1
def is_palindrome(s):
return s == s[::-1]

def calculate_lmax(s):
lmax = 0
current_length = 0

for i in range(len(s)):
current_length = 0
while i - current_length >= 0 and i + current_length < len(s) and s[i - current_length] == s[i + current_length]:
current_length += 1

lmax = max(lmax, current_length * 2 - 1)

return lmax

def read_input(file_name):
try:
with open(file_name, 'r') as file:
N, L = map(int, file.readline().split())
strings = [file.readline().strip() for _ in range(N)]

return N, L, strings
except Exception as e:
print(f"Nu au fost respectate cerintele impuse: {str(e)}")
return None

def write_output(file_name, result):
with open(file_name, 'w') as file:
if result is not None:
file.write(f"{result}\n")

def count_sequences(N, L, strings):
count = 0

for i in range(N):
for j in range(i, N):
lmax_sum = sum(calculate_lmax(s) for s in strings[i:j+1])
if lmax_sum == L:
count += 2

return count

def main(input_file, output_file):
result = read_input(input_file)
if result is not None:
N, L, strings = result
result = count_sequences(N, L, strings)
write_output(output_file, result)

if __name__ == "__main__":
main("secvpal1in.txt", "secvpal1out.txt")

</syntaxhighlight>

0713 - SecvPal1 - Revision history

Ramona Dragoș at 15:09, 6 January 2024