Дважды два
Задачу добавил: alef
Успешно сдано решений: 3
Фирма "Фабрика классов" завершила разработку очередного этапа большого проекта для одного из своих основных заказчиков. По чистой случайности день завершения этапа совпал с днем рождения одного из основных разработчиков Степана Работнова. По такому случаю было решено устроить небольшое чаепитие. Рядом с офис-центром есть два супермаркета. Борис и Степан (как, впрочем, и другие сотрудники офис-центра) хорошо осведомлены о ценах в этих магазинах, и знают, что ряд продуктов стоит в обоих магазинах одинаково, однако некоторые продукты стоят дешевле в одном из супермаркетов, а некоторые - в другом.
Поэтому они договорились, что Борис пойдет в один супермаркет, а Степан в другой, и сделают закупку отличающихся по ценам продуктов там, где они дешевле. Что касается остальных продуктов, то их приобретение они хотели бы распределить таким образом, чтобы разница между весом пакетов, которые им придется нести, была бы минимально возможной.
Чтобы не путаться, они решили, что некоторый продукт покупается полностью либо в одном супермаркете, либо в другом.
Ваша задача - по списку продуктов и их весу определить, какие из них следует закупать в каком супермаркете.
Формат входного файла input.txt
Первая строка - целое число N (1 <= N <= 500) - общее количество продуктов, которое собрались приобрести Степан и Борис.
Каждая из следующих N строк содержит целые числа M и W через пробел и последовательность символов (строчные латинские символы и цифры, а также символ подчеркивания, без пробелов).
Число M может принимать значения:
0 - это означает, что данный продукт стоит одинаково в обоих супермаркетах
1 - данный продукт стоит дешевле в первом супермаркете
2 - данный продукт стоит дешевле во втором супермаркете
Число W обозначает вес продукта в некоторых единицах (1 <= W <= 400) Последовательность символов - уникальное наименование продукта
Формат выходного файла output.txt
Первая строка - положительное целое число - разница между весом продуктов, которые следует купить в первом супермаркете, и весом продуктов, которые следует купить во втором супермаркете, взятая по абсолютному значению.
Вторая строка - целое число K - количество продуктов, которые следует купить в первом супермаркете (включая те, которые стоят там дешевле)
Следующие K строк - наименования тех продуктов, которые следует купить в первом супермаркете (по одному в строке) в лексикографическом порядке.
Если решений несколько, выведите любое из них.
Пример входного файла
17 1 5 voda_mineralnaja 0 2 syr 2 3 bekon 0 1 salat_iz_kapusty 2 4 hleb 0 1 salat_iz_morkovi 0 2 golubcy 0 2 ryba_zapechennaja 1 3 kartofel_zhareny 1 2 tort 0 5 morozhenoje 0 2 tartaletki 1 6 sok 2 1 forel_narezka 2 2 banany 1 3 mandariny 0 2 yabloki
Пример выходного файла
0 8 kartofel_zhareny mandariny salat_iz_kapusty salat_iz_morkovi sok syr tort voda_mineralnaja