### 2017 Canadian Computing Competition

## Problem J5S3: Nailed It!

Tudor is a contestant in the Canadian Carpentry Challenge (CCC). To win the CCC, Tudor must demonstrate his skill at nailing wood together to make the longest fence possible using boards. To accomplish this goal, he has `N` pieces of wood. The `i`^{th} piece of wood has integer length `L _{i}`.

A *board* is made of **exactly two** pieces of wood. The length of a board made with lengths `L _{i}` and

`L`is

_{j}`L`+

_{i}`L`. A

_{j}*fence*consists of boards that are the same length. The

*length of the fence*is the number of boards used to make it, and the

*height of the fence*is the length of each board in the fence. In the example fence below, the length of the fence is 4; the height of the fence is 50; and, the length of each piece of wood is shown:

Tudor would like to make the longest fence possible. Please help him determine the maximum length of any fence he could make, and the number of different heights a fence of that maximum length could have.

### Input Format

The first line will contain the integer `N` (2 ≤ `N` ≤ 1 000 000).

The second line will contain `N` space-separated integers `L`_{1}, `L`_{2}, …, `L _{N}` (1 ≤

`L`≤ 2000).

_{i}For 5 of the 15 available marks, `N` ≤ 100.

For an additional 4 of the 15 available marks, `N` ≤ 1000.

For an additional 3 of the 15 available marks, `N` ≤ 100 000.

### Output Format

Output two integers on a single line separated by a single space: the length of the longest fence and the number of different heights a longest fence could have.

### Sample Input 1

4 1 2 3 4

### Sample Output 1

2 1

### Explanation 1

Tudor first combines the pieces of wood with lengths 1 and 4 to form a board of length 5. Then he combines the pieces of wood with lengths 2 and 3 to form another board of length 5. Finally, he combines the boards to make a fence with length 2 and height 5.

### Sample Input 2

5 1 10 100 10000 2000

### Sample Output 2

1 10

### Explanation 2

Tudor canâ€™t make a fence longer than length 1, and there are 10 ways to make a fence with length 1 by choosing any two pieces of wood to nail together. Specifically, he may have a fence of height 11, 101, 1001, 2001, 110, 1010, 2010, 1100, 2100 and 3000.

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Aug 08, 2017

**Languages Allowed:**

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

## Comments (Search)

skyfeatheron Sep 01, 2017 - 7:08:20 pm UTC Sample Input 2