3733 - Cosuri

Cerința

Se consideră N coșuri numerotate cu numerele distincte de la 1 la 2•N. Coșul 1 conține C1 mere, coșul 2 conține C2 mere,…, coșul 2•N conține C2•N mere.

Cele 2•N coșuri vor fi grupate două câte două, rezultând N perechi de coșuri. Fiecare coș poate face parte dintr-o singură pereche. Numărul de mere dintr-o pereche de coșuri este egal cu suma numerelor de mere din cele două coșuri. Pentru fiecare pereche, valoarea absolută a diferenței numerelor de mere din cele două coșuri ale perechii reprezintă excedentul perechii.

Ionuț, având o fire curioasă, vrea să afle mai multe despre aceste perechi.

Mai întâi vrea să afle numărul minim posibil, respectiv maxim posibil, de mere dintr-o pereche, indiferent de gruparea coșurilor în perechi de câte două.

Apoi, Ionuț vă întreabă dacă este posibil să grupeze cele 2•N coșuri în perechi de câte două, astfel încât cele N perechi rezultate să aibă același număr de mere. Dacă este posibil, atunci Ionuț vrea să afle și care este valoarea minimă a excedentelor perechilor din noua grupare.

Voi va trebui să îl ajutați pe Ionuț să afle răspunsurile la întrebările lui. Scrieți un program care să citească numărul N și cele 2•N numere naturale C1, C2,…, C2•N, iar apoi să determine:

1. Numărul minim de mere și numărul maxim de mere pe care le pot avea perechile de coșuri.

2. Răspunsul DA sau NU la întrebarea lui Ionuț; dacă răspunsul este DA, se va determina și care este valoarea minimă a excedentelor perechilor din noua grupare.

Date de intrare

Fișierul de intrare cosuri.in conține pe prima linie două numere naturale T și N separate printr-un spațiu. A doua linie a fișierului conține cele 2•N numere naturale C1, C2,…, C2•N, separate prin câte un spațiu.

Date de intrare

Fișierul de intrare cosuri.in conține pe prima linie două numere naturale T și N separate printr-un spațiu. A doua linie a fișierului conține cele 2•N numere naturale C1, C2,…, C2•N, separate prin câte un spațiu.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Fișierul de ieșire cosuri.out va conține:

Dacă T=1, pe prima linie, două numere naturale separate printr-un singur spațiu reprezentând numărul minim, respectiv maxim de mere pe care le pot avea perechile (răspunsul la cerinţa 1); Dacă T=2, pe prima linie, un șir de două caractere care poate fi DA sau NU, reprezentând răspunsul la întrebarea lui Ionuț; dacă răspunsul este DA, atunci a doua linie a fișierului va conține un număr natural reprezentând valoarea minimă a excedentelor perechilor din noua grupare (răspunsul la cerința 2). În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ N ≤ 500 000
• 1 ≤ Ci ≤ 1 000 000, pentru oricare 1 ≤ i ≤ 2·N
• Pentru teste în valoare de 30 de puncte, T = 1
• Pentru restul de 70 de puncte, T= 2
• Pentru teste în valoare de 20 de puncte, N ≤ 5
• Pentru alte teste în valoare de 40 de puncte, N ≤ 70000

Exemple

Exemplul 1

cosuri.in

1 3

1 7 4 10 2 9

ecran

Datele sunt introduse corect.

cosuri.out

3 19

Exemplul 2

cosuri.in

2 3

1 7 4 10 2 9

ecran

Datele sunt introduse corect.

cosuri.out

DA

3

Exemplul 3

puternic.in

2 3

1 7 5 12 2 9

ecran

Datele nu corespund restricțiilor impuse.

puternic.out

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 3733 - Cosuri

import math

1. Funcția de validare a datelor de intrare
2. Funcția de validare a datelor de intrare

def validate_input(C: int, N: int, nums: list[int]) -> bool:

   # Verificăm că C este 1 sau 2
   if C not in [1, 2]:
       return False

   # Verificăm că N este între 1 și 100.000
   if not (1 <= N <= 100000):
       return False

   # Verificăm că lista nums are lungimea N și conține doar numere întregi între 1 și 1.000.000.000
   if len(nums) != N or not all(isinstance(x, int) and 1 <= x <= 1000000000 for x in nums):
       return False

   return True

1. Funcția de rezolvare

def solve(C: int, N: int, nums: list[int]) -> str:

   # Cazul 1
   if C == 1:
       nrp = 0
       for x in nums:
           if x > 1 and is_powerful(x):
               nrp += 1
       return str(nrp)

   # Cazul 2
   new_nums = []
   for x in nums:
       if x == 1 or not is_powerful(x):
           new_nums.append(x)

   result = []
   for i in range(len(new_nums) // 2):
       nr1 = new_nums[i]
       nr2 = new_nums[-i - 1]
       lp = concat(nr1, nr2)
       if is_powerful(lp):
           result.append((nr1, nr2))

   if not result:
       return "-1"
   else:
       return "\n".join([f"{nr1} {nr2}" for nr1, nr2 in result])

1. Funcția de concatenare și verificare dacă numărul obținut este puternic

def is_powerful(nr: int) -> bool:

   # Calculăm descompunerea în factori primi și verificăm dacă toți au exponența mai mare sau egală cu 2
   i = 2
   while i * i <= nr:
       ex = 0
       while nr % i == 0:
           ex += 1
           nr //= i
       if ex == 1:
           return False
       i += 1
   if nr > 1:
       ex = 1
   if ex == 1:
       return False

   # Verificăm dacă nr este pătrat perfect sau cub perfect
   sqrt_nr = round(math.sqrt(nr))
   if sqrt_nr * sqrt_nr == nr:
       return True
   cub_rt = round(nr ** (1 / 3))
   if cub_rt * cub_rt * cub_rt == nr:
       return True
   return False

1. Funcția de concatenare a două numere întregi

def concat(a: int, b: int) -> int:

   s = str(a) + str(b)
   return int(s)

1. Funcția main care citește și afișează datele din fișiere
2. Funcția main care citește și afișează datele din fișiere

if __name__ == "__main__":

   with open("puternic.in", "r") as fin:
       with open("puternic.out", "w") as fout:
           C = int(fin.readline().strip())
           N = int(fin.readline().strip())
           nums = list(map(int, fin.readline().strip().split()))

           if not validate_input(C, N, nums):
                print ("Datele nu corespund restricțiilor impuse.")
           else:
               print ("Datele sunt introduse corect.\n")
               if C == 1:
                   nrp = 0
                   for x in nums:
                       if x > 1 and is_powerful(x):
                           nrp += 1
                   fout.write(str(nrp))
               elif C == 2:
                   new_nums = []
                   for x in nums:
                       if x == 1 or not is_powerful(x):
                           new_nums.append(x)

                   result = []
                   for i in range(len(new_nums) // 2):
                       nr1 = new_nums[i]
                       nr2 = new_nums[-i - 1]
                       lp = concat(nr1, nr2)
                       if is_powerful(lp):
                           result.append((nr1, nr2))

                   if not result:
                       fout.write("-1")
                   else:
                       fout.write("\n".join([f"{nr1} {nr2}" for nr1, nr2 in result]))

</syntaxhighlight>