• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Apr 22nd, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. fin = open("input.txt")
2. lines = []
3. for line in fin:
4.     lines.append(line)
5. n = len(lines) - 1
6. print(n)
7.
8. d = []
9. smejnost = []
10. v = []
11. vstar = []
12. p = []
13. inf = 1e9
14. for i in range(n):
15.     d.append([])
16.     p.append([])
17.     smejnost.append([])
18.     v.append(0)
19.     vstar.append([])
20.     for j in range(n):
21.         smejnost[i].append(0)
22.         d[i].append(inf)
23.         p[i].append(0)
24.         vstar[i].append(0)
25.
26. for i in range(n):
27.     s = lines[i]
28.     a, s = s.split('=')
29.     ss = s.split(')')
30.     a = int(a)
31.     a -= 1
32.     for c in range(len(ss) - 1):
33.         sss = ss[c].split('(')
34.         b, cost = sss[1].split(',')
35.         b = int(b)
36.         cost = int(cost)
37.         b -= 1
38.         d[a][b] = cost
39.         smejnost[a][b] = cost
40. fin.close()
41.
42. mxlen = 0
43. for i in range(n):
44.     for j in range(n):
45.         mxlen = max(mxlen, smejnost[i][j])
46.
47. mxlen *= n
48. for i in range(n):
49.     for j in range(n):
50.         if smejnost[i][j] == -1:
51.             smejnost[i][j] = mxlen
52.         d[i][j] = smejnost[i][j]
53. s = lines[n]
54. s = s[1:len(s) - 1].split(',')
55. for c in s:
56.     a, b = c.split(':')
57.     a = int(a)
58.     b = int(b)
59.     v[a - 1] = b
60.
61. for i in range(n):
62.     d[i][i] = 0
63.
64. for k in range(n):
65.     for i in range(n):
66.         for j in range(n):
67.             if d[i][k] < inf and d[k][j] < inf:
68.                 d[i][j] = min(d[i][j], d[i][k] + d[k][j])
69.
70. CBB = []
71. for i in range(n):
72.     CBB.append(0)
73.     for j in range(n):
74.         CBB[i] += d[i][j]
75. mediana = 0
76. for i in range(n):
77.     if CBB[mediana] > CBB[i]:
78.         mediana = i
79.
80. MBB = []
81. for i in range(n):
82.     MBB.append(d[i][0])
83.     for j in range(n):
84.         MBB[i] = max(MBB[i], d[i][j])
85. center = 0
86. for i in range(n):
87.     if MBB[center] > MBB[i]:
88.         center = i
89.
90. print("Smejnost")
91. for i in range(n):
92.     s = ""
93.     for j in range(n):
94.         s += str(smejnost[i][j]) + ' '
95.     print(s)
96. print("D")
97. for i in range(n):
98.     s = ""
99.     for j in range(n):
100.         s += str(d[i][j]) + ' '
101.     print(s)
102. print("center " + str(center + 1))
103. print("mediana " + str(mediana + 1))
104.
105. P = inf
106. for i in range(n):
107.     for j in range(i + 1, n):
108.         if smejnost[i][j] > 0 and smejnost[i][j]!=mxlen:
109.             # print(i+1,j+1,end=': ')
110.
111.             for k in range(n):
112.                 if k == i or k == j:
113.                     continue
114.                 if v[k] * min(d[k][i], d[k][j]) > p[i][j]:
115.                     vstar[i][j] = k
116.                     p[i][j] = v[k] * min(d[k][i], d[k][j])
117.
118.                     # print(v[k]*min(d[k][i],d[k][j]),end=', ')
119.
120.                     # print()
121.                     # print(p[i][j])
122.
123.             P = min(P, p[i][j])
124. H = inf
125. for i in range(n):
126.     for j in range(i + 1, n):
127.         if smejnost[i][j] > 0:
128.             H = min(H, p[i][j] + v[vstar[i][j]] * smejnost[i][j] / 2)
129.
130. print("P =", P)
131. print("H =", H)
132. print("rebra kotorie ostalis")
133. for i in range(n):
134.     for j in range(n):
135.         if H >= smejnost[i][j] >= P and smejnost[i][j]!=mxlen:
136.             print(i + 1, j + 1)
137.         else:
138.             smejnost[i][j] = 0
139.
140. for i in range(n):
141.     for j in range(n):
142.         d[i][j] *= v[j]
143. print("D")
144. for i in range(n):
145.     s = ""
146.     for j in range(n):
147.         s += str(d[i][j]) + ' '
148.     print(s)
149.
150. ok = False
151. minf = 0
152. minv1 = 0
153. minv2 = 0
154. fepsilon = 0
155. for i in range(n):
156.     for j in range(n):
157.         if smejnost[i][j] > 0 and smejnost[i][j] != mxlen:
158.             print("Rebro ({},{})".format(i + 1, j + 1))
159.
160.             print("Ksi")
161.             e = []  # 1 etap
162.             for k in range(n):
163.                 brv = d[j][k]
164.                 alv = d[i][k]
165.                 vv = v[k]
166.                 #  print("brv = {} alv = {} vv = {} toapp = {}".format(brv,alv,vv,(brv-alv)/(2*vv)))
167.                 e.append((brv - alv) / (2 * vv))
168.             print(e)
169.
170.             print("eps")
171.             eps = []  # 2 этап
172.             for v1 in range(n):
173.                 eps.append([])
174.                 for v2 in range(n):
175.                     #           print("Look for {},{}".format(v1, v2))
176.                     bv1 = d[j][v1]
177.                     av2 = d[i][v2]
178.                     vv1 = v[v1]
179.                     vv2 = v[v2]
180.                     #        print("bv1 = {} av2 = {} vv1 = {} vv2 = {} toapp = {}".format(bv1,av2,vv1,vv2,(bv1-av2)/(vv1+vv2)))
181.
182.                     eps[v1].append((bv1 - av2) / (vv1 + vv2))
183.                 print(eps[v1])
184.
185.             print("f")
186.             f = []  # 3 этап
187.             found = False
188.             mnv1 = 0
189.             mnv2 = 0
190.             mnf = 0
191.             for v1 in range(n):
192.                 f.append([])
193.                 for v2 in range(n):
194.                     bv1 = d[j][v1]
195.                     vv1 = v[v1]
196.                     f[v1].append(bv1 - vv1 * eps[v1][v2])
197.                     # if i == 0 and j == 2 and v1 == 1 and v2 == 3:
198.                     #    print("CHECK ",f[v1][v2])
199.                     if e[v1] <= eps[v1][v2] <= smejnost[i][j] and 0 < eps[v1][v2] < e[v2]:
201.                             found = True
202.                             mnf = f[v1][v2]
203.                             mnv1 = v1
204.                             mnv2 = v2
205.                         else:
206.                             if f[v1][v2] < mnf:
207.                                 mnf = f[v1][v2]
208.                                 mnv1 = v1
209.                                 mnv2 = v2
210.                 print(f[v1])
211.             print("f* = {} eps = {}".format(mnf, eps[mnv1][mnv2]))
212.             fl = 0  # 4 ETAP
213.             fr = 0
214.             for v1 in range(n):
215.                 fl = max(fl, d[v1][i])
216.                 fr = max(fr, d[v1][j])
217.             print("fl = {} fr = {}".format(fl, fr))
218.             epsilon = 0
219.             a = sorted([fl, fr, mnf])
220.             if a[0] == fr:
221.                 epsilon = fr
222.             elif a[0] == mnf:
223.                 epsilon = eps[mnv1][mnv2]
224.
225.             if not ok:  # 5 etap
226.                 ok = True
227.                 fepsilon = epsilon
228.                 minf = mnf
229.             else:
230.                 if mnf < minf:
231.                     minf = mnf
232.                     minv1 = i
233.                     minv2 = j
234.                     fepsilon = epsilon
235.             print("f = {} eps = {}".format(minf, epsilon))
236. print("min f = {}, epsilon = {}, ({},{})".format(minf, fepsilon, minv1 + 1, minv2 + 1))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top