Informatica Online Judge

  KOIn [1930 / 078A]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (34th 송현진)]
Writer ID : [gs16051]

Background

JK는 KOI국이라는 새로운 나라를 세웠다. 새로운 나라를 세운 JK는 자신의 이름을 admin으로 바꾸고 대통령이 되었다.
admin은 새로운 동전인 KOIn을 발행하려 한다(지폐는 사용하지 않는다).
그는 어떤 금액이든 가장 가치가 큰 동전부터 지불하면 가장 적은 수의 동전으로 지불할 수 있게 하려 한다.

그러던 어느 날, admin은 동전 발행 책임자로 당신을 지명하였다.
당신은 admin을 도와 동전의 가치가 잘 설정되었는지 확인하는 작업을 해야 한다.
동전의 가치를 입력받아 이렇게 가치를 설정하면 admin이 원하는 방법이 되는지 확인해야 한다.
(금액의 단위는 1KOIn이며 가치가 1KOIn인 동전은 반드시 존재한다. 두 종류의 동전의 가치가 같은 경우는 없다.)

Input

첫 줄에는 판정해야 하는 조합의 개수 $t$가 주어진다.(단, $1\leq t\leq 5$)
첫 줄에는 동전의 개수 $n$이 주어진다(단, $1\leq n\leq100$).
다음 줄에는 동전의 가치 $v_i$가 오름차순으로 공백으로 구분되어 주어진다($1\leq i\leq n$, $1\leq v_i\leq100000$, $v_i$는 자연수).
전체 테스트 케이스의 60%는 $1\leq n\leq10$, $1\leq v_i\leq1000$을 만족한다.

Output

$t$개의 조합에 대하여 각각 한 줄씩 다음과 같은 내용을 출력한다:
입력처럼 가치를 설정하여 동전을 발행하였을 때 admin이 원하는 방법처럼 된다면 1을 출력한다.
만약 그렇지 않다면 0과 가장 가치가 큰 동전부터 지불할 때 가장 적은 수의 동전으로 지불할 수 없는 가장 작은 금액을 출력한다.

IO Example

Example Input 1
1
4
1 2 10 50

Example Output 2
1

<설명>
어떠한 금액이더라도 50KOIn->10KOIn->2KOIn->1KOIn 순서로 지불하면 최적이 된다.
Example Input 1
2
3
1 4 5
3
1 2 3

Example Output 2
0 8
1

<설명>
첫 번째 경우, 8KOIn은 4KOIn짜리 동전 2개로 지불하는 것이 최적으로, 가치가 큰 동전부터 사용하면 5KOIn짜리 1개와 1KOIn짜리 3개로 지불해야 하므로 최적이 아니다.
1KOIn부터 7KOIn까지는 가치가 큰 동전부터 사용하는 것이 최적이다.
두 번째 경우, 어떠한 금액이더라도 3KOIn->2KOIn->1KOIn 순서로 지불하면 최적이 됨을 보일 수 있다.

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