COCI '07 Contest 4 #5 Poklon

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem types

Mirko got a set of intervals for his birthday. There are many games he can play with them. In one of them, Mirko must find the longest sequence of distinct intervals such that each interval in the sequence is in the set and that each interval contains the one that follows in the sequence.

Write a program which finds one such longest sequence.

Input Specification

The first line of input contains the integer N (1 \le N \le 100000), the number of intervals in the set. Each of the following N lines contains two integers A and B describing one interval (1 \le A < B \le
1000000).

Output Specification

Output the length K of the longest sequence on the first line. Each of the following K lines should contain one element of the sequence, an interval in the same format it was given in the input.

Sample Input 1

3
3 4
2 5
1 6

Sample Output 1

3
1 6
2 5
3 4

Sample Input 2

5
10 30
20 40
30 50
10 60
30 40

Sample Output 2

3
10 60
30 50
30 40

Sample Input 3

6
1 4
1 5
1 6
1 7
2 5
3 5

Sample Output 3

5
1 7
1 6
1 5
2 5
3 5

DMOJ Editor's note

A sequence is an ordered list of elements. For example, \{1,5,3\} is a sequence taken from elements of \{1,2,3,4,5,6\}.


Comments


  • 3
    A_H_Ghaznavi  commented on May 20, 2019, 3:20 p.m.

    I have a problem with this problem!

    I submitted a right code but get WA!

    According to this link the first test case is:

    6
    
    2 10
    
    6 9
    
    1 2
    
    7 8
    
    1 8
    
    8 10

    and the answer is:

    3
    
    2 10
    
    6 9
    
    7 8

    And in this picture you see my answer is right!

    enter image description here

    But get WA!


    • 2
      Kirito  commented on May 20, 2019, 4:04 p.m.

      There was an error with the checker that has since been fixed. All submissions have been rejudged.