Informatica Online Judge

  중딩(S) [1128 / 0468]

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


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

[JKJeong 2014]

Background

초등학교를 졸업한 경곽이는 중학교에 입학했다.

이제 경곽이는 수학실력이 많이 늘었다.

예전과는 달리 이제 자연수로는 700까지 계산할 수 있다. (음수는 고려하지 않는다.)

1부터 9로 구성된 n개의 숫자가 주어질 때,

이 숫자들 사이에 "+", "-", "결합"을 사용하여 k를 만들 수 있는 경우의 수는 어떻게 구할까?

만약 1 과 2가 주어진다면, 각 연산의 결과는 다음과 같다.

1 + 2 ("+"사용)
1 - 2 ("-" 사용)
12 ("결합" 사용)

만약 3개의 숫자 1, 2, 3이 주어지고, k는 9라면 다음과 같이 만들 수 있다.

1 "결합" 2 "-" 3

즉, 12 - 3 = 9 로 만들 수 있다.

이와 같이 n개의 숫자와 k값이 주어질 때, 주어진 조건을 만족하며 k를 만들 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 숫자의 수 n이 입력된다.
두 번째 줄에 원하는 수 k가 입력된다.
세 번째 줄에는 1~9까지의 숫자 n개가 공백으로 구분되어 입력된다.

[입력값의 정의역]
n <= 15 인 자연수임을 만족한다.
k <= 700 인 자연수임을 만족한다.

Output

첫 번째 줄에 가능한 경우의 수를 출력한다.

IO Example

입력
3
9
1 2 3

출력
1

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