No.1463 Hungry Kanten
タグ : / 解いたユーザー数 174
作問者 :
Problem Statement
There are now $N$ integers $A_i(1 \leq i \leq N)$ in the refrigerator. Kanten-kun, who has gotten hungry, has decided to eat his favorite food: integers.
Since he cannot eat them as they are, Kanten-kun chooses $K$ or more of the integers, performs exactly one of the following operations once, and eats the resulting integer.
・Heat cooking - Mix all the chosen integers together and heat them. The resulting integer is the sum of the chosen integers.
・Pressure cooking - Put all the chosen integers into a pressure vessel and apply pressure. The resulting integer is the product of the chosen integers.
Given that only these two cooking methods exist, how many different integers can Kanten-kun eat?
Input
$N\ K$ $A_1\ A_2\ \cdots\ A_N$
All test cases satisfy the following constraints.
・$2 \leq N \leq 18$
・$2 \leq K \leq N$
・$1 \leq A_i \leq 10^3(1 \leq i \leq N)$
・All inputs are integers
Output
Output the number of different integers Kanten-kun can eat on one line. Also, print a newline at the end.
Sample
Sample 1
Input
4 2 1 2 3 5
Output
12
By cooking these integers, Kanten-kun can eat the 12 integers $2,3,4,5,6,7,8,9,10,11,15,30$.
Sample 2
Input
2 2 2 2
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。