daily pastebin goal
9%
SHARE
TWEET

Untitled

wrequiems Mar 25th, 2019 69 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.
  5. 3) https://www.spoj.com/problems/ADAINDEX/, helpful drawings: https://www.webwhiteboard.com/board/6bdf3r4k
  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. #
  100. # https://www.spoj.com/problems/ADAINDEX/, helpful drawings: https://www.webwhiteboard.com/board/6bdf3r4k
  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. #
  135. # https://atcoder.jp/contests/dp/tasks/dp_a
  136.  
  137. n = int(input())
  138. a = [int(i) for i in input().split(' ')]
  139.  
  140. dp = [0] * n
  141. dp[0] = 0
  142. dp[1] = abs(a[0] - a[1])
  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] = 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[100000], dp[100000], 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] = 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. #
  206. # https://atcoder.jp/contests/dp/tasks/dp_c
  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[0][0] = a[0]
  222. dp[0][1] = b[0]
  223. dp[0][2] = c[0]
  224. for i in range(1, n):
  225.    dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i]
  226.    dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i]
  227.    dp[i][2] = max(dp[i - 1][0], dp[i - 1][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(' ')][1])
  248.    k = int(input())
  249.    read = 0
  250.    for i in range(n):
  251.        if books[i] >= k:
  252.            return n - read
  253.        read += 1
  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[0][0] != b[0][0] 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. OK, I Understand
 
Top