COCI '10 Contest 1 #2 Profesor

Points: 5 (partial)

Time limit: 1.0s

Memory limit: 64M

Problem type

In a long classroom, $N$ ~N~ desks are arranged in a single row, with two students sitting at each desk. Students are cranky because they are about to have an art class, and their professor is planning to examine them.

Each student has studied art, but only to a certain level. The old professor can tell by the looks on their faces just how much they have studied. The professor, being an artist, uses a different coloured pencil for each grade. Unfortunately, today he brought only one pencil.

In order to make the examination seem fair, he wants to choose two desks and question one student from each desk positioned between the two desks he has chosen (including the chosen desks). It is important that all examined students deserve the same grades, so he can write them down using his only pencil.

The professor wants to know the maximum number of students he can examine this way, as well as which grade the students will get.

Input Specification

The first line of input contains a single integer $N$ ~N~ $(1 \le N \le 100\,000)$ ~(1 \le N \le 100\,000)~.

Each of the following $N$ ~N~ rows contains two integers: $A_i$ ~A_i~ and $B_i$ ~B_i~, grades deserved by students sitting at desk $i$ ~i~ $(1 \le A_i, B_i \le 5)$ ~(1 \le A_i, B_i \le 5)~.

Test cases worth $70\%$ ~70\%~ of total points have $N \le 100$ ~N \le 100~.

Output Specification

The first and only line of output must contain two numbers separated by a single space: the maximum number of students the professor can examine and the grade those students will get.

If there are multiple solutions possible, output the one with the smallest grade.

Sample Input 1

1
1 5

Sample Output 1

1 1

Sample Input 2

Sample Output 2

2 5

Sample Input 3

Sample Output 3

2 2

Comments

0

mrap commented on Nov. 9, 2024, 7:35 p.m.

I could use some help understanding the question.

My understanding is: select 2 desks and find the smallest grade with the most students.

So for the 1st sample, 1 student with 1. For the 2nd sample 2 students with 3 (but the sample answer is 2 students with 5). For the 3rd sample, 3 students with 2, but we're only selecting 2 desks at a time, so 2 students with 2.

0

mrap commented on Dec. 15, 2024, 1:54 a.m.

A friend provided me the explanation below. Hoping it helps someone else as well.

Two students are sitting at each desk. Each student gets a grade from 1 to 5.

We're looking for the maximum number of consecutive desks, where at each of those desks there's a student with the same grade.

So for these three desks: 3 5 4 5 1 3 There are two desks in a row with a 5 grade (the 3 5 desk and the 4 5 desk), so the answer is 2 5

There are two desks with a 3 grade, but those are not consecutive, so we can't use them.