Pull to refresh

Олимпиадное хобби. Задача об утилизации отходов

Reading time 4 min
Views 3.3K
Привет. С вами олимпиадное хобби. Здесь мы выбираем себе олимпиадную задачу по программированию, разбираем ее, вырабатываем возможные пути решения и реализовываем задуманное, после чего отправляем на суд. Нам потребуется знание одного из языков программирования: c, c++, java, pascal, терпение, ловкость и базовые знания английского языка, чтобы понимать условие задачи, хотя последний пункт необязателен, ведь я вольно перескажу условие на русском языке.

Вы не забыли размяться? Если забыли, то быстренько разминайтесь, и возвращайтесь к нам.

Напоминаю, что я беру задачи с сайта http://uva.onlinejudge.org, и сегодня случайный выбор пал на задачку под номером 154 — задачу об утилизации отходов.

Краткий перевод условия задачи (вольный перевод):

В Новую Зеландию прибыла технология сбора мусора Kerbside. Пять мусорных корзин разных цветов: красный (red), оранжевый (orange), желтый (yellow), зеленый(green) и синий (blue), в которые определены 5 видов отходов: пластиковые отходы (Plastic), стеклянные (Glass), алюминиевые (Aluminium), стальные(Steel) и бумажные (Newspaper). К сожалению, никакой координации между городами не было, поэтому каждый город поставил в соответствие цветным корзинам произвольный вид отходов. Теперь, когда правительство смогло решить все маловажные задачи (вроде реорганизации здравоохранения, соц. обеспечения и образования), оно решило заняться другими проблемами. Министр охраны окружающей среды представил в парламент документ о регулировании соответствия видов отходов цветными корзинами, но для этого ему необходимо выбрать собственное распределение отходов по цветам. Будучи сторонником демократии, он исследовал все города, которые используют Kerbside. С помощью полученных данных он хочет выбрать город, чья схема соответствия видов отходов цветным корзинам (будучи распространенной по всей стране) вызовет наименьшее количество изменений. Размер города не имеет значения, согласно демократии: 1 город — 1 голос.

Необходимо написать программу, которая считает данные о распределении видов отходов по цветам в каждом городе, и определит, какая схема должна быть выбрана. Имейте ввиду, что всегда будет явный лидер.

Входные данные: серия блоков. Каждый блок будет содержать несколько строк, выражающих распределение видов отходов по цветам, по 1 строке на каждый город. Городов может быть до 100. Каждый блок оканчивается строкой, начинающийся с символа «e». Конец входных данных ознаменуется строкой из одного символа "#".

Выходные данные: На каждый входящий блок необходимо вывести порядковый номер города, чью схему распределения стоит выбрать в качестве эталона.

Пример входящих данных:
r/P,o/G,y/S,g/A,b/N
r/G,o/P,y/S,g/A,b/N
r/P,y/S,o/G,g/N,b/A
r/P,o/S,y/A,g/G,b/N
e
r/G,o/P,y/S,g/A,b/N
r/P,y/S,o/G,g/N,b/A
r/P,o/S,y/A,g/G,b/N
r/P,o/G,y/S,g/A,b/N
ecclesiastical
#

Результат:
1
4


Тем, кто хочет проверить собственные способности, в этом месте рекомендуется прерваться на создание собственного решения задачи, а потом вернуться, чтобы сравнить свои мысли, с нашими.

Первый вариант (неверный) решения этой задачи, который мне пришел в голову почти мгновенно, таков:
  1. Выбираем по каждому цвету вид отходов, который представлен данным цветом в максимальном количестве городов
  2. Создаем схему соответствия цветов видам отходов, которые были выбраны в 1 пункте
  3. Выбираем город, чья схема распределения видов отходов по цветам максимально похожа на схему из пункта 2

К сожалению, оказалось, что такое решение неверно, хотя бы потому, что иногда встречаются города с одинаковой схожестью с эталонной схемой (выбранной в пункте 2). Вот вам контрпример:
r/P,o/G,y/S,g/A,b/N
r/P,o/S,y/A,g/N,b/G
r/S,o/G,y/P,g/N,b/G
r/A,o/S,y/P,g/N,b/G
r/G,o/S,y/P,g/A,b/N

Эталонная схема согласно пункту 2:
r/P.o/S,y/P,g/N,b/G

Второй и четвертый города одинаково похожи на выработанную схему, теме не менее, при выборе города №4 число изменений в остальных городах меньше, чем при выборе города №2.

Второй вариант: я решил посчитать сколько изменений необходимо будет сделать, если в качестве эталона выбирать поочередно все города. Т.е. я посчитал для каждого города его суммарное отличие от всех остальных городов.

Изначально, мне казалось такое решение не оптимальным, казалось, что оно непременно выйдет за лимит времени. Но давайте попробуем оценить, как много времени займет такой подсчет количества отличий каждого города от всех остальных.

Каждый город необходимо сравнить со всеми остальными, причем сравнений будет 5, по каждому цвету, т.е. 5(n-1) сравнений на каждый город, где n — количество городов. В сумме выходит 5n(n-1) сравнений на все города. Если принять во внимание тот факт, что городов не больше 100, то число сравнений не превосходит 5*100*99=49500. Операции сравнения также будут сопровождаться операциями наращивания счетчика различия каждого города. Но даже в сумме, при наихудших условиях, число операций не превысит 49500 сравнений и 49500 операций прибавления единицы. Становится ясно, что наш алгоритм выполнится за очень короткий промежуток времени даже на самых сложных тестах.

Попробуем посчитать число отличий для одного из примеров и предыдущего контрпримера к варианту решения №1:
Схема Число отличий от других городов
r/P,o/G,y/S,g/A,b/N
r/G,o/P,y/S,g/A,b/N
r/P,y/S,o/G,g/N,b/A
r/P,o/S,y/A,g/G,b/N
1+2+1+2+1 = 7 < — лучший вариант
3+3+1+2+1 = 10
1+2+1+3+3 = 10
1+3+3+3+1 = 11
r/P,o/G,y/S,g/A,b/N
r/P,o/S,y/A,g/N,b/G
r/S,o/G,y/P,g/N,b/G
r/A,o/S,y/P,g/N,b/G
r/G,o/S,y/P,g/A,b/N
3+3+4+3+3 = 16
3+2+4+2+2 = 13
4+3+2+2+2 = 13
4+2+2+2+2 = 12 < — лучший вариант
4+2+2+3+3 = 14

Собственно остается реализовать задуманное и нести к судьям. А здесь мое решение на C++.

Accepted (0.012). Удачи!
Tags:
Hubs:
+23
Comments 35
Comments Comments 35

Articles