Editing 3061 - oracol

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>