| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1161406 | browhatt | Type Printer (IOI08_printer) | C++20 | 0 ms | 0 KiB |
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)