Oros Ioana Diana at 17:06, 8 January 2024

2024-01-08T17:06:46Z

← Older revision		Revision as of 17:06, 8 January 2024
Line 1:		Line 1:
			Fie un şir a[1], a[2], …, a[n] de numere naturale, unde n este impar. Avem la dispoziţie o singură operaţie admisă şi anume: putem aduna la două poziţii diferite din şir o aceeaşi valoare naturală nenulă.
	== Cerința ==		== Cerința ==
	Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații.		Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații.
Line 27:		Line 28:
	<br>		<br>
	~ Pentru teste valorând 20 de puncte vom avea C=1. Pentru restul testelor vom avea C=2, din care pentru 30 de puncte șirul va fi format din numere distincte cuprinse între 1 și n.		~ Pentru teste valorând 20 de puncte vom avea C=1. Pentru restul testelor vom avea C=2, din care pentru 30 de puncte șirul va fi format din numere distincte cuprinse între 1 și n.
	== ~~Exemplu~~ 1 ==		== Exemplul 1 ==
	; ~~Intrare~~		; perechi2in.txt
	~~: perechi2~~.in
	:1		:1
	:5		:5
	:8 2 8 8 2		:8 2 8 8 2
	; ~~Ieșire~~		; perechi2out.txt
	~~: perechi2~~.~~out~~
	:2 5 6		:2 5 6
	== ~~Exemplu~~ 2 ==		== Exemplul 2 ==
	; ~~Intrare~~		; perechi2in.txt
	~~: perechi2~~.in
	;2		;2
	:5		:5
	:8 5 6 3 10		:8 5 6 3 10
	; ~~Ieșire~~		; perechi2out.txt
	~~: perechi2~~.~~out~~
	:1 2 2		:1 2 2
	:3 4 4		:3 4 4
Line 78:		Line 75:

	return operatii		return operatii
			def verificare_restrictii(numar): # funcția de verificare a datelor de intrare
			if 5 <= numar < 2000 # adăugăm restricția pentru n
			0 <= a[i] <= 1.000.000.000:
			return True
			else:
			return False


	def main():		def main():

Oros Ioana Diana: Pagină nouă: == Cerința == Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații.
Folosind de mai multe ori operaţia admisă, să se obţină șirul cu toate elementele egale, dar valoarea egală obţinută să nu depăşească dublul valorii maxime din şirul iniţial. == Date de intrare == Fișierul de intrare perechi2.in conține pe prima linie un număr natural C, pe a doua linie numărul n, iar pe linia a treia, separate pri...

2023-12-12T15:48:23Z

Pagină nouă: == Cerința == Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații. Folosind de mai multe ori operaţia admisă, să se obţină șirul cu toate elementele egale, dar valoarea egală obţinută să nu depăşească dublul valorii maxime din şirul iniţial. == Date de intrare == Fișierul de intrare perechi2.in conține pe prima linie un număr natural C, pe a doua linie numărul n, iar pe linia a treia, separate pri...

New page

== Cerința ==
Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații.
 
Folosind de mai multe ori operaţia admisă, să se obţină șirul cu toate elementele egale, dar valoarea egală obţinută să nu depăşească dublul valorii maxime din şirul iniţial.
== Date de intrare ==
Fișierul de intrare perechi2.in conține pe prima linie un număr natural C, pe a doua linie numărul n, iar pe linia a treia, separate prin câte un spațiu, valorile a[1], a[2], …, a[n].
== Date de ieșire ==
Fișierul de ieșire perechi2.out va conține:
 
1.Dacă C=1, atunci se va rezolva doar prima cerință, deci se va afișa pe prima linie valoarea 0 dacă nu se pot obține în șir toate elementele egale, sau se vor afișa trei numere naturale i j v cu semnificația: la pozițiile i și j din șir se adaugă valoarea v și astfel toate elementele vectorului vor deveni egale.
 
2.Dacă C=2, atunci se va rezolva doar a doua cerință. Pe fiecare linie a fișierului de ieșire se vor afișa exact trei valori i j v cu semnificația: se adună valoarea v la a[i] și la a[j] (unde i și j sunt distincte și sunt cuprinse între 1 și n).
== Restricții și precizări ==
~ 5 ≤ n < 2000, n este impar
 
~ 0 ≤ a[i] ≤ 100 000 000, pentru orice i=1..n
 
~ Elementele șirului inițial nu sunt neapărat distincte, dar nu sunt nici toate egale
 
~ Dacă există mai multe soluții, puteți afișa oricare dintre ele.
 
~ Dacă numărul operațiilor aplicate este mai mic sau egal decât n, iar valoarea finală este de cel mult două ori cât maximul inițial și rezultatul aplicării operațiilor furnizează în șir aceeași valoare, atunci veți primi 100% din punctaj.
 
~ Dacă numărul operațiilor este cuprins între n+1 și 2n, iar valoarea finală este de cel mult două ori cât maximul inițial și rezultatul aplicării operațiilor furnizează în șir aceeași valoare, atunci veți primi 70% din punctaj.
 
~ Dacă numărul operațiilor este mai mare de 2n sau dacă valoarea finală depășește dublul valorii maxime inițiale, atunci veți primi 0 puncte. De asemenea, dacă în urma operațiilor aplicate nu se obține un șir cu aceeași valoare peste tot, sau dacă aplicați o operație în care pozițiile i și j nu sunt din intervalul 1..n, atunci de asemenea veți primi 0 puncte.
 
~ Pentru teste valorând 20 de puncte vom avea C=1. Pentru restul testelor vom avea C=2, din care pentru 30 de puncte șirul va fi format din numere distincte cuprinse între 1 și n.
== Exemplu 1 ==
; Intrare
: perechi2.in
:1
:5
:8 2 8 8 2
; Ieșire
: perechi2.out
:2 5 6
== Exemplu 2 ==
; Intrare
: perechi2.in
;2
:5
:8 5 6 3 10
; Ieșire
: perechi2.out
:1 2 2
:3 4 4
:2 4 3
 
== Rezolvare ==
<syntaxhighlight lang="python" line>
#1696 - Perechi 2
def pot_deveni_egale(n, arr):
elemente_unice = set(arr)
if len(elemente_unice) == 1:
return True

valoare_maxima = max(arr)
contor_maxim = arr.count(valoare_maxima)

if contor_maxim % 2 == 0:
return True
elif contor_maxim > 1:
return valoare_maxima * 2 <= max(arr)
else:
return False

def aplicare_operatii(n, arr):
operatii = []
valoare_maxima = max(arr)

for i in range(n):
if arr[i] != valoare_maxima:
diferenta = valoare_maxima - arr[i]
operatii.append((i + 1, (i + 1) % n + 1, diferenta))
arr[i] += diferenta
arr[(i + 1) % n] += diferenta

return operatii

def main():
with open("perechi2.in", "r") as file_in:
C = int(file_in.readline().strip())
n = int(file_in.readline().strip())
arr = list(map(int, file_in.readline().split()))

if C == 1:
rezultat = 0 if pot_deveni_egale(n, arr) else 1
with open("perechi2.out", "w") as file_out:
file_out.write(str(rezultat))
elif C == 2:
operatii = aplicare_operatii(n, arr)
with open("perechi2.out", "w") as file_out:
file_out.write(str(len(operatii)) + "\n")
for op in operatii:
file_out.write(f"{op[0]} {op[1]} {op[2]}\n")

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

1696 - Perechi 2 - Revision history

Oros Ioana Diana at 17:06, 8 January 2024