def move(target_i, target_j): global cost global ANS global current_i, current_j b = sum(B) while (current_i, current_j) != (target_i, target_j): if current_i < target_i: ANS.append((1, "D")) current_i += 1 elif current_i > target_i: ANS.append((1, "U")) current_i -= 1 elif current_j < target_j: ANS.append((1, "R")) current_j += 1 elif current_j > target_j: ANS.append((1, "L")) current_j -= 1 cost += (1 if A[current_i][current_j] == "." else 2) * (b + 1) ** 2 def buy(k): global cost assert A[current_i][current_j] == "@" cost += price[k] B[k] += 1 ANS.append((2, k + 1)) if DEBUG: print("buy", k, "@", (current_i, current_j)) def bomb_check(k, ii, jj): s = 0 t = 0 for i, j in Z[k][1]: ni = ii + i nj = jj + j if 0 <= ni < N and 0 <= nj < N and A[ni][nj] != ".": if A[ni][nj] == "@": s += 1 else: t += 1 def bomb(k): assert B[k] > 0 global shop_list B[k] -= 1 ANS.append((3, k + 1)) for i, j in Z[k][1]: ni = current_i + i nj = current_j + j if 0 <= ni < N and 0 <= nj < N and A[ni][nj] != ".": if A[ni][nj] == "@": shop_list.remove((ni, nj)) A[ni][nj] = "X" if DEBUG: print("bomb", k, "@", (current_i, current_j)) def answer(): print(len(ANS)) for a, b in ANS: print(a, b) if DEBUG: print("cost =", cost) writetext_output(ANS) def disp(): if DEBUG: print("") print("-" * 20) building_cnt = sum(a.count("#") for a in A) shop_cnt = sum(a.count("@") for a in A) print("building cnt =", building_cnt) print("shop cnt =", shop_cnt) print("shop_list =", len(shop_list), shop_list) print("cost =", cost) print("A =") for a in A: print("".join(a)) print("-" * 20) print("") try: LOCAL except NameError: LOCAL = 0 if LOCAL: DEBUG = 1 N, M, A, Z = random_testcase() else: DEBUG = 0 N, M = map(int, input().split()) A = [] for _ in range(N): A.append([a for a in input()]) Z = [] for _ in range(M): C, L = map(int, input().split()) pos = [] for _ in range(L): a, b = map(int, input().split()) pos.append((a, b)) Z.append((C, pos)) if DEBUG: writetext_input(N, M, A, Z) price = [] B = [0] * M cost = 0 current_i = 0 current_j = 0 ANS = [] if DEBUG: print("N =", N) print("M =", M) shop_list = [] for i, a in enumerate(A): for j, aa in enumerate(a): if aa == "@": shop_list.append((i, j)) disp() for C, pos in Z: if DEBUG: print("C, cnt =", C, len(pos), "{:.4f}".format(len(pos) / C)) print("pos =", pos) price.append(C) if 0: print("") print("C =", C) print("cnt =", len(pos)) z = [["."] * 41 for _ in range(41)] for i, j in pos: z[i+20][j+20] = "#" if 0: print("pos =") for zz in z: print("".join(zz)) def best_shop(i, j): best_i = -1 best_j = -1 best = 1000 for ti, tj in shop_list: d = abs(ti - i) + abs(tj - j) d += (max(10 - ti, 0) + max(ti - 39, 0) + max(10 - tj, 0) + max(tj - 39, 0)) * 5 if 21 <= ti < 29: d += 15 if 21 <= tj < 29: d += 15 if d < best: best = d best_i = ti best_j = tj return best_i, best_j while shop_list: move(*best_shop(current_i, current_j)) ni = current_i + 1 if current_i < N - 1 else current_i - 1 nj = current_j + 1 if current_j < N - 1 else current_j - 1 for k in range(M): buy(k) buy(k) buy(k) for k in range(M): bomb(k) move(ni, current_j) for k in range(M): bomb(k) move(ni, nj) for k in range(M): bomb(k) answer() disp()