Охранник
Компания Bluewater Security предоставляет охранников для клиентов, у которых есть ценные вещи. Bluewater выяснила, что клиенты хотят, чтобы охранники находились в местах, откуда они могут видеть все ценные предметы, просто повернув голову, и предпочитают, чтобы охранники были особенно близки к особенно ценным предметам. Пример расположения сайта показан выше. Пока игнорируйте три черные точки. Различные места обозначены и имеют свои значения. Например, местоположение A с координатами (0,8) — это позиция предмета со значением 4. Места, показывающие значение 0, как G, не содержат ценных предметов. Прямые линии обозначают коридоры. Для простоты коридоры моделируются как отрезки с нулевой шириной. Охранник, находящийся на точке пересечения нескольких коридоров, может видеть и, следовательно, охранять предметы на каждом из коридоров. Если Bluewater заключила контракт на предоставление 3 охранников, они могут выбрать разместить их в позициях, указанных маленькими черными точками. Охранник, не находящийся в уже обозначенной позиции, находится в (15.5, 6). Чтобы учесть желание, чтобы охранники были ближе к предметам с более высокой ценностью, Bluewater рассчитывает риск для ценного предмета как значение предмета, умноженное на минимальное расстояние до охранника, который может видеть предмет. Даже если охранник близко к предмету, который находится за углом, этот охранник не влияет на риск для предмета, так как он не может видеть за угол. На показанной диаграмме риски для предметов следующие: A: 4x5=20, C: 4x2.5=10, D: 2x0=0, .... Наибольшие риски для H: 50x7.5=375 и I: 50x7.5=375, так что максимальный риск для любого одного предмета составляет 375. С этим расположением сайта никакое размещение 3 охранников не обеспечит меньший максимальный риск, так что это размещение 3 охранников минимизирует максимальный риск. Bluewater хотела бы иметь возможность сообщить любому клиенту, который запрашивает определенное количество охранников для определенного расположения сайта, каким будет минимизированный максимальный риск.
Входные данные
Входные данные состоят из одного до шестнадцати наборов данных, за которыми следует строка, содержащая только 0. В каждой строке данные состоят из разделенных пробелами токенов.
Первая строка набора данных содержит целые числа p c g, где p — количество заданных точек, c — количество коридоров, и g — количество охранников, которых нужно разместить. Ограничения: 1 < p < 12; 0 < c < 12; 0 < g < 5.
Далее в наборе данных идут p группы из четырех токенов, каждая из которых состоит из заглавной буквы и трех неотрицательных целых чисел L x y v, указывающих на точку (x, y) с меткой L, содержащую предмет со значением v. Если p не больше 6, эти группы будут все в одной строке. Если p больше 6, то седьмая и последующие группы будут в следующей строке. Метки будут последовательными буквами, начиная с A. Все числа меньше 1000. Каждая из точек уникальна. Значение 0 для v означает, что там нет ценного предмета. Количество мест с ценными предметами будет как минимум таким же, как количество охранников.
Последняя строка набора данных содержит c строк букв, по одной для каждого коридора. Для каждого коридора буквы являются метками для точек вдоль коридора, в порядке вдоль отрезка от одного конца до другого, включая обе конечные точки, все точки пересечения с другими коридорами и все местоположения на коридоре с ценным предметом. Каждая из точек, данных в наборе данных, будет лежать как минимум на одном из коридоров.
Выходные данные
Для каждого набора данных выводится одна строка. Если предоставлено недостаточно охранников, чтобы видеть все ценные предметы, строка будет "too few guards". В противном случае строка будет содержать неотрицательное число r, округленное до двух знаков после запятой, где r — это минимальное значение среди всех размещений g охранников максимального "риска" для ценных предметов.