1200 - Spiriduși - Revision history

Ramona Dragoș at 20:39, 7 January 2024

2024-01-07T20:39:51Z

← Older revision		Revision as of 20:39, 7 January 2024
Line 33:		Line 33:
	; '''spriridusiout.txt'''		; '''spriridusiout.txt'''
	: 13		: 13
			== Explicație ==
			"Dacă alegem camerele '''a = 2 și b = 6''', obținem un spațiu de joacă format din camerele '''2, 4 și 6'''.
			"Numărul total de spiriduși goniți din aceste camere este '''4 + 2 + 1 = 7''', care este mai mic sau egal decât '''C = 8'''.
			"Suma coeficienților p ai acestor camere este '''10 + (-2) + 5 = 13''', maximul posibil ce se poate obține.
	<br>		<br>
	== Exemplu 2 ==		== Exemplu 2 ==

Ramona Dragoș at 20:38, 7 January 2024

2024-01-07T20:38:32Z

← Older revision		Revision as of 20:38, 7 January 2024
Line 1:		Line 1:
	== Enunt ==		== Enunt ==

	Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din N camere, unite între ele prin N-1 culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera 1. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră i s-au stabilit s[i] spiriduși de praf.		Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din '''N''' camere, unite între ele prin '''N-1''' culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera '''1'''. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră '''i''' s-au stabilit '''s[i]''' spiriduși de praf.

	Cele două fete doresc să-și amenajeze un spațiu de joacă întins pe mai multe camere. Ele vor să stabilească două camere a și b (nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera b trece prin camera a. Fetele vor merge apoi din camera a în camera b pe drumul cel mai scurt (fără a trece de două ori prin aceeași cameră), gonind spiridușii de praf aflați în fiecare cameră prin care trec, inclusiv pe cei din camerele a și b. După ce fetele ajung în camera b, ele consideră că toate camerele din care au gonit spiridușii de praf au fost alese pentru spațiul de joacă.		Cele două fete doresc să-și amenajeze un spațiu de joacă întins pe mai multe camere. Ele vor să stabilească două camere '''a''' și '''b''' (nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera '''b''' trece prin camera '''a'''. Fetele vor merge apoi din camera '''a''' în camera '''b''' pe drumul cel mai scurt (fără a trece de două ori prin aceeași cameră), gonind spiridușii de praf aflați în fiecare cameră prin care trec, inclusiv pe cei din camerele '''a''' și '''b'''. După ce fetele ajung în camera '''b''', ele consideră că toate camerele din care au gonit spiridușii de praf au fost alese pentru spațiul de joacă.

	Fetele au stabilit pentru fiecare cameră i un coeficient p[i] care reprezintă cât de plăcută ar fi camera i pentru spațiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de C spiriduși ai prafului din camerele prin care trec.		Fetele au stabilit pentru fiecare cameră '''i''' un coeficient '''p[i]''' care reprezintă cât de plăcută ar fi camera i pentru spațiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de '''C''' spiriduși ai prafului din camerele prin care trec.
	== Cerința ==		== Cerința ==
	Cunoscând valorile lui N și C, numărul de spiriduși ai prafului s[i], coeficienții p[i] pentru fiecare cameră i, cât și modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienților p ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.		Cunoscând valorile lui '''N''' și '''C''', numărul de spiriduși ai prafului '''s[i]''', coeficienții '''p[i]''' pentru fiecare cameră i, cât și modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienților '''p''' ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.
	== Date de intrare ==		== Date de intrare ==
	Pe prima linie a fișierului de intrare spiridusiin.txt se vor afla două numere naturale N și C cu semnificația din enunț. Pe a doua linie se vor afla N numere naturale separate prin câte un spațiu, al i-lea dintre acestea reprezentând numărul de spiriduși s[i] aflați în camera i. Pe a treia linie se vor afla N numere întregi separate prin câte un spațiu, al i-lea dintre acestea reprezentând coeficientul p[i] al camerei i. Pe următoarele N-1 linii se vor afla câte două numere întregi x și y separate printr-un spațiu, semnificând existența unui culoar ce unește camerele x și y.		Pe prima linie a fișierului de intrare '''spiridusiin.txt''' se vor afla două numere naturale '''N''' și '''C''' cu semnificația din enunț. Pe a doua linie se vor afla '''N''' numere naturale separate prin câte un spațiu, al i-lea dintre acestea reprezentând numărul de spiriduși '''s[i]''' aflați în camera i. Pe a treia linie se vor afla '''N''' numere întregi separate prin câte un spațiu, al i-lea dintre acestea reprezentând coeficientul p[i] al camerei i. Pe următoarele '''N-1''' linii se vor afla câte două numere întregi '''x''' și '''y''' separate printr-un spațiu, semnificând existența unui culoar ce unește camerele x și y.
	== Date de ieșire ==		== Date de ieșire ==
	În fișierul de ieșire spiridusiout.txt se va afișa o singură linie conținând un singur număr natural, reprezentând suma maximă a coeficienților p ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.		În fișierul de ieșire '''spiridusiout.txt''' se va afișa o singură linie conținând un singur număr natural, reprezentând suma maximă a coeficienților '''p''' ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.
	== Restricții și precizări ==		== Restricții și precizări ==
	*1 &les; N &les; 100 000		*'''1 &les; N &les; 100 000'''
	*1 &les; C &les; 20 000 000		*'''1 &les; C &les; 20 000 000'''
	*1 &les; s[i] &les; 20 000 000, pentru orice i, 1 &les; i &les; N.		*'''1 &les; s[i] &les; 20 000 000''', pentru orice i, '''1 &les; i &les; N.'''
	*-10 000 &les; p[i] &les; 10 000, pentru orice i, 1 &les; i &les; N.		*'''-10 000 &les; p[i] &les; 10 000''', pentru orice i, '''1 &les; i &les; N'''.
	*1 &les; x, y &les; N		*'''1 &les; x, y &les; N'''
	*Pentru 20% din teste, fiecare cameră are maximum 2 vecini.		*Pentru 20% din teste, fiecare cameră are maximum '''2''' vecini.
	*Pentru 30% din teste, N ≤ 1 000.		*Pentru 30% din teste, '''N ≤ 1 000'''.
	*Se garantează că pentru orice cameră x, numărul total de spiriduși aflați în camerele de pe drumul cel mai scurt de la camera 1 la camera x nu depășește 1 000 000 000.		*Se garantează că pentru orice cameră '''x''', numărul total de spiriduși aflați în camerele de pe drumul cel mai scurt de la camera 1 la camera x nu depășește '''1 000 000 000'''.
	== Exemplu 1 ==		== Exemplu 1 ==
	; spiridusiin.txt		; '''spiridusiin.txt'''
	: 6 8		: 6 8
	:2 4 6 2 4 1		:2 4 6 2 4 1
Line 31:		Line 31:
	:4 5		:4 5
	:4 6		:4 6
	; spriridusiout.txt		; '''spriridusiout.txt'''
	: 13		: 13
	<br>		<br>
	== Exemplu 2 ==		== Exemplu 2 ==
	; spiridusiin.txt		; '''spiridusiin.txt'''
	: 0 0		: 0 0
	; ~~priridusiout~~.txt		; '''spriridusiout.txt'''
	: Nu au fost respectate cerintele impuse		: Nu au fost respectate cerintele impuse
	<br>		<br>
Line 54:		Line 54:
	all(-10000 <= elem <= 10000 for elem in p) and all(		all(-10000 <= elem <= 10000 for elem in p) and all(
	1 <= elem <= N for pair in connections for elem in pair)):		1 <= elem <= N for pair in connections for elem in pair)):
	raise ValueError("Numerele nu ~~respecta~~ restricțiile.")		raise ValueError("Numerele nu respectă restricțiile.")

	return N, C, s, p, connections		return N, C, s, p, connections
	except Exception as e:		except Exception as e:
	print(f"Nu au fost respectate ~~cerintele~~ impuse: {str(e)}")		print(f"Nu au fost respectate cerințele impuse: {str(e)}")
	return None		return None

Line 97:		Line 97:

	# Citim datele de intrare		# Citim datele de intrare
	~~with open~~("spiridusiin.txt~~", "r~~") ~~as file~~:		input_data = read_input("spiridusiin.txt")
	N, C = ~~map(int, file.readline().split())~~		if input_data is not None:
	s = ~~list~~(~~map(int~~, ~~file.readline().split())~~)		N, C, s, p, connections = input_data
	~~p = list~~(~~map(int~~, file~~.readline().split()))~~
	~~connections = [tuple(map(int,~~ file.~~readline~~(~~).split~~())~~) for _ in range(N - 1)]~~		# Calculăm rezultatul
			result = solve(N, C, s, p, connections)

			# Scriem rezultatul în fișierul de ieșire
			with open("spiridusiout.txt", "w") as file:
			file.write(str(result))

	~~# Calculăm rezultatul~~
	~~result = solve(N, C, s, p, connections)~~

	~~# Scriem rezultatul în fișierul de ieșire~~
	~~with open("spiridusiout.txt", "w") as file:~~
	~~file.write(str(result))~~
	</syntaxhighlight>		</syntaxhighlight>

Ramona Dragoș: Pagină nouă: == Enunt == Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din N camere, unite între ele prin N-1 culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera 1. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră i s-au stabilit s[i] spiriduși de praf. Cele două fete doresc să-și amenajeze un spațiu de joacă întins pe...

2023-12-29T15:27:31Z

Pagină nouă: == Enunt == Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din N camere, unite între ele prin N-1 culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera 1. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră i s-au stabilit s[i] spiriduși de praf. Cele două fete doresc să-și amenajeze un spațiu de joacă întins pe...

New page

== Enunt ==

Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din N camere, unite între ele prin N-1 culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera 1. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră i s-au stabilit s[i] spiriduși de praf.

Cele două fete doresc să-și amenajeze un spațiu de joacă întins pe mai multe camere. Ele vor să stabilească două camere a și b (nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera b trece prin camera a. Fetele vor merge apoi din camera a în camera b pe drumul cel mai scurt (fără a trece de două ori prin aceeași cameră), gonind spiridușii de praf aflați în fiecare cameră prin care trec, inclusiv pe cei din camerele a și b. După ce fetele ajung în camera b, ele consideră că toate camerele din care au gonit spiridușii de praf au fost alese pentru spațiul de joacă.

Fetele au stabilit pentru fiecare cameră i un coeficient p[i] care reprezintă cât de plăcută ar fi camera i pentru spațiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de C spiriduși ai prafului din camerele prin care trec.
== Cerința ==
Cunoscând valorile lui N și C, numărul de spiriduși ai prafului s[i], coeficienții p[i] pentru fiecare cameră i, cât și modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienților p ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.
== Date de intrare ==
Pe prima linie a fișierului de intrare spiridusiin.txt se vor afla două numere naturale N și C cu semnificația din enunț. Pe a doua linie se vor afla N numere naturale separate prin câte un spațiu, al i-lea dintre acestea reprezentând numărul de spiriduși s[i] aflați în camera i. Pe a treia linie se vor afla N numere întregi separate prin câte un spațiu, al i-lea dintre acestea reprezentând coeficientul p[i] al camerei i. Pe următoarele N-1 linii se vor afla câte două numere întregi x și y separate printr-un spațiu, semnificând existența unui culoar ce unește camerele x și y.
== Date de ieșire ==
În fișierul de ieșire spiridusiout.txt se va afișa o singură linie conținând un singur număr natural, reprezentând suma maximă a coeficienților p ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.
== Restricții și precizări ==
*1 &les; N &les; 100 000
*1 &les; C &les; 20 000 000
*1 &les; s[i] &les; 20 000 000, pentru orice i, 1 &les; i &les; N.
*-10 000 &les; p[i] &les; 10 000, pentru orice i, 1 &les; i &les; N.
*1 &les; x, y &les; N
*Pentru 20% din teste, fiecare cameră are maximum 2 vecini.
*Pentru 30% din teste, N ≤ 1 000.
*Se garantează că pentru orice cameră x, numărul total de spiriduși aflați în camerele de pe drumul cel mai scurt de la camera 1 la camera x nu depășește 1 000 000 000.
== Exemplu 1 ==
; spiridusiin.txt
: 6 8
:2 4 6 2 4 1
:3 10 11 -2 4 5
:1 2
:2 3
:2 4
:4 5
:4 6
; spriridusiout.txt
: 13
<br>
== Exemplu 2 ==
; spiridusiin.txt
: 0 0
; priridusiout.txt
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#1200 - Spiridusi
def read_input(file_name):
try:
with open(file_name, 'r') as file:
N, C = map(int, file.readline().split())
s = list(map(int, file.readline().split()))
p = list(map(int, file.readline().split()))
connections = [tuple(map(int, file.readline().split())) for _ in range(N - 1)]

if not (1 <= N <= 100000 and 1 <= C <= 20000000 and all(1 <= elem <= 20000000 for elem in s) and
all(-10000 <= elem <= 10000 for elem in p) and all(
1 <= elem <= N for pair in connections for elem in pair)):
raise ValueError("Numerele nu respecta restricțiile.")

return N, C, s, p, connections
except Exception as e:
print(f"Nu au fost respectate cerintele impuse: {str(e)}")
return None

def solve(N, C, s, p, connections):
# Construim graful
graph = {}
for x, y in connections:
if x not in graph:
graph[x] = []
if y not in graph:
graph[y] = []
graph[x].append(y)
graph[y].append(x)

# Funcție pentru calculul sumei maxime a coeficienților
def dfs(node, parent, current_path, current_dust):
nonlocal max_sum
current_path.append(node)

# Calculăm suma pentru nodul curent
current_sum = sum(p[i - 1] for i in current_path)
max_sum = max(max_sum, current_sum)

# Parcurgem vecinii nodului curent
for neighbor in graph[node]:
if neighbor != parent:
# Calculăm numărul total de spiriduși de praf pe drumul curent
total_dust = current_dust + s[neighbor - 1]
# Verificăm dacă numărul de spiriduși nu depășește C
if total_dust <= C:
dfs(neighbor, node, current_path[:], total_dust)

max_sum = 0
dfs(1, 0, [], s[0])

return max_sum

# Citim datele de intrare
with open("spiridusiin.txt", "r") as file:
N, C = map(int, file.readline().split())
s = list(map(int, file.readline().split()))
p = list(map(int, file.readline().split()))
connections = [tuple(map(int, file.readline().split())) for _ in range(N - 1)]

# Calculăm rezultatul
result = solve(N, C, s, p, connections)

# Scriem rezultatul în fișierul de ieșire
with open("spiridusiout.txt", "w") as file:
file.write(str(result))
</syntaxhighlight>