0377. Носки

Input file name: socks.in
Output file name: socks.out
Time limit: 2 s
Memory limit: 256 megabytes

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

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

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

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

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

Пример:

socks.insocks.out
10 29 2 29 3 27 1 27 2 29 4 29 3 31 2 31 0 31 0 27 3 3 3 4 1 2 8 9

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


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

Discuss       Submit a solution



Printable version