Обработка математики: 100%

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

printЗадачи

2312. Перетягивание каната

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

Работа с парусами требует большой слаженности и физической силы, поэтому для тренировки экипаж корабля разбивается на две команды из N человек и проводят соревнование по перетягиванию каната. По правилам соревнований разница в суммарном весе команд не должна превышать D. Поэтому капитан перед началом соревнований берет по одному участнику из каждой команды и меняет их местами, пока разница в суммарном весе команд не станет меньше или равна D.
Напишите программу, которая определит, минимальное количество обменов для достижения цели и порядок таких обменов.
Первая строка ввода содержит два целых числа – количество участников в командах N (2  N  20) и предельную разницу в весе D (1  D  10000). Далее следует две строки, содержащих по N чисел от 1 до 10000 – веса участников в первой и во второй команде.
Первая строка вывода должна содержать одно целое число – минимальное количество обменов K. Далее должно быть K строк, содержащих по два целых числа от 1 до N – номер участника из первой команды и номер участника из второй команды, которых нужно поменять. Если существует несколько вариантов с минимальным количеством обменов, то вывести вариант, при котором итоговая суммарная разница будет как можно меньше. Если существует несколько вариантов с минимальной итоговой разницей, то можно вывести любой из них. Если добиться желаемой разницы невозможно, то вывести в первой строке -1.

Пример ввода

3 100
160 155 100
95 100 105

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

1
1 3
Пояснение к примеру: также можно поменять 2-го участника из первой команды на 1-го или 2-го участника из второй.
loading