Submission #1161423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161423		browhatt	Type Printer (IOI08_printer)	Pypy 3	30 / 100	1104 ms	327680 KiB

printer

def get_operations(prev, curr):
    """Calculate operations needed to transform prev to curr"""
    i = 0
    min_len = min(len(prev), len(curr))
    
    # Find common prefix length
    while i < min_len and prev[i] == curr[i]:
        i += 1
        
    # Calculate operations
    backspace = len(prev) - i
    additions = len(curr) - i
    
    return backspace + additions + 1  # +1 for print operation

def get_operation_sequence(prev, curr):
    """Get actual sequence of operations"""
    ops = []
    i = 0
    min_len = min(len(prev), len(curr))
    
    # Find common prefix length
    while i < min_len and prev[i] == curr[i]:
        i += 1
        
    # Add backspace operations
    ops.extend(['-'] * (len(prev) - i))
    
    # Add new characters
    ops.extend(list(curr[i:]))
    
    # Add print operation
    ops.append('P')
    
    return ops

def solve(words):
    n = len(words)
    if n == 1:
        return list(words[0]) + ['P']
    
    # Create adjacency matrix of operation costs
    costs = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i != j:
                costs[i][j] = get_operations(words[i], words[j])
    
    # Initialize dp table for TSP-like approach
    dp = {}
    
    def find_min_cost(mask, pos):
        if mask == (1 << n) - 1:  # All words printed
            return 0
            
        state = (mask, pos)
        if state in dp:
            return dp[state]
            
        min_cost = float('inf')
        for next_pos in range(n):
            if not (mask & (1 << next_pos)):
                cost = (len(words[next_pos]) + 1) if pos == -1 else costs[pos][next_pos]
                total = cost + find_min_cost(mask | (1 << next_pos), next_pos)
                min_cost = min(min_cost, total)
                
        dp[state] = min_cost
        return min_cost
    
    # Find optimal path
    def reconstruct_path():
        path = []
        mask = 0
        pos = -1
        
        while mask != (1 << n) - 1:
            next_best = -1
            min_remaining = float('inf')
            
            for next_pos in range(n):
                if not (mask & (1 << next_pos)):
                    cost = (len(words[next_pos]) + 1) if pos == -1 else costs[pos][next_pos]
                    remaining = find_min_cost(mask | (1 << next_pos), next_pos)
                    if cost + remaining < min_remaining:
                        min_remaining = cost + remaining
                        next_best = next_pos
            
            # Add operations for this word
            curr = "" if pos == -1 else words[pos]
            path.extend(get_operation_sequence(curr, words[next_best]))
            
            mask |= (1 << next_best)
            pos = next_best
            
        return path
    
    # Find minimum cost first
    find_min_cost(0, -1)
    
    # Reconstruct the path
    return reconstruct_path()

# Read input
n = int(input())
words = [input().strip() for _ in range(n)]

# Get solution
operations = solve(words)

# Print output
print(len(operations))
for op in operations:
    print(op)

Compilation message (stdout)

Compiling 'printer.py'...

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

=======

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10