ВШ 2019. Структуры данных, жадность

Problem J. Joke with Turtles ≡

problems
visible spaces
basic formulae
wide text
editor

Author:	Andrew Lopatin (original idea), Roman Elizarov (text)	Time limit:	2 sec
Input file:	joke.in	Memory limit:	64 Mb
Output file:	joke.out

Statement

There is a famous joke-riddle for children:

Three turtles are crawling along a road. One turtle says: "There are two turtles ahead of me." The other turtle says: "There are two turtles behind me." The third turtle says: "There are two turtles ahead of me and two turtles behind me." How could this have happened?

The answer is — the third turtle is lying!

Now in this problem you have n turtles crawling along a road. Some of them are crawling in a group, so that they do not see members of their group neither ahead nor behind them. Each turtle makes a statement of the form: "There are a_i turtles crawling ahead of me and b_i turtles crawling behind me." Your task is to find the minimal number of turtles that must be lying.

Let us formalize this task. Turtle i has x_i coordinate. Some turtles may have the same coordinate. Turtle i tells the truth if and only if a_i is the number of turtles such that x_j > x_i and b_i is the number of turtles such that x_j < x_i. Otherwise, turtle i is lying.

Input file format

The first line of the input file contains integer number n. It is followed by n lines containing numbers a_i and b_i that describe statements of each turtle for i from 1 to n.

Output file format

On the first line of the output file write an integer number m — the minimal number of turtles that must be lying, followed by m integers — turtles that are lying. Turtles can be printed in any order. If there are different sets of m lying turtles, then print any of them.

Constraints

1 ≤ n ≤ 1000; 0 ≤ a_i, b_i ≤ 1000.

Sample tests

No.	Input file (`joke.in`)	Output file (`joke.out`)
1	`3 2 0 0 2 2 2`	`1 3`
2	`5 0 2 0 3 2 1 1 2 4 0`	`2 1 4`