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 p de N numere întregi. Pentru a face lucrurile mai interesante, Gustavo îi percepe o taxă de C(i,j) bănuți pentru a-i divulga suma numerelor din șirul p cu indici în intervalul [i, j], anume pi + pi+1 + ... + pj.

Cerința

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

Date de intrare

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

Date de ieșire

Fișierul de ieșire oracol.out 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 p.

Restricții și precizări

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

Exemplu:

oracol.in

3
4 5 1
6 3
2

oracol.out

6

Explicație

Costul total minim este 6 și se obține astfel:

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

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

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

Din acestea putem afla exact toate elementele șirului p.

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>