Олимпиадный тренинг

Задача . Сын маминой подруги


Задача

Темы: жадные алгоритмы реализация
Вася уже в десятом классе. После месяца ежедневных заруб в доту со своими товарищами, он начал замечать, что его оценки начали проседать. Исправлять их он, конечно же не собирается, но есть один нюанс...
Вместе с Васей в классе учится сын маминой подруги — Петя. Вася очень не любит его, потому что мама Васи дружит с мамой Пети и знает про него почти всё. В конце триместра у васиной мамы есть традиция садиться и сравнивать оценки Васи с оценками Пети. За каждый случай, когда у Васи оценка ниже, чем у Пети, мама выдаёт ему наряд вне очереди! — мыть весь день посуду, пропылесосить во всём доме, помыть окна или отвести/забрать младшую сестру из детского сада.
Конечно же, эта ситуация Васе не очень нравится, потому что в среднем Вася умнее Пети. Вася хочет минимизировать количество штрафных нарядов, поэтому он собирается перемешать оценки.
Помимо оценок в журнале встречается метка n. Она означает, что ученика на уроке не было. Если кого-то из учеников не было на уроке, то мама Васи не может сравнить успехи своего сына и сына своей подруги, поэтому штрафной наряд выписан быть не может
Помогите Васе перемешать свои оценки и n-ки так, чтобы получить как можно меньше штрафных нарядов. Если существует несколько решений, выведите любое.
В школе N различных предметов, и по каждому из них Вася должен перемешать оценки.
В каждом тесте первое число N — это количество предметов, за которые получены оценки в этом триместре. В следующих 2N строках находятся N блоков по 2 строки. В каждом блоке в первой строке находятся оценки Васи, а во второй — оценки Пети. Для каждого блока в новой строчке нужно вывести такую перестановку номеров оценок и меток n, что ai означает, что Васина оценка под номером i должна занять позицию ai.
В первом тесте N = 30. Оценка за этот тест: 30 баллов. За каждый предмет, за который получено больше штрафных нарядов, чем могло бы быть, снимается 1 балл. Проверка осуществляется в режиме online (результат виден сразу).
Во втором тесте N = 35. Оценка за этот тест: 70 баллов. За каждый предмет, за который получено больше штрафных нарядов, чем могло бы быть, снимается 2 балла. Во время тура проверяется, что по каждому предмету сдана корректная перестановка. Проверка правильности ответа осуществляется в режиме offline (результат виден после окончания тура).
Примеры
№ Входные данные Выходные данные
1 3
5
4 4 3 4 4
5 5 4 5 5
4
n 3 4 n
4 n 4 n
4
1 3 2 4
3 2 1 5		 5 1 2 4 3
1 2 3 4
3 4 2 1

В первом примере Вася получит 4 наряда вне очереди. Во втором примере ничего никуда переставлять не надо, потому что на единственном уроке, на котором присутствовали оба ученика, они получили по 4 балла. В третьем примере Вася переставит оценки вот так: 4, 2, 1, 3 и получит один наряд вне очереди

 
Статистика успешных решений по компиляторам

Ваш ответ

выберите язык и введите исходный код


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

Загруженные файлы
Нет