문제
구름이와 바람이는 세계 각지에 숨겨진 보물들을 찾아 몇년째 여행 중이다. 기나긴 여정을 시작한 지 어느덧 1년이 되어 구름이와 바람이는 현재까지 찾은 보물들을 서로 나누어 가지려고 한다.
두 사람은 아직 보물들을 현금화하지 않았기 때문에, 보물은 훼손하지 않은채로 최대한 공평하게 나누어 가지려고 한다. 구름이와 바람이는 1년 동안 서로 다른 총 개의 보물을 수집했으며, 각 보물은 고유한 가격을 가지고 있다. 단, 가격이 같은 서로 다른 두 개 이상의 보물이 존재할 수 있다.
하나의 보물은 두 개 이상으로 쪼개어 가질 수 없다. 구름이와 바람이가 보물들을 나누어 가질 때, 두 사람이 보유한 보물들의 총 가격의 차가 최소가 되는 방법과 그러한 방법은 몇 가지가 있는지 계산하는 프로그램을 작성해주자. 단, 구름이와 바람이가 완전히 똑같은 값어치로 보물들을 둘로 나눌 수 없다면, 구름이가 조금 더 가지는 것으로 한다.
예제 설명
첫 번째 예제에서는 다섯 개의 보물을 수집했으며, 각 보물의 가격은 [2, 1, 8, 4, 16]이다.
구름이가 [16], 바람이가 [2, 1, 8, 4] 가격의 보물을 나눠 가진다면 두 사람이 가지는 보물의 총 가격차는 1이 된다.
그리고 가격차가 1이 되도록 보물을 나누는 방법은 위 경우가 유일하다. 따라서 경우의 수로도 1을 출력한다.
입력
첫째 줄에 수집한 보물의 개수를 의미하는 이 주어진다.
다음 개의 줄에는 보물의 가격을 의미하는 정수가 한 줄에 하나씩 주어진다.
- 보물의 가격은
이상
이하의 정수이다.
출력
첫째 줄에는 두 사람이 얻을 수 있는 돈의 최소 차이를 출력한다.
둘째 줄에는 위 최소 차이를 얻을 수 있게 보물들을 분배하는 경우의 수를 출력한다. 단, 경우의 수가 너무 커질 수 있으므로 이를 으로 나눈 나머지를 출력한다.