Cristina94: Pagină nouă: ==Enunţ== Definim un număr liber de pătrate ca fiind un număr natural care nu are ca divizor niciun pătrat perfect mai mare ca 1. Prin convenție, 1 este considerat liber de pătrate. Așadar, șirul numerelor libere de pătrate este: 1,2,3,5,6,7,10,11,13,14,15,17, ... Se consideră un șir de N numere naturale X[i], 1 ≤ i ≤ N, unde N este un număr natural. O secvență este un subșir format din numere aflate pe poziții consecutive în șirul dat. Definim o bise...

2024-03-28T11:05:43Z

Pagină nouă: ==Enunţ== Definim un număr liber de pătrate ca fiind un număr natural care nu are ca divizor niciun pătrat perfect mai mare ca 1. Prin convenție, 1 este considerat liber de pătrate. Așadar, șirul numerelor libere de pătrate este: 1,2,3,5,6,7,10,11,13,14,15,17, ... Se consideră un șir de N numere naturale X[i], 1 ≤ i ≤ N, unde N este un număr natural. O secvență este un subșir format din numere aflate pe poziții consecutive în șirul dat. Definim o bise...

New page

==Enunţ==
Definim un număr liber de pătrate ca fiind un număr natural care nu are ca divizor niciun pătrat perfect mai mare ca 1. Prin convenție, 1 este considerat liber de pătrate.

Așadar, șirul numerelor libere de pătrate este: 1,2,3,5,6,7,10,11,13,14,15,17, ...

Se consideră un șir de N numere naturale X[i], 1 ≤ i ≤ N, unde N este un număr natural. O secvență este un subșir format din numere aflate pe poziții consecutive în șirul dat. Definim o bisecvență ca un subșir nevid obținut prin eliminarea dintr-o secvență a unui număr care nu este la începutul sau la sfârșitul secvenței.

==Cerința==
*1) Să se determine câte numere libere de pătrate conține șirul dat.
*2) Să se determine cea mai lungă bisecvență din șir formată din numere libere de pătrate, obținută prin eliminarea unui număr care nu este liber de pătrate.

==Date de intrare==
Fișierul de intrare oneout.in conține pe primul rând un număr natural C, care poate fi doar 1 sau 2, reprezentând cerința, pe a doua linie numărul natural N iar pe a treia linie N numere naturale, separate prin câte un spațiu, cu semnificația de mai sus.

==Date de ieșire==
Dacă C = 1, în fișierul de ieșire oneout.out se va scrie numărul de numere libere de pătrate din șir. Dacă C = 2:
:- pe prima linie a fișierului de ieșire oneout.out se vor scrie două numere L și K despărțite printr-un spațiu, unde L reprezintă lungimea maximă a unei bisecvențe cu proprietățile cerute, iar K reprezintă numărul de bisecvențe de lungime maximă existente în șir
:- pe următoarele K linii se vor scrie indicii de început și de sfârșit ai fiecărei bisecvențe de lungime maximă găsite, în ordinea crescătoare a indicelui de start, despărțite printr-un spațiu
:- dacă șirul nu conține nicio bisecvență cu proprietățile cerute, în fișierul de ieșire se va scrie -1.

==Restricții și precizări==
*3 ≤ N ≤ 1.000.000
*2 ≤ X[i] ≤ 1.000.000, 1 ≤ i ≤ N
*Lungimea unei bisecvențe reprezintă numărul de numere din aceasta.
*Datorită dimensiunilor prea mari ale testelor, s-au adăugat doar o parte din ele

==Exemplul 1==
;oneout.in
:1
:6
:10 2 12 7 8 15

;oneout.out
:4

==Exemplul 2==
;oneout.in
:0
:5
:10 20 30 40 50

;oneout.out
:Date de intrare invalide.

==Rezolvare==
<syntaxhighlight lang="python" line>
#4094 oneout
def is_square_free(num):
i = 2
while i * i <= num:
if num % (i * i) == 0:
return False
i += 1
return True

def count_square_free_numbers(numbers):
count = 0
for num in numbers:
if is_square_free(num):
count += 1
return count

def longest_square_free_bisect(numbers):
longest_length = 0
current_length = 0
max_length_count = 0
max_length_start = -1
max_length_end = -1
current_start = -1

for i, num in enumerate(numbers):
if is_square_free(num):
current_length += 1
if current_start == -1:
current_start = i
else:
if current_length > longest_length:
longest_length = current_length
max_length_count = 1
max_length_start = current_start
max_length_end = i - 1
elif current_length == longest_length:
max_length_count += 1
current_length = 0
current_start = -1

if current_length > longest_length:
longest_length = current_length
max_length_count = 1
max_length_start = current_start
max_length_end = len(numbers) - 1
elif current_length == longest_length:
max_length_count += 1

if longest_length == 0:
return -1
else:
return longest_length, max_length_count, max_length_start, max_length_end

def validate_input(C, N, numbers):
if C not in [1, 2]:
return False
if N < 3 or N > 1000000:
return False
if any(num < 2 or num > 1000000 for num in numbers):
return False
return True

def main():
with open("oneout.in", "r") as f_in:
C = int(f_in.readline().strip())
N = int(f_in.readline().strip())
numbers = list(map(int, f_in.readline().split()))

if not validate_input(C, N, numbers):
with open("oneout.out", "w") as f_out:
f_out.write("Date de intrare invalide.\n")
return

with open("oneout.out", "w") as f_out:
if C == 1:
result = count_square_free_numbers(numbers)
f_out.write(str(result) + "\n")
elif C == 2:
result = longest_square_free_bisect(numbers)
if result == -1:
f_out.write("-1\n")
else:
length, count, start, end = result
f_out.write(f"{length} {count}\n")
for i in range(count):
f_out.write(f"{start} {end}\n")
else:
f_out.write("Cerința introdusă nu este validă.\n")

if __name__ == "__main__":
main()
</syntaxhighlight>

4094 - oneout - Revision history