Woburn Challenge 2018-19 Finals Round - Junior Division

Problem 1: Conditional Contracts

The cows and monkeys of Scarberia, their long-standing conflicts well behind them at last, have banded together to produce a historical drama documenting their past battles. With the Head Monkey as writer and producer, and the director's chair occupied by the cows' leader, Bo Vine, this will be a collaborative masterpiece to remember!

As part of his preparations, Bo Vine is considering what width of film to use, an important artistic decision. He doesn't want to limit himself to a single width, so he's decided that two copies of the movie will be shot, on two different film widths! Each film width (measured in mm) must be an integer between 1 and 1,000,000,000, inclusive, and the two widths must be distinct.

There are N (1 ≤ N ≤ 100) acclaimed actors interested in the film, and the Head Monkey and Bo Vine would like to cast as many of them as possible. However, they only work under very specific conditions — the i-th actor insists that they must be captured on film with a width of exactly Wi mm (1 ≤ Wi ≤ 1,000,000,000). Each actor can be employed if their requirement is satisfied for at least one of the two copies of the movie.

If Bo Vine chooses a pair of distinct film widths optimally, what's the maximum number of different actors who can be employed?

Subtasks

In test cases worth 5/10 of the points, Wi ≤ 100 for each i.

Input Format

The first line of input consists of a single integer, N.
N lines follow, the i-th of which consists of a single integer, Wi, for i = 1..N.

Output Format

Output a single integer, the maximum number of actors who can be employed.

Sample Input

4
50
70
51
70

Sample Output

3

Sample Explanation

One possibility is using 50mm film for the first copy of the movie and 70mm film for the second copy. This allows the first, second, and fourth actors to be employed. It's impossible for all 4 actors to be employed at once.

All Submissions
Best Solutions


Point Value: 5 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 18, 2019
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...