4094 - oneout

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

#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()