No.3711 Udon, Tempura
タグ : / 解いたユーザー数 63
作問者 :
UT0911
/ テスター :
sclara
👑 
Rino-program
Problem Statement
Yuti is at an udon restaurant. This restaurant offers $N$ kinds of udon and $M$ kinds of tempura. The price of the $i$-th udon is $U_i$, and the price of the $j$-th tempura is $T_j$.
Yuti is about to place an order.
In the order, he first chooses $1$ kind of udon.
Then, for each of the $M$ kinds of tempura, he decides whether or not to choose it. He may also choose not even $1$ tempura.
Find the number of distinct possible total prices.
Constraints
- All inputs are integers.
- $1 \leq N \leq 100$
- $1 \leq M \leq 100$
- $1 \leq U_i \leq 10^5$
- $1 \leq T_j \leq 1000$
Input
$N$ $M$ $U_1$ $U_2$ $\cdots$ $U_N$ $T_1$ $T_2$ $\cdots$ $T_M$
Output
Output the number of distinct possible total prices.
Print a newline at the end.
Sample
Sample 1
Input
2 2 100 200 20 30
Output
8
The ways to choose udon and tempura, along with the corresponding total prices, are as follows.
$$ \begin{array}{llr} ・\ \text{Udon } 1 &:& 100 \\ ・\ \text{Udon } 1, \text{Tempura } 1 &:& 100 + 20 \quad = \quad 120 \\ ・\ \text{Udon } 1, \text{Tempura } 2 &:& 100 + 30 \quad = \quad 130 \\ ・\ \text{Udon } 1, \text{Tempura } 1, 2 &:& 100 + 20 + 30 \quad = \quad 150 \\ ・\ \text{Udon } 2 &:& 200 \\ ・\ \text{Udon } 2, \text{Tempura } 1 &:& 200 + 20 \quad = \quad 220 \\ ・\ \text{Udon } 2, \text{Tempura } 2 &:& 200 + 30 \quad = \quad 230 \\ ・\ \text{Udon } 2, \text{Tempura } 1, 2 &:& 200 + 20 + 30 \quad = \quad 250 \end{array} $$
There are $8$ distinct prices, so output $8$.
Sample 2
Input
2 2 100 200 50 150
Output
7
$$ \begin{array}{llr} ・\ \text{Udon } 1 &:& 100 \\ ・\ \text{Udon } 1, \text{Tempura } 1 &:& 100 + 50 \quad = \quad 150 \\ ・\ \text{Udon } 1, \text{Tempura } 2 &:& 100 + 150 \quad = \quad 250 \\ ・\ \text{Udon } 1, \text{Tempura } 1, 2 &:& 100 + 50 + 150 \quad = \quad 300 \\ ・\ \text{Udon } 2 &:& 200 \\ ・\ \text{Udon } 2, \text{Tempura } 1 &:& 200 + 50 \quad = \quad 250 \\ ・\ \text{Udon } 2, \text{Tempura } 2 &:& 200 + 150 \quad = \quad 350 \\ ・\ \text{Udon } 2, \text{Tempura } 1, 2 &:& 200 + 50 + 150 \quad = \quad 400 \end{array} $$
There are $2$ ways to reach $250$ yen, but since the answer is the number of distinct prices, the answer is $7$.
Sample 3
Input
5 2 1000 1000 1000 1000 1000 50 50
Output
3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。