Rus Marius: Pagină nouă: = Enunț = În țara Zoomba trăiesc `K` prieteni, fiecare în localități diferite. În această țară se găsesc `N` orașe, oricare două fiind legate prin cel mult o șosea bidirecțională. Deoarece nu s-au mai întâlnit de mult, cei `K` prieteni s-au hotărât să se reîntâlnească într-un oraș. Fiecare are câte o mașină cu număr nelimitat de locuri. Pentru a trece de la un oraș la altul, o mașină consumă `1` li...

2024-01-06T20:37:24Z

Pagină nouă: = Enunț = În țara Zoomba trăiesc <code>K</code> prieteni, fiecare în localități diferite. În această țară se găsesc <code>N</code> orașe, oricare două fiind legate prin cel mult o șosea bidirecțională. Deoarece nu s-au mai întâlnit de mult, cei <code>K</code> prieteni s-au hotărât să se reîntâlnească într-un oraș. Fiecare are câte o mașină cu număr nelimitat de locuri. Pentru a trece de la un oraș la altul, o mașină consumă <code>1</code> li...

New page

= Enunț =
În țara Zoomba trăiesc <code>K</code> prieteni, fiecare în localități diferite. În această țară se găsesc <code>N</code> orașe, oricare două fiind legate prin cel mult o șosea bidirecțională. Deoarece nu s-au mai întâlnit de mult, cei <code>K</code> prieteni s-au hotărât să se reîntâlnească într-un oraș. Fiecare are câte o mașină cu număr nelimitat de locuri. Pentru a trece de la un oraș la altul, o mașină consumă <code>1</code> litru de benzină.

= Cerința =
Știind că odată ce au ajuns în același oraș <code>2</code> sau mai mulți prieteni, aceștia iși pot continua drumul cu o singură mașină, să se determine consumul minim de benzină pentru ca aceștia să ajungă în orașul <code>Z</code>.

= Date de intrare =
Fișierul de intrare <code>zoombaIN.txt</code> conține pe prima linie numerele <code>N</code>, <code>M</code>(numărul de șosele), <code>K</code> și <code>Z</code>. Pe următoarea linie se află <code>K</code> numere, reprezentând pozițiile inițiale ale celor <code>K</code> prieteni. Pe următoarele <code>M</code> linii se află câte o pereche <code>i j</code>, cu semnificația că există șosea de la orașul <code>i</code> la orașul <code>j</code>.

= Date de ieșire =
Fișierul de ieșire <code>zoombaOUt.txt</code> va conține pe prima linie numărul <code>C</code>, ce va fi egal cu consumul minim de combustibil necesar ca cei <code>K</code> prieteni să se întâlnească în orașul <code>Z</code>, sau <code>-1</code> în cazul în care aceștia nu pot ajunge în el.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ Z ≤ N ≤ 200</code>
* <code>1 ≤ K ≤ min(N,10)</code>

= Exemplul 1: =
<code>zoombaIN.txt</code>
5 4 3 5
1 2 3
1 4
2 4
3 4
4 5
<code>zoombaOUt.txt</code>
4

= Exemplul 2: =
<code>zoombaIN.txt</code>
201 4 3 5
1 2 3
1 4
2 4
3 4
4 5
<code>zoombaOUt.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque
import sys

def check_constraints(n, k, z):
if not (1 <= z <= n <= 200 and 1 <= k <= min(n, 10)):
with open('zoombaOUT.txt', 'w') as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
sys.exit()

def main():
kmax = 10
nmax = 203
inf = int(1e9)

def lee(v):
while coada:
k = coada.popleft()
for i in range(len(g[k])):
if dp[g[k][i]][v] > dp[k][v] + 1:
dp[g[k][i]][v] = dp[k][v] + 1
coada.append(g[k][i])

def construct(l):
ret = 0
i = 0
while l:
ret ^= (1 << i)
i += 1
l -= 1
return ret

def nbiti(x):
k = 0
while x:
k += (x & 1)
x >>= 1
return k

# Redirect input and output to files
sys.stdin = open('zoombaIN.txt', 'r')
sys.stdout = open('zoombaOUT.txt', 'w')

n, m, k, z = map(int, input().split())

# Check constraints and exit if not met
check_constraints(n, k, z)

a = list(map(int, input().split()))
g = [[] for _ in range(nmax)]
dp = [[inf] * (1 << (kmax + 1)) for _ in range(nmax)]
coada = deque()

for _ in range(m):
i, j = map(int, input().split())
g[i].append(j)
g[j].append(i)

for i in range(k):
dp[a[i]][1 << i] = 0
coada.append(a[i])
lee(1 << i)

for l in range(2, k + 1):
for j in range(construct(l), (1 << k)):
if nbiti(j) == l:
for i in range(1, n + 1):
for c in range(1, j):
if (j | c) == j:
dp[i][j] = min(dp[i][j], dp[i][c] + dp[i][j ^ c])
coada.append(i)
lee(j)

result = dp[z][(1 << k) - 1] if dp[z][(1 << k) - 1] != inf else -1
print(result)

# Close the files
sys.stdin.close()
sys.stdout.close()

if __name__ == "__main__":
main()

</syntaxhighlight>

1825 - Zoomba - Revision history