Alice's Number Guessing Game

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 256M

Problem type

Alice is thinking of an integer N, that Bob is trying to guess. Bob has asked questions of two types:

  1. is N \le X for some integer X?
  2. is N \ge X for some integer X?

For each question, Alice responded with either yes or no. Bob remembers the M questions that Alice responded yes to, but can't calculate the range [L, R] that N could be in!

Please help him determine the range based on Alice's responses. It may be possible that a range is impossible based on Alice's responses. If this is the case, output LIES!.


1 \le M \le 10^3

1 \le N, X \le 10^9

Input Specification

The first line will contain M, the number of questions Bob has asked.

The next M lines will contain 2 space-separated integers, denoting a question Bob asked that Alice responded yes to. The first integer is either 1 or 2 corresponding to the question type and the second is X for that question.

Output Specification

If a range is determined to be impossible based on Alice's responses, output LIES!.

Otherwise, output 2 space-separated integers L and R \ (1 \le L \le R \le 10^9), the range that N could be in.

Sample Input 1

2 10
1 17
1 15

Sample Output 1

10 15

Explanation for Sample Output 1

Alice says that N \ge 10, N \le 17, and N \le 15. Based on these constraints, 10 \le N \le 15, so [L, R] = [10, 15].

Sample Input 2

1 14
2 20

Sample Output 2


Alice says that N \le 14 and N \ge 20. We see that a range is impossible and Alice is lying.

Sample Input 3

1 8

Sample Output 3

1 8

Sample Input 4

2 4
2 3
2 5
2 8

Sample Output 4

8 1000000000


There are no comments at the moment.