Submission #1148088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148088		montes_jose	Coin Collecting (JOI19_ho_t4)	Pypy 3	0 / 100	1098 ms	263524 KiB

joi2019_ho_t4

from collections import deque

def bfs(start_x, start_y, target_x, target_y):
    """Performs BFS to compute shortest path from (start_x, start_y) to (target_x, target_y)."""
    queue = deque([(start_x, start_y, 0)])  # (x, y, steps)
    visited = set()
    visited.add((start_x, start_y))

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # Up, Down, Right, Left

    while queue:
        x, y, steps = queue.popleft()
        
        if (x, y) == (target_x, target_y):
            return steps  # Found shortest path
        
        for dx, dy in directions:
            new_x, new_y = x + dx, y + dy
            if (new_x, new_y) not in visited:
                visited.add((new_x, new_y))
                queue.append((new_x, new_y, steps + 1))
    
    return float('inf')  # Should not reach here

def min_operations_to_rearrange_coins(N, coins):
    """
    Given N and a list of 2N coin positions, compute the minimum operations needed
    to place them in a (N × 2) grid using BFS.
    """
    # Target positions: (1,1) to (N,2)
    targets = [(x, y) for x in range(1, N + 1) for y in range(1, 3)]
    
    # Sorting helps in reducing mismatches (greedy approach)
    coins.sort()
    targets.sort()
    
    total_moves = 0
    
    # Assign each coin to a target and compute BFS
    for i in range(2 * N):
        total_moves += bfs(coins[i][0], coins[i][1], targets[i][0], targets[i][1])

    return total_moves

# Read input
N = int(input())
coins = [tuple(map(int, input().split())) for _ in range(2 * N)]

# Compute and print result
print(min_operations_to_rearrange_coins(N, coins))

Compilation message (stdout)

Compiling 'joi2019_ho_t4.py'...

=======
  adding: __main__.pyc (deflated 40%)

=======

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63