Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Интернет-олимпиады

(Время: 1 сек. Память: 16 Мб Сложность: 28%)

Многим известно о проекте «Интернет-олимпиады по информатике», расположенном в сети Интернет по адресу http://neerc.ifmo.ru/school/io/, где проводятся онлайн-олимпиады для школьников в двух номинациях: базовой и усложненной. Ваша задача состоит в том, чтобы написать программу, обрабатывающую результаты Интернет-олимпиады, то есть определяющую: какие команды в какой номинации будут участвовать в следующей олимпиаде.

Правила перехода команд из одной номинации в другую таковы. Задачи усложненной номинации решают следующие команды:

  • участвовавшие в предыдущей олимпиаде в усложненной номинации и решившие хотя бы одну задачу;
  • участвовавшие в предыдущей олимпиаде в базовой номинации, решившие хотя бы одну задачу, и при этом решившие либо столько же задач, сколько команда-победитель, либо строго больше задач, чем команда, занявшая медианное место среди команд, решивших хотя бы одну задачу (место с номером k/2, где k - число команд, участвовавших в базовой номинации, решивших хотя бы одну задачу, округление производится вниз).

Все остальные команды участвуют в следующей олимпиаде в базовой номинации. В этой задаче мы считаем, что никакие новые команды не региструются для участия в следующей олимпиаде.

Напомним также, что при подведении итогов одной олимпиады команды сортируются по убывании количества решенных задач, а при равенстве количества решенных задач - по возрастанию штрафного времени.

Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа: n и m - соответственно, количество команд, участвовавших в базовой и усложненной номинациях (1 ≤ n, m ≤ 1000).

После этого идут n строк, описывающих результаты команд, участвовавших в базовой номинации. Каждая из этих строк содержит три целых числа, разделенных пробелами, - id, s, t - соответственно, уникальный идентификатор команды, количество решенных задач и штрафное время. Количество решенных задач - целое число от 0 до 12, а штрафное время - целое число от 0 до 20000. Идентификатор команды - это целое число от 1 до 2000.

После этого идут m строк, описывающих результаты усложненной номинации в таком же формате.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите число k команд, которые допускаются до участия в усложненной номинации в следующей олимпиаде. Вторая строка должна содержать k целых чисел - идентификаторы этих команд в возрастающем порядке.

Пример

INPUT.TXTOUTPUT.TXT
16 3
1 1 45
2 4 678
3 5 1000
4 5 894
5 2 343
6 3 555
1998 0 0
1999 1 34
2000 3 366
4
3 4 1999 2000

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483