Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Вам дано \(t\) пар массивов \(a_i\) и \(b_i\) равной длины.

За одну операцию модификации можно:

Поменять местами любые два элемента массива \(a_i\), но каждый элемент массива может участвовать не более чем в одном обмене.
Вычесть из любого элемента массива \(a_i\) единицу. Данную операцию можно применять неограниченное число раз к любому элементу массива.

Для каждой пары массивов найдите минимальное число операций, которые необходимо применить к массиву \(a_i\), чтобы получить массив \(b_i\), или определите, что это невозможно.

Входные данные
В первой строке дано число \(t\) — число пар массивов (\(1 \le t \le 40\)).

В следующих \(3t\) строках содержатся описания пар массивов. Каждая пара описывается тремя строками.

В первой из них дано число \(n_i\) — количество элементов в каждом массиве \(i\)-й пары(\(1 \le n_i \le 10\)). Во второй строке заданы \(n_i\) чисел \(a_{i,j}\) — элементы массива \(a_i\) (\(1 \le a_{i,j} \le 1000\)). В третьей строке заданы \(n_i\) чисел \(b_{i,j}\) — элементы массива \(b_i\) (\(1 \le b_{i,j} \le 1000\)).

Гарантируется, что сумма \(n_i\) по всем тестовым наборам не превосходит \(150\).

Выходные данные
Для каждого пары массивов выведите одно число — минимальное число операций, которые необходимо применить к массиву \(a_i\), чтобы получить массив \(b_i\), или \(-1\), если для данной пары это невозможно.

жадные алгоритмы реализация

✓ 2✗ 0—Войти и решать

Сын маминой подруги#39500

Вася уже в десятом классе. После месяца ежедневных заруб в доту со своими товарищами, он начал замечать, что его оценки начали проседать. Исправлять их он, конечно же не собирается, но есть один нюанс...
Вместе с Васей в классе учится сын маминой подруги — Петя. Вася очень не любит его, потому что мама Васи дружит с мамой Пети и знает про него почти всё. В конце триместра у васиной мамы есть традиция садиться и сравнивать оценки Васи с оценками Пети. За каждый случай, когда у Васи оценка ниже, чем у Пети, мама выдаёт ему наряд вне очереди! — мыть весь день посуду, пропылесосить во всём доме, помыть окна или отвести/забрать младшую сестру из детского сада.
Конечно же, эта ситуация Васе не очень нравится, потому что в среднем Вася умнее Пети. Вася хочет минимизировать количество штрафных нарядов, поэтому он собирается перемешать оценки.
Помимо оценок в журнале встречается метка n. Она означает, что ученика на уроке не было. Если кого-то из учеников не было на уроке, то мама Васи не может сравнить успехи своего сына и сына своей подруги, поэтому штрафной наряд выписан быть не может
Помогите Васе перемешать свои оценки и n-ки так, чтобы получить как можно меньше штрафных нарядов. Если существует несколько решений, выведите любое.
В школе N различных предметов, и по каждому из них Вася должен перемешать оценки.
В каждом тесте первое число N — это количество предметов, за которые получены оценки в этом триместре. В следующих 2N строках находятся N блоков по 2 строки. В каждом блоке в первой строке находятся оценки Васи, а во второй — оценки Пети. Для каждого блока в новой строчке нужно вывести такую перестановку номеров оценок и меток n, что a_iозначает, что Васина оценка под номером i должна занять позицию a_i.
В первом тесте 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 и получит один наряд вне очереди

жадные алгоритмы реализация

—Войти и решать