| Автор: | А. Бахтурин | Ограничение времени: | 1 сек | |
| Входной файл: | test.sql | Ограничение памяти: | 256 Мб | |
| Выходной файл: | test.log |
Известная всем страна Камнепадия славится своей добычей драгоценных камней, чем привлекает многих туристов. Основными добываемыми драгоценностями являются рубины, изумруды и сапфиры. Три крупных компании: "Рубинусы", "Изумрудсы" и "Сапфирсы" - поделили рынок между собой, и каждая компания занимается добычей только одного камня. Каждая компания имеет по одному фирменному магазину с камнями в каждом городе.
Один очень хитрый господин по имени Дроп Датабейсович узнал, что в фирменных магазинах повсеместно используют язык SQL, а еще он разузнал, что компании в Камнепадии не обладают тайным знанием защиты от SQL-инъекций. Дроп Датабейсович решил разжиться драгоценностями, воспользовавшись своим громким именем, у которого есть одно интересное свойство. Каждый раз, когда Дроп Датабейсович каким-то образом взаимодействует с непродвинутыми компаниями, которые не знают, что такое SQL-инъекция, их база данных магическим образом падает, и он может извлечь из этого выгоду.
Дроп Датабейсович начал планировать свою поездку по Камнепадии. Свой путь он думает начать в городе "Tarataika", а закончить в городе "Agapovka". В каждом городе Дроп Датабейсович может выбрать, в каких магазинах уронить базу данных и забрать все камни себе. Он может ограбить любое число магазинов в городе, в том числе ни одного. Ему нужно найти все пути между начальным и конечным городами с максимальной суммой всех полученных драгоценностей, и выбрать из них самые короткие. Однако всё не так просто. Как только Дроп Датабейсович провернёт махинацию в одном фирменном магазине, все остальные магазины этой компании поймут, в чём дело, и поставят защиту от SQL-инъекций, из-за чего он не сможет больше ничего получить из их магазинов. Также, с каждым пройденным городом количество камней в каждом магазине страны будет уменьшаться на единицу, из-за того, что драгоценности будут скупать другие люди, а так как камешки невероятно дорогие, то, чтобы купить хотя бы 1 камень, жители скидываются на него всем городом.
Господин Дроп Датабейсович раздобыл базу данных городов с текущим количеством камней в магазинах, а также карту всех дорог между городами в Камнепадии.
CREATE TABLE IF NOT EXISTS Cities (
id INTEGER PRIMARY KEY,
name TEXT NOT NULL,
rubies INTEGER NOT NULL, -- число рубинов в магазине
emeralds INTEGER NOT NULL, -- число изумрудов в магазине
sapphires INTEGER NOT NULL -- число сапфиров в магазине
);
CREATE TABLE IF NOT EXISTS Roads (
from_city_id INTEGER REFERENCES Cities(id),
to_city_id INTEGER REFERENCES Cities(id),
PRIMARY KEY (from_city_id, to_city_id)
);
Дроп Датабейсовичу нужно составить SQL запрос, который покажет все самые выгодные варианты с наибольшим числом собранных камней и наименьшей длиной пути. Результатом запроса должен быть список кортежей (path, total_jewelry, ruby_city, emerald_city, sapphire_city), отсортированных по возрастанию по всем полям кортежа слева направо, где path: путь в формате "Tarataika -> ... -> Agapovka", total_jewelry: сумма всех драгоценных камней полученная в пути, ruby_city, emerald_city, sapphire_city: названия городов, в которых нужно забрать рубины, изумруды и сапфиры соответственно. Также нужно учитывать, что в пределах одного пути Дроп Датабейсович может получить максимальное число камней разными способами в зависимости от того, из каких городов берёт камни.
Решение следует представить в виде текстового файла, содержащего единственный SQL-запрос.
Предполагается, что для работы с базой данных используется SQLite3.