CCC '17 S3 - Nailed It! - DMOJ: Modern Online Judge

CCC '17 S3 - Nailed It!

Points: 7 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

Canadian Computing Competition: 2017 Stage 1, Junior #5, Senior #3

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$ ~N~ pieces of wood. The $i^{th}$ ~i^{th}~ piece of wood has integer length $L_i$ ~L_i~.

A board is made up of exactly two pieces of wood. The length of a board made of wood with lengths $L_i$ ~L_i~ and $L_j$ ~L_j~ is $L_i + L_j$ ~L_i + L_j~. A 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:

$\text{[math]}$

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 Specification

The first line will contain the integer $N$ ~N~ $(2 \le N \le 1\,000\,000)$ ~(2 \le N \le 1\,000\,000)~.
The second line will contain $N$ ~N~ space-separated integers $L_1, L_2, \dots, L_N$ ~L_1, L_2, \dots, L_N~ $(1 \le L_i \le 2\,000)$ ~(1 \le L_i \le 2\,000)~.

For 5 of the 15 available marks, $N \le 100$ ~N \le 100~.
For an additional 4 of the 15 available marks, $N \le 1\,000$ ~N \le 1\,000~.
For an additional 3 of the 15 available marks, $N \le 100\,000$ ~N \le 100\,000~.

Output Specification

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 for Sample Output 1

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

Sample Input 2

5
1 10 100 1000 2000

Sample Output 2

1 10

Explanation for Sample Output 2

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

Comments

0

AmIJohnLi commented on Dec. 11, 2024, 6:06 a.m.

What is the correct time complexity supposed to be?

-3

wwwddddz commented on Jan. 23, 2024, 4:20 p.m.

what a tricky question

-6

volcano commented on Sept. 2, 2022, 5:51 p.m.

Does anyone know why my code doesn't work? https://dmoj.ca/src/4811358

This comment is hidden due to too much negative feedback. Show it anyway.

9

Badmode commented on May 23, 2021, 5:29 p.m. ← edited →

Are all lengths of the pieces of wood distinct?

Edit: Thanks.

6

Nils_Emmenegger commented on May 23, 2021, 9:39 p.m.

No.

1

ayazshukla commented on Jan. 14, 2021, 6:03 a.m.

I'm tryna check which test case my code fails on but I don't know which one it is cuz test data isn't properly numbered. Is there a way I can find out what subtask 1 test 2 is in the input files ?

1

vichua2006 commented on May 17, 2021, 12:43 p.m.

I suppose you can go to the offical CEMC website and find all the test data there. Then just manually check through the however many test case there are.

0

volcano commented on Sept. 2, 2022, 5:26 p.m.

But you should try to solve it yourself first because in the actual CCC you don't have the test data available.

-7

pro commented on Jan. 14, 2018, 1:54 a.m.

15 available marks?

This comment is hidden due to too much negative feedback. Show it anyway.

13

Xyene commented on Jan. 14, 2018, 8:42 p.m.

Problem testcases are weighted out of 15.