• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled wrequiems  Mar 25th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. """
2. 1) Check if there is a quadruple such that:
3. (i, j, k, z): i < j < k < z and a[i] * a[k] = a[j] * a[z], https://community.topcoder.com/stat?c=problem_statement&pm=13951
4. N <= 2000
5. 2) Find the maximum side of a cross of 1's in a matrix, N <= 2000. Think about a harder version: https://codeforces.com/problemset/problem/677/E; Don't care about the big number part.
7. 4) Hit https://codeforces.com/blog/entry/64250
8. 5) Round 546
9. """
10.
11. #####
12. # 1 #
13. #####
14. #
15. # Check if there is a quadruple such that:
16. # (i, j, k, z): i < j < k < z and a[i] * a[k] = a[j] * a[z], https://community.topcoder.com/stat c=problem_statement&pm=13951 N <= 2000
17.
18. from math import gcd
19.
20. a = [int(i) for i in input().split(' ')]
21. n = len(a)
22. d = {}
23. count = 0
24.
25. for i in range(n):
26.     for j in range(i + 1, n):
27.         g = gcd(a[i], a[j])
28.         a_i = a[i] // g
29.         a_j = a[j] // g
30.         d.setdefault((a_i, a_j), [])
31.         d[(a_i, a_j)].append(j)
32.
33. for k in range(n):
34.     for z in range(k + 1, n):
35.         g = gcd(a[k], a[z])
36.         a_k = a[k] // g
37.         a_l = a[z] // g
38.         division = (a_l, a_k)
39.         if division in d:
40.             for position in d[division]:
41.                 if position < k:
42.                     count += 1
43. print(count)
44.
45. #####
46. # 2 #
47. #####
48. #
49. # Find the maximum side of a cross of 1's in a matrix, N <= 2000. Think about a harder version: https://codeforces.com/problemset/problem/677/E; Don't care about the big number part.
50.
51. n = int(input())
52. a = []
53. k = []
54.
55. directions = ['left', 'right', 'up', 'down']
56.
57. def process_row(i):
58.     j = 0
59.     while j < n:
60.         start = j
61.         while j < n and a[i][j] == 1:
62.             j += 1
63.         for x in range(start, j):
64.             value = x - start
65.             k[i][x]['left'] = value
66.             k[i][x]['right'] = j - x - 1
67.         j += 1
68.
69. def process_column(j):
70.     i = 0
71.     while i < n:
72.         start = i
73.         while i < n and a[i][j] == 1:
74.             i += 1
75.         for x in range(start, i):
76.             value = x - start
77.             k[x][j]['up'] = value
78.             k[x][j]['down'] = i - x - 1
79.         i += 1
80.
81. for i in range(n):
82.     a.append([int(i) for i in input().split(' ')])
83.     k.append([])
84.     for j in range(n):
85.         k[i].append({'left': 0, 'right': 0, 'up': 0, 'down': 0})
86.
87. for i in range(n):
88.     process_row(i)
89.     process_column(i)
90.
91. m = 0
92. for i in range(n):
93.     for j in range(n):
94.         m = max(m, min(k[i][j].values()))
95. print(m)
96.
97. #####
98. # 3 #
99. #####
100. #
102.
103. n, q = map(int, input().split(' '))
104. t = {"children": {}, "value": 0}
105. for _ in range(n):
106.     word = input()
107.     t['value'] += 1
108.     current_node = t
109.     for l in word:
110.         current_node['children'].setdefault(l, {"children": {}, "value": 0})
111.         current_node['children'][l]['value'] += 1
112.         current_node = current_node['children'][l]
113. for _ in range(q):
114.     word = input()
115.     current_node = t
116.     printed = False
117.     for l in word:
118.         if l not in current_node['children']:
119.             print(0)
120.             printed = True
121.             break
122.         current_node = current_node['children'][l]
123.     if not printed:
124.         print(current_node['value'])
125.
126. #####
127. # 4 #
128. #####
129. #
130. # Hit https://codeforces.com/blog/entry/64250
131.
132. #######
133. # 4.1 #
134. #######
135. #
137.
138. n = int(input())
139. a = [int(i) for i in input().split(' ')]
140.
141. dp =  * n
142. dp = 0
143. dp = abs(a - a)
144. for i in range(2, n):
145.     dp[i] = min(abs(a[i - 2] - a[i]) + dp[i - 2], abs(a[i - 1] - a[i]) + dp[i - 1])
146. print(dp[-1])
147.
148. #########
149. # 4.2.1 #
150. #########
151. #
152. # https://atcoder.jp/contests/dp/tasks/dp_b - python version - TLE
153.
154. n, k = map(int, input().split(' '))
155. a = [int(i) for i in input().split(' ')]
156.
157. dp = [float('inf')] * n
158. dp = 0
159. for i in range(1, n):
160.     for x in range(1, min(i, k) + 1):
161.         z = abs(a[i - x] - a[i]) + dp[i - x]
162.         if dp[i] > z:
163.             dp[i] = z
164. print(dp[-1])
165.
166. #########
167. # 4.2.1 #
168. #########
169. #
170. # https://atcoder.jp/contests/dp/tasks/dp_b - got pissed, implemented it in raw C - the very same construct < 30ms o.O
171.
172. """
173. #include <stdio.h>
174. #include <stdlib.h>
175.
176. int min(int a, int b) {
177.    if (a > b) {
178.        return b;
179.    }
180.    return a;
181. }
182.
183. int main() {
184.    int a, dp, n, k;
185.    const int inf = 1e9;
186.    scanf("%d", &n);
187.    scanf("%d", &k);
188.    for(int i = 0; i < n; i++) {
189.        scanf("%d", &a[i]);
190.        dp[i] = inf;
191.    }
192.    dp = 0;
193.    for(int i = 1; i < n; i++){
194.        for(int j = 1; j < min(i, k) + 1; j++){
195.            dp[i] = min(dp[i], abs(a[i] - a[i - j]) + dp[i - j]);
196.        }
197.    }
198.    printf("%d\n", dp[n - 1]);
199.    return 0;
200. }
201. """
202.
203. #######
204. # 4.3 #
205. #######
206. #
208.
209. n = int(input())
210. a = []
211. b = []
212. c = []
213. dp = []
214. for i in range(n):
215.     dp.append([0, 0, 0])
216. for i in range(n):
217.     a_i, b_i, c_i = [int(i) for i in input().split(' ')]
218.     a.append(a_i)
219.     b.append(b_i)
220.     c.append(c_i)
221.
222. dp = a
223. dp = b
224. dp = c
225. for i in range(1, n):
226.     dp[i] = max(dp[i - 1], dp[i - 1]) + a[i]
227.     dp[i] = max(dp[i - 1], dp[i - 1]) + b[i]
228.     dp[i] = max(dp[i - 1], dp[i - 1]) + c[i]
229.
230. print(max(dp[-1]))
231.
232. #####
233. # 5 #
234. #####
235. #
236. # https://codeforces.com/contest/1136
237.
238. #######
239. # 5.1 #
240. #######
241. #
242. # https://codeforces.com/contest/1136/problem/A
243.
244. def go():
245.     n = int(input())
246.     books = []
247.     for i in range(n):
248.         books.append([int(i) for i in input().split(' ')])
249.     k = int(input())
250.     read = 0
251.     for i in range(n):
252.         if books[i] >= k:
253.             return n - read
254.         read += 1
255.
256. print(go())
257.
258. #######
259. # 5.2 #
260. #######
261. #
262. # https://codeforces.com/contest/1136/problem/B
263.
264. def go():
265.     n, k = map(int, input().split(' '))
266.     return min(n - k, k - 1) + 3 * n
267.
268. print(go())
269.
270. #######
271. # 5.1 #
272. #######
273. #
274. # https://codeforces.com/contest/1136/problem/C - this one is failing on a test. I have no idea why that would be, since my reasoning seems legit. (You can switch any elements, given enough transposes on different submatrices. The only 2 that won't ever switch are the diagonal heads (0, 0), (n, m). Yet, this fails. I could use some help with understanding why this is wrong or why this assumption is invalid.
275.
276. def go():
277.     n, m = map(int, input().split(' '))
278.     a = []
279.     b = []
280.     for l in [a, b]:
281.         for i in range(n):
282.             l.append([int(i) for i in input().split(' ')])
283.     if a != b or a[-1][-1] != b[-1][-1]:
284.         return "NO"
285.     counter_a = {}
286.     counter_b = {}
287.     for l, c in [(a, counter_a), (b, counter_b)]:
288.         for i in range(n):
289.             for j in range(m):
290.                 c.setdefault(l[i][j], 0)
291.                 c[l[i][j]] += 1
292.     if counter_a != counter_b:
293.         return "NO"
294.     return "YES"
295. print(go())
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