images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
20/04/2024 10:47:45

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2217. Сайт знакомств

Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Тиму необходима программа, которая выбирает пары для проведения виртуальных свиданий на сайте знакомств iDate. Виртуальное свидание будет наиболее продуктивным, если пара живет в одном и том же или близких часовых поясах. Программа должна создать как можно больше пар для свиданий среди `N` мужчин и `M` женщин, зарегистрированных на сайте, при этом сумма значений выражений `min(|T_i\ –\ T_j|\ mod\ 24,\ 24\ -\ (|T_i\ -\ T_j|\ mod\ 24))` по всем выбранным парам должна быть как можно меньше. Здесь `T_i` – часовой пояс мужчины, а `T_j` – часовой пояс женщины, если программа для свидания выбрала пару из `i`-го мужчины и `j`-й женщины. Каждый человек может быть назначен программой не более чем в одну пару.
Формат ввода
Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 1000`) – количество мужчин и женщин. Вторая строка содержит часовые пояса `N` мужчин, а третья – часовые пояса `M` женщин. Часовой пояс задается как разница со всемирным координированным временем (UTC) и может принимать значение от `-11` до `+14`, после целого количества часов опционально может быть указано время в минутах 30 или 45.
Формат вывода
Вывести `min(N,M)` строк. В каждой строке вывести номера мужчины и женщины в выбранной для виртуального свидания паре. Если существует несколько вариантов с минимальной суммой, то можно вывести любой из них.

Пример ввода

3 4
-7 -11 +5
-9 -8 +5:30 +13

Пример вывода

2 4
1 2
3 3
loading