Informatica Online Judge

  무단 외출 [0498 / 01F2]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 74   Total Tried : 98


The Champion of this Problem (C++) : ajou709 - ms / 445byte
My Best Submission (C++) : N/A

[USACO 2011 BRONZE]

Background

무단외출이 많기로 소문난 경곽에서는 학생들이 무단외출을 하지 못하게 하기 위하여 학교 주변을 호수로 둘러싸고 도개교를 만들어서 통행하고 있다.

야간에는 도개교 들어서 학생들이 외출을 하기 못하게 한다.

머리가 좋은 경곽의 학생들은 무단외출 계획을 세우고 있다.

새벽이 오기 전에 호수에 땟목을 띄워서 탈출하려고 한다.

그런데 이 땟목에는 약간의 문제점이 있어서 어떤 반의 모든 학생들이 무단 외출을 할 수 없다는 사실을 알게되었다.

이 반에는 $n$ 명의 학생들이 있다.

이 학생들의 무게는 각각 $w_1, w_2, ... , w_n$이다.

이 학생들의 무게의 합을 계산하는 도중에 자리올림이 발생될 경우, 땟목은 견디지 못하고 침몰한다.

만약 땟목에 $2$명의 학생들이 타려고 한다.

한 학생의 무게가 $18$, 다른 학생의 무게가 $11$이라면 두 학생의 합은 $29$가 되며 이 계산시에 자리올림이 발생되지 않으므로 안전하게 땟목을 타고 무단외출을 할 수 있다.

반면에 한 학생의 무게가 $18$ 다른 학생의 무게가 $3$이라면 합은 $21$밖에 되지 않지만 $8$과 $3$을 더하는 순간 $11$이 되어 자리올림이 발생된다.

이 때는 땟목이 침몰하여 외출을 할 수 없게된다.

학생들의 무게가 주어질 때, 안전하게 무단외출할 수 있는 학생들의 수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 학생의 수를 나타내는 자연수 $n$이 주어진다.

다음 줄부터 $n$줄에 걸쳐서 각 학생들의 무게 $w_i$가 한 줄에 하나씩 주어진다.

[입력값의 정의역]

$1 ≤ n ≤ 20$
$1 ≤ w_i ≤ 100,000,000$

Output

탈출할 수 있는 학생의 최댓값을 출력한다.

IO Example

입력
5
522
6
84
7311
19

출력
3

*설명 : 세 명의 학생 $522, 6, 7311$의 무게를 더하는 과정에서 자리올림이 발생하지 않는다. 이 보다 더 많은 학생들이 탈출할 수 있는 경우는 없다.

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