/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
AtCoder さんはバレンタインデーの日に N 人の友達にチョコレートを配ることにしました。i 人目 (1 \leq i \leq N) の友達には、大きさ 2^{A_i} \times 2^{A_i} の正方形の板チョコを渡したいです。
ここで、AtCoder さんは大きさ H \times W の長方形の板チョコを 1 枚仕入れました。この板チョコは切れ目によって縦 H 行・横 W 列のマス目状に区切られており、その各マスは大きさ 1 \times 1 の正方形になっています。
板チョコを切れ目に沿っていくつかのピースに分割することにより、友達に渡す板チョコをすべて得ることが可能か判定してください。なお、余るピースがあっても構いません。
制約
- 1 \leq H \leq 10^9
- 1 \leq W \leq 10^9
- 1 \leq N \leq 1000
- 0 \leq A_i \leq 25 \ (1 \leq i \leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
H W N A_1 A_2 \cdots A_N
出力
可能ならば Yes、不可能ならば No と出力してください。
入力例 1
4 4 4 1 0 0 1
出力例 1
Yes
以下の図のように大きさ 4 \times 4 の板チョコを分割することで、大きさ 2 \times 2, 1 \times 1, 1 \times 1, 2 \times 2 のピースを得ることができます。
入力例 2
5 7 6 0 1 0 2 0 1
出力例 2
Yes
以下の図のように大きさ 5 \times 7 の板チョコを分割することで、大きさ 1 \times 1, 2 \times 2, 1 \times 1, 4 \times 4, 1 \times 1, 2 \times 2 のピースを得ることができます。
入力例 3
3 2 7 0 0 0 0 0 0 0
出力例 3
No
大きさ 3 \times 2 の板チョコから、大きさ 1 \times 1 のピースを 7 つ得ることは不可能です。
入力例 4
11 11 2 2 3
出力例 4
No
大きさ 11 \times 11 の板チョコから、大きさ 4 \times 4, 8 \times 8 のピースを両方得ることは不可能です。
入力例 5
777 777 6 8 6 9 1 2 0
出力例 5
Yes
Score: 500 points
Problem Statement
Ms. AtCoder has decided to distribute chocolates to N friends on Valentine's Day. For the i-th friend (1 \leq i \leq N), she wants to give a square chocolate bar of size 2^{A_i} \times 2^{A_i}.
She has procured a rectangular chocolate bar of size H \times W. It is partitioned by lines into a grid of H rows and W columns, each cell being a 1 \times 1 square.
Determine whether it is possible to divide the chocolate bar along the lines into several pieces to obtain all the chocolate bars for her friends. It is fine to have leftover pieces.
Constraints
- 1 \leq H \leq 10^9
- 1 \leq W \leq 10^9
- 1 \leq N \leq 1000
- 0 \leq A_i \leq 25 \ (1 \leq i \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H W N A_1 A_2 \cdots A_N
Output
If the objective is achievable, print Yes; otherwise, print No.
Sample Input 1
4 4 4 1 0 0 1
Sample Output 1
Yes
By dividing a 4 \times 4 chocolate bar as shown in the figure below, you can obtain pieces of size 2 \times 2, 1 \times 1, 1 \times 1, 2 \times 2.
Sample Input 2
5 7 6 0 1 0 2 0 1
Sample Output 2
Yes
By dividing a 5 \times 7 chocolate bar as shown in the figure below, you can obtain pieces of size 1 \times 1, 2 \times 2, 1 \times 1, 4 \times 4, 1 \times 1, 2 \times 2.
Sample Input 3
3 2 7 0 0 0 0 0 0 0
Sample Output 3
No
It is impossible to obtain seven pieces of size 1 \times 1 from a 3 \times 2 chocolate bar.
Sample Input 4
11 11 2 2 3
Sample Output 4
No
It is impossible to obtain both a 4 \times 4 and an 8 \times 8 piece from an 11 \times 11 chocolate bar.
Sample Input 5
777 777 6 8 6 9 1 2 0
Sample Output 5
Yes