nq1s788

Untitled

Mar 16th, 2026
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.41 KB | None | 0 0
  1. inf = 1000000000
  2.  
  3. def find_max(start):
  4.     global n, no_left, no_up, field_max, starts
  5.     if field_max[start[0]][start[1]] == 0:
  6.         return 0
  7.     answ = [[0 for i in range(n)] for j in range(n)]
  8.     answ[start[0]][start[1]] = field_max[start[0]][start[1]]
  9.     for i in range(start[0], n):
  10.         for j in range(start[1], n):
  11.             if (i, j) in starts:
  12.                 continue
  13.             if (i, j) in no_left:
  14.                 answ[i][j] = answ[i - 1][j] + field_max[i][j]
  15.             elif (i, j) in no_up:
  16.                 answ[i][j] = answ[i][j - 1] + field_max[i][j]
  17.             else:
  18.                 answ[i][j] = max(answ[i][j - 1], answ[i - 1][j]) + field_max[i][j]
  19.     current = (n - 1, n - 1)
  20.     while current != start:
  21.         field_max[current[0]][current[1]] = 0
  22.         if current in no_left:
  23.             current = (current[0] - 1, current[1])
  24.         elif current in no_up:
  25.             current = (current[0], current[1] - 1)
  26.         elif answ[current[0] - 1][current[1]] >= answ[current[0]][current[1] - 1]:
  27.             current = (current[0] - 1, current[1])
  28.         else:
  29.             current = (current[0], current[1] - 1)
  30.     field_max[start[0]][start[1]] = 0
  31.     return answ[n - 1][n - 1]
  32.  
  33. def find_min(start):
  34.     global n, no_left, no_up, field_min, starts
  35.     if field_min[start[0]][start[1]] >= inf:
  36.         return 0
  37.     answ = [[inf for i in range(n)] for j in range(n)]
  38.     answ[start[0]][start[1]] = field_min[start[0]][start[1]]
  39.     for i in range(start[0], n):
  40.         for j in range(start[1], n):
  41.             if (i, j) in starts:
  42.                 continue
  43.             if (i, j) in no_left:
  44.                 answ[i][j] = answ[i - 1][j] + field_min[i][j]
  45.             elif (i, j) in no_up:
  46.                 answ[i][j] = answ[i][j - 1] + field_min[i][j]
  47.             else:
  48.                 answ[i][j] = min(answ[i][j - 1], answ[i - 1][j]) + field_min[i][j]
  49.     current = (n - 1, n - 1)
  50.     while current != start:
  51.         field_min[current[0]][current[1]] = inf
  52.         if current in no_left:
  53.             current = (current[0] - 1, current[1])
  54.         elif current in no_up:
  55.             current = (current[0], current[1] - 1)
  56.         elif answ[current[0] - 1][current[1]] <= answ[current[0]][current[1] - 1]:
  57.             current = (current[0] - 1, current[1])
  58.         else:
  59.             current = (current[0], current[1] - 1)
  60.     field_min[start[0]][start[1]] = inf
  61.     return answ[n - 1][n - 1]
  62.  
  63.  
  64. no_left_raw = [(0, (1, 19)), (1, (2, 12)), (2, (9, 12)), (3, (3, 4)), (5, (12, 16)), (6, (4, 7)), (7, (10, 16)), (10, (3, 4)), (10, (13, 17)), (11, (13, 16)), (13, (3, 9)), (16, (2, 4)), (16, (10, 18)), (18, (8, 16))]
  65. no_up_raw = [(0, (1, 19)), (1, (2, 5)), (8, (3, 3)), (3, (7, 8)), (9, (8, 8)), (18, (9, 9)), (15, (12, 14)), (19, (14, 5)), (5, (16, 16)), (16, (17, 17))]
  66. no_left = set()
  67. for e in no_left_raw:
  68.     for x in range(e[1][0], e[1][1] + 1):
  69.         no_left.add((x, e[0]))
  70. no_up = set()
  71. for e in no_up_raw:
  72.     for y in range(e[1][0], e[1][1] + 1):
  73.         no_up.add((e[0], y))
  74. starts = [(0, 0), (1, 1), (2, 3), (2, 10), (2, 13), (3, 6), (8, 2), (9, 7), (11, 5), (12, 11)]
  75. a = open('18.txt').readlines()
  76. n = len(a)
  77. for i in range(n):
  78.     a[i] = list(map(int, a[i].split()))
  79. answ_mx = 0
  80. answ_mn = inf
  81. for st1 in starts:
  82.     for st2 in starts:
  83.         if st2 == st1:
  84.             continue
  85.         for st3 in starts:
  86.             if st3 in [st1, st2]:
  87.                 continue
  88.             for st4 in starts:
  89.                 if st4 in [st1, st2, st3]:
  90.                     continue
  91.                 for st5 in starts:
  92.                     if st5 in [st1, st2, st3, st4]:
  93.                         continue
  94.                     field_max = [[0 for i in range(n)] for j in range(n)]
  95.                     for i in range(n):
  96.                         for j in range(n):
  97.                             field_max[i][j] = a[i][j]
  98.                     field_min = [[inf for i in range(n)] for j in range(n)]
  99.                     for i in range(n):
  100.                         for j in range(n):
  101.                             field_min[i][j] = a[i][j]
  102.                     cur_mx_answ = find_max(st1) + find_max(st2) + find_max(st3) + find_max(st4) + find_max(st5)
  103.                     cur_mn_answ = find_min(st1) + find_min(st2) + find_min(st3) + find_min(st4) + find_min(st5)
  104.                     answ_mx = max(answ_mx, cur_mx_answ)
  105.                     answ_mn = min(answ_mn, cur_mn_answ)
  106. print(answ_mn, answ_mx)
Advertisement
Add Comment
Please, Sign In to add comment