Sovago Rares-Andrei at 16:22, 29 April 2023

2023-04-29T16:22:49Z

← Older revision		Revision as of 16:22, 29 April 2023
Line 1:		Line 1:
	==Cerința== ~~#NEFINALIZATA~~		==Cerința==

	Se consideră '''N''' coșuri numerotate cu numerele distincte de la 1 la '''2•N'''.		Se consideră '''N''' coșuri numerotate cu numerele distincte de la 1 la '''2•N'''.

Sovago Rares-Andrei: Pagină nouă: ==Cerința== #NEFINALIZATA 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 d...

2023-04-07T16:52:59Z

Pagină nouă: ==Cerința== #NEFINALIZATA 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 d...

New page

==Cerința== #NEFINALIZATA

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''
:
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 3733 - Cosuri
import math

# Funcția de validare a datelor de intrare
# 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

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

# 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

# Funcția de concatenare a două numere întregi
def concat(a: int, b: int) -> int:
s = str(a) + str(b)
return int(s)

# Funcția main care citește și afișează datele din fișiere
# 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>

==Explicatie==

3733 - Cosuri - Revision history

Sovago Rares-Andrei at 16:22, 29 April 2023