0014. Выставка кошек

Имя входного файла:	cats.in
Имя выходного файла:	cats.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

Выставка кошек ≈ это своеобразный конкурс их красоты. О том, по каким критериям в ыбирается лучший представитель породы, и какой должна быть идеальная кошка ≈ написано в Стандарте. Для каждой породы стандартом предусматривается описание фенотипа кошки по нескольким параметрам: вес, размер, высота в холке, длина хвоста, постав ушей, окрас шерсти, цветовое распределение и т.п.

В зависимости от значения каждого из параметров, кошка получает соответствующие баллы. Например, если кошка весит от 0 до 2 кг, то ей присуждается 1 балл, от 3 до 5 кг - 2 балла, от 6 до 100 кг - 3 балла. Суммарная оценка кошки равна сумме оценок по каждому из ее параметров.

Для участия в городской выставке зарегистрировано N кошек. О каждой кошке известны ее кличка и значения всех оцениваемых параметров. Вам, как председателю жюри, необходимо определить победителей и раздать дипломы. Для этого в итоговой таблице результатов необходимо упорядочить кошек по убыванию суммарной оценки. Если оценки некоторых кошек совпадают, то вывести их клички в алфавитном порядке.

Формат входного файла

Первая строка входного файла содержит два числа N и M (1 ≤ N, M ≤ 100) √ количество кошек и оцениваемых параметров. Затем следуют M блоков, соответствующих каждому параметру. В блоке указаны диапазоны и баллы, которые получает участник, если соответствующий параметр окажется в некотором диапазоне. В первой строке каждого блока указано число диапазонов K (1 ≤ K ≤ 100), а следующие K строк содержат по три числа: значение нижней и верхней границ диапазона, а также балл за диапазон. Объединение диапазонов обязательно охватывает все возможные значения данного параметра. Диапазоны не пересекаются.

Затем идет N строк, в каждой из которых содержится: кличка кошки (длиной не более 20 прописных символов латинского алфавита) и список значений ее параметров - M чисел, разделенных пробелами. Все числа √ целые, неотрицательные и не превышают 100, клички кошек могут повторяться.

Формат выходного файла

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

Пример:

cats.in	cats.out
4 3 2 0 2 1 3 100 4 3 0 4 2 5 10 3 11 100 1 3 0 10 5 11 40 6 41 80 12 betty 1 6 2 alisa 2 67 23 cristy 5 15 5 alan 1 8 24	alan 10 cristy 10 betty 9 alisa 8
5 3 2 0 2 1 3 100 4 3 0 4 2 5 10 3 11 100 1 3 0 10 5 11 40 6 41 80 12 betty 1 6 2 cristy 2 67 23 alisa 5 15 5 alan 1 8 24 alisa 2 67 23	alan 10 alisa 10 betty 9 alisa 8 cristy 8

Источник: Командное школьное первенство Республики Карелия по программированию, май 2008.

Обсудить       Отправить решение



Версия для печати