Advertisement
wrequiems

Untitled

Mar 21st, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.51 KB | None | 0 0
  1. """ Homework
  2. 1) Check if there is a quadruple such that:
  3. (i, j, k, z): i < j < k < z and a[i] + a[j] = a[k] + a[z]
  4. N <= 2000
  5. 2) Check if there is a quadruple such that:
  6. (i, j, k, z): i < j < k < z and a[i] + a[k] = a[j] + a[z]
  7. N <= 2000
  8. 3) Check if there is a quadruple such that:
  9. (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
  10. N <= 2000
  11. 4) 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.
  12. """
  13.  
  14. #####
  15. # 1 #
  16. #####
  17.  
  18. a = [int(i) for i in input().split(' ')]
  19.  
  20. def exists(a):
  21.     n = len(a)
  22.     d = {}
  23.     for i in range(n):
  24.         for j in range(i + 1, n):
  25.             s = a[i] + a[j]
  26.             if s not in d:
  27.                 d[s] = j
  28.  
  29.     for z in range(n - 1, -1, -1):
  30.         for k in range(z - 1, -1, -1):
  31.             s = a[z] + a[k]
  32.             if s in d and d[s] < k:
  33.                 return True
  34.     return False
  35.  
  36. print(exists(a))
  37.  
  38. #####
  39. # 2 #
  40. #####
  41.  
  42. a = [int(i) for i in input().split(' ')]
  43.  
  44. def exists(a):
  45.     n = len(a)
  46.     d = {}
  47.     for i in range(n):
  48.         for j in range(i + 1, n):
  49.             s = a[i] - a[j]
  50.             if s not in d:
  51.                 d[s] = j
  52.  
  53.     for z in range(n - 1, -1, -1):
  54.         for k in range(z - 1, -1, -1):
  55.             s = a[z] - a[k]
  56.             if s in d and d[s] < k:
  57.                 return True
  58.     return False
  59.  
  60. print(exists(a))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement