fork download
copy 
  1. def fits_at(r, c, height, width, N, M, field):
  2.  
  3.     if r + height > N or c + width > M:
  4.         return False
  5.  
  6.     for row in range(r, r + height):
  7.         for col in range(c, c + width):
  8.             if field[row][col] == 1:
  9.                 return False
  10.     return True
  11.  
  12. # 0KXRgNGW0L/Rg9C90L7Qsg==
  13.  
  14. def dp_solve(index, N, M, P, K, field, memo):
  15.     if index >= N * M:
  16.         return 0
  17.  
  18.     if memo[index] != -1:
  19.         return memo[index]
  20.  
  21.     r = index // M
  22.     c = index % M
  23.  
  24.     max_garages = dp_solve(index + 1, N, M, P, K, field, memo)
  25.  
  26.     if fits_at(r, c, P, K, N, M, field):
  27.         next_c = c + K
  28.         next_r = r + (next_c // M)
  29.  
  30.         next_index = next_r * M + (next_c % M)
  31.  
  32.         garages_if_placed = 1 + dp_solve(next_index, N, M, P, K, field, memo)
  33.         max_garages = max(max_garages, garages_if_placed)
  34.  
  35.     memo[index] = max_garages
  36.     return max_garages
  37.  
  38.  
  39. def find_max_garages(N, M, P, K, field):
  40.  
  41.     memo_pk = [-1] * (N * M + 1)
  42.     result_pk = dp_solve(0, N, M, P, K, field, memo_pk)
  43.  
  44.     final_result = result_pk
  45.  
  46.     if P != K:
  47.         memo_kp = [-1] * (N * M + 1)
  48.         result_kp = dp_solve(0, N, M, K, P, field, memo_kp)
  49.  
  50.         final_result = max(result_pk, result_kp)
  51.  
  52.     return final_result
  53.  
  54.  
  55. def solve():
  56.     try:
  57.         line1 = input("Введіть розміри поля N M (наприклад, 8 8): ").split()
  58.         if len(line1) < 2:
  59.             raise ValueError("Потрібно ввести два числа: N та M.")
  60.         N = int(line1[0])
  61.         M = int(line1[1])
  62.  
  63.         line2 = input("Введіть розміри гаража P K (наприклад, 2 3): ").split()
  64.         if len(line2) < 2:
  65.             raise ValueError("Потрібно ввести два числа: P та K.")
  66.         P = int(line2[0])
  67.         K = int(line2[1])
  68.  
  69.         print(f"Введіть поле {N}x{M}, де '1' - дерево, '0' - вільна ділянка. Кожен рядок - через пробіл:")
  70.         field = []
  71.         for i in range(N):
  72.             row_input = input(f"Рядок {i}: ").split()
  73.             if len(row_input) != M:
  74.                 print(f"Помилка: Рядок {i} повинен містити {M} елементів.")
  75.                 return
  76.             field.append([int(x) for x in row_input])
  77.  
  78.     except Exception as e:
  79.         print(f"Помилка вводу: {e}")
  80.         return
  81.  
  82.     if N > 50 or M > 50:
  83.         print("Помилка: N та M не повинні перевищувати 50.")
  84.         return
  85.  
  86.     max_garages = find_max_garages(N, M, P, K, field)
  87.  
  88.     print(f"\nМаксимальна кількість прямокутних гаражів ({P}x{K} або {K}x{P}), які можна розмістити: {max_garages}")
  89.  
  90. solve()
  91.  
Success #stdin #stdout 0.09s 14212KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Введіть розміри поля N M (наприклад, 8 8): Помилка вводу: EOF when reading a line
https://ideone.com/HtdR4f
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!