11/04/2025 01:20:16

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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-го участника из второй.