ЕГЭ-27. Анализ данных. Кластеризация

На столе выложили цепочку из N костяшек по принципу домино. Под костяшкой понимается пара любых неотрицательных чисел, каждое не превышает 100. В наборе нет двух одинаковых костяшек (как в домино). Переставлять местами костяшки нельзя, но можно поворачивать любую костяшку, получая из костяшки 1-2 костяшку 2-1. 
Определите максимально длинную цепочку костяшек домино, которую можно получить. Под цепочкой следует понимать последовательность костяшек, у которой второе число первой костяшки равно первому числу второй.

На вход программы подается 366 строк, которые содержат информацию о среднесуточной температуре всех дней 2008 года. Формат каждой из строк следующий: сначала записана дата в виде dd.mm (на запись номера дня и номера месяца в числовом формате отводится строго два символа, день от месяца отделен точкой), затем через пробел записано значение температуры — число со знаком плюс или минус, с точностью до 1 цифры после десятичной точки. Данная информация отсортирована по значению температуры, то есть хронологический порядок нарушен. 

Требуется написать программу, которая будет выводить на экран информацию о месяце (месяцах), среднемесячная температура у которого (которых) наименее отклоняется от среднегодовой. Отклонения считаются одинаковыми, если разница между ними по модулю не превышает 0.00001.
В первой строке вывести среднегодовую температуру. Найденные значения для каждого из месяцев следует выводить в отдельной строке.
Формат вывода:
среднегодовая_температура 
номер_месяца значение_среднемесячной_температуры отклонение_от_среднегодовой_температуры

На вход программе сначала подается число участников олимпиады N. В каждой из следующих N строк находится результат одного из участников олимпиады в следующем формате:
<Фамилия> <Имя> <класс> <баллы>,

где <Фамилия> – символьная строка (не более 20 символов);
- <Имя> – символьная строка (не более 15 символов);
- <класс> – число от 7 до 11;
- <баллы> – целое число набранных участником баллов. 

<Фамилия> и <Имя>, <Имя> и <класс>, а также <класс> и <баллы> разделены одним пробелом.

Пример входной строки:

Семенов Егор 11 225

Победителем олимпиады становится участник, набравший наибольшее количество баллов, при условии, что он набрал более 200 баллов. Если такое количество баллов набрали несколько участников, то все они признаются победителями при выполнении условия, что их доля не превышает 20% от общего числа участников.
Победителем олимпиады не признается никто, если нет участников, набравших больше 200 баллов, или больше 20% от общего числа участников набрали одинаковый наибольший балл.
Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять фамилию и имя лучшего участника, не ставшего победителем олимпиады. Если таких участников несколько, т.е. если следующий за баллом победителей один и тот же балл набрали несколько человек, или, если победителей нет, а лучших участников несколько (в этом случае именно они являются искомыми), то выдается только количество искомых участников. Гарантируется, что искомые участники (участник) имеются. 

Программа должна выводить через пробел фамилию и имя искомого участника или их количество.

Пример выходных данных (один искомый участник):

Семенов Егор
 

Второй вариант выходных данных (несколько искомых участников):

12

 

На вход программе подаются сведения о пассажирах, сдавших свой багаж в камеру хранения. В первой строке задано текущее время: через двоеточие два целых числа, соответствующие часам (от 00 до 21, ровно 2 символа) и минутам (от 00 до 59, ровно 2 символа). Во второй строке задается количество пассажиров N, которое не меньше 10, но не превосходит 1000. В каждой из последующих N строк находится информация о пассажирах в следующем формате: 

<Фамилия> <Время освобождения ячейки>,

где <Фамилия> – строка, состоящая не более, чем из 20 символов без пробелов, <Время освобождения ячейки> – через двоеточие два целых числа, соответствующие часам (от 00 до 21, ровно 2 символа) и минутам (от 00 до 59, ровно 2 символа). <Фамилия> и <Время освобождения ячейки> разделены ровно одним пробелом.

Пример входных строк

10:00

3

Иванов 12:00

Петров 10:12

Сидоров 12:12 

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

Петров

Иванов

 

В молочных магазинах города Х продается сметана с жирностью 15, 20 и 25 процентов. В городе X был проведен мониторинг цен на сметану. Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять для каждого вида сметаны, сколько магазинов продают ее дешевле всего. На вход программе сначала подается число магазинов N. В каждой из следующих N строк находится информация в следующем формате:

где <Фирма> – строка, состоящая не более, чем из 20 символов без пробелов, <Улица> – строка, состоящая не более, чем из 20 символов без пробелов, <Жирность> – одно из чисел – 15, 20 или 25, <Цена> – целое число в диапазоне от 2000 до 5000, обозначающее стоимость одного литра сметаны в копейках.
<Фирма> и <Улица>, <Улица> и <Жирность>, а также <Жирность> и <Цена> разделены ровно одним пробелом.

Пример входной строки:

Перекресток Короленко 25 3200

Программа должна выводить через пробел 3 числа – количество магазинов, продающих дешевле всего сметану с жирностью 15, 20 и 25 процентов. Если какой-то вид сметаны нигде не продавался, то следует вывести 0.

Пример выходных данных:

12 10 0