Informatica Online Judge

  연결시켜 붙이기 [1962 / 07AA]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 20   Total Tried : 20


The Champion of this Problem (C++) : gs16106 - 0ms / 1150byte
My Best Submission (C++) : N/A

[CCC 2017]

Background

경곽이는 ACM-ICPC 참가자이다. 대회에서 우승하기 위해 경곽이는 주어진 판자들을 이용해 만들 수 있는 담장의 최대 길이를 알아내야 한다.

$n$개의 판자 조각이 주어졌을 때, 담장을 만들 수 있는 단위 길이는 정확히 $2$개의 판을 이어 붙여 만들고, 그렇게 만든 것들을 연결해 붙인 담장의 높이는 모두 같아야한다.

담장의 길이는 담장을 만들기 위해 사용된 단위 길이의 개수를 의미하고, 담장의 높이는 단위 길이의 높이이다.

예를 들어, 아래 그림은 길이가 $4$, 높이가 $50$인 담장의 예이다.



$n$개의 판자 조각이 주어졌을 때 만들 수 있는 가장 긴 담장 길이와, 그러한 길이가 가능한 높이의 가짓수를 구해보자.

Input

첫 줄에는 사용할 수 있는 판자의 개수($n$)가 입력된다.
두 번째 줄에는 각 판자의 크기(높이, $L_i$)가 공백을 두고 입력된다.


[입력값의 정의역]

$2≤n≤1,000,000$
$1≤L_{i}≤2,000$

Output

가능한 최대 길이와 그 길이로 만들 수 있는 높이의 가짓수를 공백을 두고 출력한다.

IO Example

입력1
4
1 2 3 4

출력1
2 1

설명 (1+4), (2+3) 으로 길이 2짜리 담장을 만들 수 있고, 높이는 5가 유일하다.

입력2
5
1 10 100 1000 2000

출력2
1 10

5개 중 2개만 골라 길이 1짜리 담장을 만들 수 있고,
높이는 11, 101, 1001, 2001, 110, 1010, 2010, 1100, 2100, 3000이 가능하다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]