S3. Nailed It!
레이팅 미적용의견: 0
Time limit: 2 seconds
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 up of exactly
two pieces of wood. The length of a board made of wood with
lengths \(L_i\) and \(L_j\) is \(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:
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.
\((2 \le N \le 1\ 000\ 000)\)
\((1 \le L_i \le 2\,000)\)
\(N \le 100\)
\(N \le 1000\)
\(N \le 100\ 000\)
The first line will contain the integer \(N\) \((2 \le N \le 1\ 000\ 000)\).
The second line will contain \(N\)
space-separated integers \(L_1, L_2, \ldots, L_N\) \((1 \le L_i \le 2\,000)\).
For 5 of the 15 available marks, \(N \le 100\).
For an additional 4 of the 15 available marks, \(N \le 1000\).
For an additional 3 of the 15 available marks, \(N \le 100\ 000\).
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.
4
1 2 3 42 1Tudor 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\).
5
1 10 100 1000 20001 10Tudor 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.
평가 및 의견
S3. Nailed It!
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
S3. Nailed It!