Danciu: Pagină nouă: Gustavo, după ce a realizat că posedă abilitatea de a vedea în viitor, a decis că a venit momentul să treacă la următorul nivel și să-și valorifice capacitățile extrasenzoriale. Pentru a câștiga prestigiu și a deveni mai cunoscut în rândurile magicienilor profesioniști, acesta a ales să debuteze la Olimpiada Națională de Informatică prin prezicerea datelor de intrare pentru anumite probleme propuse în concurs. Primul client al lui Gustavo, Alfredo, ar...

2024-06-04T03:04:00Z

Pagină nouă: Gustavo, după ce a realizat că posedă abilitatea de a vedea în viitor, a decis că a venit momentul să treacă la următorul nivel și să-și valorifice capacitățile extrasenzoriale. Pentru a câștiga prestigiu și a deveni mai cunoscut în rândurile magicienilor profesioniști, acesta a ales să debuteze la Olimpiada Națională de Informatică prin prezicerea datelor de intrare pentru anumite probleme propuse în concurs. Primul client al lui Gustavo, Alfredo, ar...

New page

Gustavo, după ce a realizat că posedă abilitatea de a vedea în viitor, a decis că a venit momentul să treacă la următorul nivel și să-și valorifice capacitățile extrasenzoriale. Pentru a câștiga prestigiu și a deveni mai cunoscut în rândurile magicienilor profesioniști, acesta a ales să debuteze la Olimpiada Națională de Informatică prin prezicerea datelor de intrare pentru anumite probleme propuse în concurs. Primul client al lui Gustavo, Alfredo, ar dori să afle într-un mod inedit conținutul unui fișier de intrare aferent unei probleme de concurs, în care sunt scrise elementele unui șir <code>p</code> de <code>N</code> numere întregi. Pentru a face lucrurile mai interesante, Gustavo îi percepe o taxă de <code>C(i,j)</code> bănuți pentru a-i divulga suma numerelor din șirul <code>p</code> cu indici în intervalul <code>[i, j]</code>, anume <code>pi</code> <code>+ pi+1</code> <code>+ ... + pj</code>.

= Cerința =
Dându-se valoarea lui <code>N</code> și toate valorile <code>C(i,j)</code> cu <code>1 ≤ i ≤ j ≤ N</code>, determinați costul total minim pe care trebuie să-l plătească Alfredo pentru a afla toate elementele șirului <code>p</code>.

= Date de intrare =
În fișierul <code>oracol.in</code> se află pe prima linie numărul natural <code>N</code>. Pe următoarele <code>N</code> linii se află taxele percepute de Gustavo astfel: pe linia <code>i+1</code> se vor afla <code>N-i+1</code> numere naturale separate prin câte un spațiu, reprezentând în ordine costurile <code>C(i,i)</code>, <code>C(i,i+1)</code>, …, <code>C(i,N)</code>.

= Date de ieșire =
Fișierul de ieșire <code>oracol.out</code> va conține pe prima linie un singur număr care reprezintă costul total minim pe care trebuie să-l plătească Alfredo pentru a afla șirul <code>p</code>.

= Restricții și precizări =

* <code>1 ≤ N ≤ 1000</code>;
* pentru orice <code>1 ≤ i ≤ j ≤ N</code> se garantează <code>0 ≤ C(i,j) ≤ 1.000.000</code>;
* pentru teste în valoare de <code>48</code> puncte <code>1 ≤ N ≤ 250</code>.

= Exemplu: =
<code>oracol.in</code>
3
4 5 1
6 3
2
<code>oracol.out</code>
6

=== Explicație ===
Costul total minim este <code>6</code> și se obține astfel:

Cu un cost de valoare <code>C(1,3) = 1</code> putem afla suma <code>p1</code> <code>+ p2</code> <code>+ p3</code>.

Cu un cost de valoare <code>C(3,3) = 2</code> putem afla valoarea lui <code>p3</code>.

Cu un cost de valoare <code>C(2,3) = 3</code> putem afla suma <code>p2</code> <code>+ p3</code>.

Din acestea putem afla exact toate elementele șirului <code>p</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
class DSU:
def __init__(self, n):
self.f = list(range(n))

def find(self, x):
if self.f[x] != x:
self.f[x] = self.find(self.f[x])
return self.f[x]

def union(self, x, y):
self.f[self.find(x)] = self.find(y)

def main():
with open("oracol.in", "r") as fin:
n = int(fin.readline())
costs = []
for _ in range(n):
row = list(map(int, fin.readline().split()))
costs.extend(row)

edges = []
for i in range(n):
for j in range(i + 1, n + 1):
cost = costs.pop(0)
edges.append((i, j, cost))

edges.sort(key=lambda x: x[2])
f = DSU(n + 1)
ans = 0
for e in edges:
if f.find(e[0]) != f.find(e[1]):
ans += e[2]
f.union(e[0], e[1])

with open("oracol.out", "w") as fout:
fout.write(str(ans) + '\n')

if __name__ == "__main__":
main()

</syntaxhighlight>

3061 - oracol - Revision history