Помогите пожалуйста
Скупой рыцарь хранит в подвале множество сундуков. Сундуки занумерованы, начиная с единицы. В сундуках лежат монеты. О содержимом каждого сундука есть опись. Опись пустого сундука -- пустая строка. Опись непустого сундука состоит из одной или нескольких записей. Каждая запись -- это сведения о стопке монет одного достоинства, лежащей в сундуке. В начале записи указано количество монет в стопке -- положительное беззнаковое целое число без незначащих нулей. Количество монет в одной стопке не превышает 1000. За количеством следует символ обозначающий достоинство монет в стопке -- строчная латинская буква: a означает монету номиналом 1 копейка; b -- 5 копеек; с -- 10 копеек; d -- 50 копеек; e -- 1 рубль или 100 копеек; f -- 2 рубля; g -- 5 рублей; h -- 10 рублей; i -- 25 рублей. Записи в описи никак не упорядочены, так как скупой рыцарь добавляет стопки монет в сундуки без какой-либо системы. В описи могут быть записи о стопках монет одного и того же достоинства. Например, опись 1a2b1a1h1i1h1i1h1i означает, что в сундуке лежат 105 рублей и 12 копеек (две монеты номиналом 1 копейка; две монеты номиналом 5 копеек; три монеты номиналом 10 рублей; три монеты номиналом 25 рублей).
Скупой рыцарь хочет найти в своём подвале два сундука, таких, чтобы разность денежных сумм, лежащих в них, была максимальной. Если в подвале есть несколько искомых пар сундуков, то скупой рыцарь выбирает из них такую пару, что сумма номеров сундуков минимальна.
Составьте программу, принимающую на вход в первой строке десятичное число N -- положительное натуральное число (1 < N < 101) -- количество сундуков, а в последующих N строках -- описи сундуков с номерами от 1 до N. Известно, что в каждой описи не более чем 500 символов (цифр и латинских букв). Программа находит номера K и L такие, что K < L, абсолютное значение (модуль) разницы количеств денег в K-ом и L-ом сундуках наибольшее и сумма K+L наименьшая. Программа выводит в первой строке найденное число K, а во второй строке -- L. Каждое число записывается в десятичной системе без знака и без незначащих нулей.
Формат входных данных
В первой строке содержится десятичное число N — количество сундуков (1 < N < 101). В следующих N строках содержатся описи монет из сундуков -- последовательности, в которых могут встретиться только строчные латинские буквы a, b, ..., i и десятичные цифры. Эти последовательности записаны по правилам составления описей сундуков Длины строк находятся в диапазоне от 0 до 500 включительно.
Формат результата
В первой строке выводится беззнаковое десятичное натуральное число K. Во второй строке выводится беззнаковое десятичное натуральное число L. Числа K и L таковы, что K
Ответы
Код на Python:
def parse_inventory(inventory_str):
inventory = {}
i = 0
while i < len(inventory_str):
count = ""
while i < len(inventory_str) and inventory_str[i].isdigit():
count += inventory_str[i]
i += 1
coin_type = inventory_str[i]
inventory[coin_type] = inventory.get(coin_type, 0) + int(count) if count else 1
i += 1
return inventory
def find_max_difference(n, inventories):
max_difference = 0
min_sum = float('inf')
result = (0, 0)
for i in range(n - 1):
for j in range(i + 1, n):
sum_i = sum(value * (ord(coin_type) - ord('a') + 1) for coin_type, value in inventories[i].items())
sum_j = sum(value * (ord(coin_type) - ord('a') + 1) for coin_type, value in inventories[j].items())
current_difference = abs(sum_i - sum_j)
current_sum = i + 1 + j + 1
if current_difference > max_difference or (current_difference == max_difference and current_sum < min_sum):
max_difference = current_difference
min_sum = current_sum
result = (i + 1, j + 1)
return result
# Зчитуємо кількість сундуків
n = int(input())
# Зчитуємо описи сундуків та парсимо їх
inventories = [parse_inventory(input()) for _ in range(n)]
# Знаходимо номери сундуків K та L
result = find_max_difference(n, inventories)
# Виводимо результат
print(result[0])
print(result[1])