shunfurh 于 2017.09.09 23:43 提问

Cutting Banknotes

Philip is often faced with a big problem: after going out for dinner or having a few beers, he owes money to his friends or the other way around. These are often small amounts, but because Philip hates coins, his wallet contains only banknotes. Therefore he usually can't pay the amount exactly. Since he hates coins, he also doesn��t allow his friends to return them as change. He does allow for banknotes as change though.

To accomodate for this problem, he and his friends came up with the following idea: let's pay with pieces of banknotes. To make the cutting easy, they only cut banknotes in two equally-sized pieces, cut those pieces in two pieces, and so on. This yields a much larger range of amounts that can be paid. Philip wonders which ones exactly.

Input

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with a number x (0.01 <= x <= 10 000.00): the amount Philip has to pay.

This is formatted with two decimal digits and a period as decimal separator.

One line with a positive integer n (1 <= n <= 1 000): the number of different banknotes.

n lines, each with an integer bi (1 <= bi <= 10 000): the values of the banknotes.

Output

For each test case:

One line with "yes" if the amount can be paid exactly and "no" otherwise.

Sample Input

4
10.75
3
2
10
20
0.33
1
1
10000.00
1
2500
1.00
2
3
5

Sample Output

yes
no
yes
yes

1个回答

devmiao      2017.09.27 21:51

Codeforces 963C. Cutting Rectangle

FZU2268 Cutting Game(数学，规律)(第七届福建省大学生程序设计竞赛)

2.1 Localization and Cutting-Plane Methods
Locatization and Cutting cutting-plane oracle 切平面池 finding cutting-planes 找到切平面 localization algorithms 定位算法 specific cutting -plance methods 特定切平面法 epigraph cutting-plane method 上镜图切平面法 lower bounds a