Второй вариант: я решил посчитать сколько изменений необходимо будет сделать, если в качестве эталона выбирать поочередно все города. Т.е. я посчитал для каждого города его суммарное отличие от всех остальных городов.
Второй и четвертый города одинаково похожи на выработанную схему, теме не менее, при выборе города 4 число изменений в остальных городах меньше, чем при выборе города 2.
Эталонная схема согласно пункту 2:
К сожалению, оказалось, что такое решение неверно, хотя бы потому, что иногда встречаются города с одинаковой схожестью с эталонной схемой (выбранной в пункте 2). Вот вам контрпример:
Выбираем город, чья схема распределения видов отходов по цветам максимально похожа на схему из пункта 2
Создаем схему соответствия цветов видам отходов, которые были выбраны в 1 пункте
Выбираем по каждому цвету вид отходов, который представлен данным цветом в максимальном количестве городов
Первый вариант (неверный) решения этой задачи, который мне пришел в голову почти мгновенно, таков:
Тем, кто хочет проверить собственные способности, в этом месте рекомендуется прерваться на создание собственного решения задачи, а потом вернуться, чтобы сравнить свои мысли, с нашими.
Пример входящих данных:
Выходные данные: На каждый входящий блок необходимо вывести порядковый номер города, чью схему распределения стоит выбрать в качестве эталона.
Входные данные: серия блоков. Каждый блок будет содержать несколько строк, выражающих распределение видов отходов по цветам, по 1 строке на каждый город. Городов может быть до 100. Каждый блок оканчивается строкой, начинающийся с символа «e». Конец входных данных ознаменуется строкой из одного символа "#".
Необходимо написать программу, которая считает данные о распределении видов отходов по цветам в каждом городе, и определит, какая схема должна быть выбрана. Имейте ввиду, что всегда будет явный лидер.
В Новую Зеландию прибыла технология сбора мусора . Пять мусорных корзин разных цветов: красный (red), оранжевый (orange), желтый (yellow), зеленый(green) и синий (blue), в которые определены 5 видов отходов: пластиковые отходы (Plastic), стеклянные (Glass), алюминиевые (Aluminium), стальные(Steel) и бумажные (Newspaper). К сожалению, никакой координации между городами не было, поэтому каждый город поставил в соответствие цветным корзинам произвольный вид отходов. Теперь, когда правительство смогло решить все маловажные задачи (вроде реорганизации здравоохранения, соц. обеспечения и образования), оно решило заняться другими проблемами. Министр охраны окружающей среды представил в парламент документ о регулировании соответствия видов отходов цветными корзинами, но для этого ему необходимо выбрать собственное распределение отходов по цветам. Будучи сторонником демократии, он исследовал все города, которые используют Kerbside. С помощью полученных данных он хочет выбрать город, чья схема соответствия видов отходов цветным корзинам (будучи распространенной по всей стране) вызовет наименьшее количество изменений. Размер города не имеет значения, согласно демократии: 1 город 1 голос.
Краткий перевод условия задачи (вольный перевод):
Напоминаю, что я беру задачи с сайта , и сегодня случайный выбор пал на задачу об утилизации отходов.
Вы не забыли ? Если забыли, то быстренько разминайтесь, и возвращайтесь к нам.
Привет. С вами олимпиадное хобби. Здесь мы выбираем себе олимпиадную задачу по программированию, разбираем ее, вырабатываем возможные пути решения и реализовываем задуманное, после чего отправляем на суд. Нам потребуется знание одного из языков программирования: c, c++, java, pascal, терпение, ловкость и базовые знания английского языка, чтобы понимать условие задачи, хотя последний пункт необязателен, ведь я вольно перескажу условие на русском языке.
Олимпиадное хобби. Задача об утилизации отходов
Олимпиадное хобби. Задача об утилизации отходов / Хабрахабр
Комментариев нет:
Отправить комментарий