Submission #1161407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161407		browhatt	Type Printer (IOI08_printer)	Pypy 3	10 / 100	1101 ms	155120 KiB

printer

def get_common_prefix_length(word1, word2):
    """Returns the length of common prefix between two words"""
    i = 0
    while i < len(word1) and i < len(word2) and word1[i] == word2[i]:
        i += 1
    return i

def get_operations(prev_word, curr_word):
    """Returns list of operations needed to transform prev_word to curr_word"""
    operations = []
    common_length = get_common_prefix_length(prev_word, curr_word)
    
    # Remove extra characters from previous word
    for _ in range(len(prev_word) - common_length):
        operations.append('-')
    
    # Add new characters for current word
    for i in range(common_length, len(curr_word)):
        operations.append(curr_word[i])
    
    # Print the word
    operations.append('P')
    return operations

def find_optimal_sequence(words):
    """Find optimal sequence of words and return operations"""
    n = len(words)
    if n == 0:
        return []
    
    # Try each word as the first word
    min_operations = float('inf')
    best_sequence = None
    
    def get_total_operations(sequence):
        operations = []
        prev_word = ""
        for word in sequence:
            operations.extend(get_operations(prev_word, word))
            prev_word = word
        return operations
    
    # Try each word as starting point
    for first_word in words:
        # Start with this word
        current_sequence = [first_word]
        remaining_words = words.copy()
        remaining_words.remove(first_word)
        
        # Greedily choose next word based on maximum common prefix
        while remaining_words:
            last_word = current_sequence[-1]
            best_next_word = max(remaining_words, 
                               key=lambda w: get_common_prefix_length(last_word, w))
            current_sequence.append(best_next_word)
            remaining_words.remove(best_next_word)
        
        # Calculate operations for this sequence
        current_operations = get_total_operations(current_sequence)
        if len(current_operations) < min_operations:
            min_operations = len(current_operations)
            best_sequence = current_operations
    
    return best_sequence

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

# Find optimal sequence of operations
operations = find_optimal_sequence(words)

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

Compilation message (stdout)

Compiling 'printer.py'...

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

=======

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 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