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