0377. Носки

Пришла весна и дед Олег решил пойти на свои грядки и заняться уборкой территории. Как и у многих представителей мужского пола, у него возникла трудность с поиском носок. Более того, почти все его носки оказались дырявыми. Олег перебрал всю свою кипу носок, и выписал размер носка и количество дырок на нём. Теперь он хочет собрать по паре носок каждого размера, который у него есть. При этом конечно же он хочет, чтобы в собранных парах было как можно меньше дырок.

Формат входного файла

В первой строке входного файла содержится положительное целое число N (N ≤ 299999) – число обнаруженных носок. Дед Олег накопил большое количество носок, за время своего существования. В следующих N строках содержится описание каждого носка: его размер s_i и число дырок h_i (1 ≤ s_i ≤ 10⁹, 0 ≤ h_i ≤ 10⁹) – Дед Олег сам недоумевает, откуда у него могли оказаться носки размера 10⁹, и откуда он мог получить такое большое количество дырок.

Формат выходного файла

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

Пример:

В примере Олег получает пару размера 27 с тремя дырками (носки 3 и 4), пару размера 29 с пятью дырками (носки 1 и 2) и пару размера 31 без дырок (носки 8 и 9).

Источник: Открытый весенний чемпионат ПетрГУ по программированию, 20 апреля 2014

Обсудить       Отправить решение



Версия для печати