1116 - Karb - Revision history

Ramona Dragoș: /* Rezolvare */

2024-01-08T16:51:22Z

Rezolvare

← Older revision		Revision as of 16:51, 8 January 2024
Line 45:		Line 45:
	def check_restrictions(n, k):		def check_restrictions(n, k):
	if not (1 <= k <= n <= 100000):		if not (1 <= k <= n <= 100000):
	with open("~~karbOUT~~.txt", "w") as output_file:		with open("karbout.txt", "w") as output_file:
	output_file.write("Datele nu corespund restrictiilor impuse\n")		output_file.write("Datele nu corespund restrictiilor impuse\n")
	sys.exit()		sys.exit()
Line 89:		Line 89:
	global D, T, special, viz, G		global D, T, special, viz, G

	input_file = open("~~karbIN~~.txt", "r")		input_file = open("karbin.txt", "r")
	output_file = open("~~karbOUT~~.txt", "w")		output_file = open("karbout.txt", "w")

	# Citeste N si K		# Citeste N si K

Ramona Dragoș: /* Rezolvare */

2024-01-08T16:49:25Z

Rezolvare

← Older revision		Revision as of 16:49, 8 January 2024
Line 42:		Line 42:
	mod = 666013		mod = 666013
	maxdim = 200005		maxdim = 200005


	def check_restrictions(n, k):		def check_restrictions(n, k):
	if not (1 <= k <= n <= 100000):		if not (1 <= k <= n <= 100000):
	with open("~~karbout~~.txt", "w") as output_file:		with open("karbOUT.txt", "w") as output_file:
	output_file.write("~~Nu au fost respectate cerintele~~ impuse\n")		output_file.write("Datele nu corespund restrictiilor impuse\n")
	sys.exit()		sys.exit()


	def dfs(nod):		def dfs(nod):
Line 87:		Line 85:
	else:		else:
	D[nod][0], D[nod][1] = 0, localD[0][ind]		D[nod][0], D[nod][1] = 0, localD[0][ind]


	def main():		def main():
	global D, T, special, viz, G		global D, T, special, viz, G

	input_file = open("~~karbin~~.txt", "r")		input_file = open("karbIN.txt", "r")
	output_file = open("~~karbout~~.txt", "w")		output_file = open("karbOUT.txt", "w")

	# Citeste N si K		# Citeste N si K
	N, K = map(int, input_file.readline().split())		N, K = map(int, input_file.readline().split())

	check_restrictions(N, K)		check_restrictions(N, K)

Line 128:		Line 125:
	input_file.close()		input_file.close()
	output_file.close()		output_file.close()


	if __name__ == "__main__":		if __name__ == "__main__":
	main()		main()

	</syntaxhighlight>		</syntaxhighlight>

Ramona Dragoș at 20:05, 7 January 2024

2024-01-07T20:05:19Z

Show changes

Ramona Dragoș: /* Enunt */

2023-12-29T15:02:53Z

Enunt

← Older revision		Revision as of 15:02, 29 December 2023
Line 4:		Line 4:
	ABIN (Agência Brasileira de Inteligência) doreşte să afle în câte moduri poate fi dominată ţara de influenţele celor K carteluri la data începerii campionatului mondial, modulo 666013.		ABIN (Agência Brasileira de Inteligência) doreşte să afle în câte moduri poate fi dominată ţara de influenţele celor K carteluri la data începerii campionatului mondial, modulo 666013.

	== Cerință ==		== Cerință ==
	Cunoscând numărul de orașe N, modul în care acestea sunt conectate, numărul de carteluri inițiale K și cele K orașe în care se află cartelurile, să se determine numărul de moduri în care ţara poate fi împărţită între cartelurile de cafea, modulo 666013.		Cunoscând numărul de orașe N, modul în care acestea sunt conectate, numărul de carteluri inițiale K și cele K orașe în care se află cartelurile, să se determine numărul de moduri în care ţara poate fi împărţită între cartelurile de cafea, modulo 666013.

Ramona Dragoș: Pagină nouă: == Enunt == În perioada Campionatului Mondial din Brazilia se preconizează o creştere a traficului de cafea. Se ştie că sunt N orase, conectate prin N-1 străzi bidirecţionale, astfel încât se poate ajunge din orice oraş în altul. În prezent există K carteluri de cafea aflate în oraşe distincte, care își exercita influența în propriul oraș. Se ştie că fiecare din aceste carteluri doreşte să-şi extindă influenţa în oraşele vecine. Astfel, la un mome...

2023-12-29T15:02:29Z

Pagină nouă: == Enunt == În perioada Campionatului Mondial din Brazilia se preconizează o creştere a traficului de cafea. Se ştie că sunt N orase, conectate prin N-1 străzi bidirecţionale, astfel încât se poate ajunge din orice oraş în altul. În prezent există K carteluri de cafea aflate în oraşe distincte, care își exercita influența în propriul oraș. Se ştie că fiecare din aceste carteluri doreşte să-şi extindă influenţa în oraşele vecine. Astfel, la un mome...

New page

== Enunt ==
În perioada Campionatului Mondial din Brazilia se preconizează o creştere a traficului de cafea. Se ştie că sunt N orase, conectate prin N-1 străzi bidirecţionale, astfel încât se poate ajunge din orice oraş în altul. În prezent există K carteluri de cafea aflate în oraşe distincte, care își exercita influența în propriul oraș. Se ştie că fiecare din aceste carteluri doreşte să-şi extindă influenţa în oraşele vecine. Astfel, la un moment de timp, un cartel poate să-şi extindă influenţa într-un oraş vecin doar dacă acesta nu se află sub influenţa altui cartel. O dată ce un cartel îşi extinde influenta asupra unui nou oraş, cartelul îşi poate extinde influenţa şi în oraşele vecine acestuia. Se ştie că până la începerea campionatului mondial, fiecare oraş va fi sub influenţa unui cartel.

ABIN (Agência Brasileira de Inteligência) doreşte să afle în câte moduri poate fi dominată ţara de influenţele celor K carteluri la data începerii campionatului mondial, modulo 666013.

== Cerință ==
Cunoscând numărul de orașe N, modul în care acestea sunt conectate, numărul de carteluri inițiale K și cele K orașe în care se află cartelurile, să se determine numărul de moduri în care ţara poate fi împărţită între cartelurile de cafea, modulo 666013.

== Date de intrare ==
Fișierul de intrare karbin.txt conține pe prima linie două numere naturale N şi K, reprezentând numărul de oraşe, respectiv numărul cartelurilor existente iniţial. Pe a doua linie din fişier se vor afla K numere, reprezentând oraşele în care se află cele K carteluri. Pe următoarele N-1 linii se vor afla câte două numere naturale, reprezentând o legătură între cele două oraşe.

== Date de ieșire ==
Fișierul de ieșire karbout.txt va conține pe prima linie un singur număr natural reprezentând numărul de moduri modulo 666013.

== Restricții și precizări ==
*1 &les; K &les; N &les; 100 000
*Pentru teste în valoare de 10% din punctaj se garantează că k ≤ n ≤ 7, iar pentru alte 20% din teste se garantează că k = 2.
*Două oraşe sunt vecine dacă există o stradă bidirecțională între ele.
== Exemplu 1 ==
;karbin.txt
:6 3
:3 4 5
:1 2
:1 3
:2 4
:2 5
:4 6
;karbout.txt
:5
<br>
== Exemplu 2 ==
;karbin.txt
:0 0
;karbout.txt
:Nu au fost respectate cerintele
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#1116 - Karb
MODULO = 666013

def check_restrictions(N, K, output_file):
if not (1 <= K <= N <= 100000):
output_file.write("Nu au fost respectate cerintele impuse\n")
exit()

def count_ways_to_dominate(N, K, cartel_cities, connections):
adj_list = {i: [] for i in range(1, N + 1)}

for conn in connections:
adj_list[conn[0]].append(conn[1])
adj_list[conn[1]].append(conn[0])

visited = [False] * (N + 1)
ways_to_dominate = [0] * (N + 1)

def dfs(node):
nonlocal ways_to_dominate

visited[node] = True
ways_to_dominate[node] = 1

for neighbor in adj_list[node]:
if not visited[neighbor]:
dfs(neighbor)
ways_to_dominate[node] += ways_to_dominate[neighbor]
ways_to_dominate[node] %= MODULO

for city in cartel_cities:
dfs(city)

total_ways = 1
for city in cartel_cities:
total_ways *= ways_to_dominate[city]
total_ways %= MODULO

return total_ways

if _name_ == "_main_":
with open("karbin.txt", "r") as input_file, open("karbout.txt", "w") as output_file:
N, K = map(int, input_file.readline().split())

check_restrictions(N, K, output_file)

cartel_cities = list(map(int, input_file.readline().split()))
connections = [tuple(map(int, input_file.readline().split())) for _ in range(N - 1)]

result = count_ways_to_dominate(N, K, cartel_cities, connections)
output_file.write(str(result - 1) + "\n")
</syntaxhighlight>