daily pastebin goal
46%
SHARE
TWEET

Untitled

wrequiems Mar 25th, 2019 67 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.
  6. 3) https://www.spoj.com/problems/ADAINDEX/, helpful drawings: https://www.webwhiteboard.com/board/6bdf3r4k
  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. #
  101. # https://www.spoj.com/problems/ADAINDEX/, helpful drawings: https://www.webwhiteboard.com/board/6bdf3r4k
  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. #
  136. # https://atcoder.jp/contests/dp/tasks/dp_a
  137.  
  138. n = int(input())
  139. a = [int(i) for i in input().split(' ')]
  140.  
  141. dp = [0] * n
  142. dp[0] = 0
  143. dp[1] = abs(a[0] - a[1])
  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] = 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[100000], dp[100000], 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] = 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. #
  207. # https://atcoder.jp/contests/dp/tasks/dp_c
  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[0][0] = a[0]
  223. dp[0][1] = b[0]
  224. dp[0][2] = c[0]
  225. for i in range(1, n):
  226.     dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i]
  227.     dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i]
  228.     dp[i][2] = max(dp[i - 1][0], dp[i - 1][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(' ')][1])
  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[0][0] != b[0][0] 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. OK, I Understand
 
Top