2021年ECNU计科考研复试机试

2021年ECNU计科考研复试机试

D. Weights II

Merchants measured many commodities using weights and a two-pan balance. If you are using a limited set of weights, however, you can only measure certain quantities accurately. For example, suppose that you have only two weights: a 1-ounce weight and a 3-ounce weight. With these you can easily measure out 4 ounces, as shown in Figure1.

Figure 1

It is somewhat more interesting to discover that you can also measure out 2 ounces by shifting the 1-ounce weight to the other side, as shown in Figure2.

Figure 2

Write a program to determine whether it is possible to measure out the desired target amount with a given set of weights.

输入格式

First line contains a single integer \( t(t<1000 ) \)

The first line of each test case contains an integers \( n( 1\leq n \leq 100)\) – thesize of the given set of weights.

The second line of each test case contains \( n \)integers\( w_1,w_2,\cdots, w_n( 1\leq w_i \leq 10^4 )\)

The third line of each test case contains an integer\( q(1\leq q \leq 10^4 )\)– thenumber of queries.

The fourth line of each test cases contains distinct integers – the desired target amounts.

It’s guaranteed that the sum of all does not exceed \( 10^4\).

输出格式

For each test case, output a binary string ,\( s\) s.t. \(s_i=1 \) if it is possible measure out the desired target amount \( W_i\) with the given set of weights and \( s_i=0 \) otherwise.

测试样例

Input

3
2
1 3
6
1 2 3 4 5 6
2
1 4
6
1 2 3 4 5 6
3
3 5 9
18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Output

111100
101110
111111111011010010

7 thoughts on “2021年ECNU计科考研复试机试

    1. 只要选择适当的算法(大概10^9的数据量的话设计O(NlogN)的算法,10^5的数据量用O(N^2)算法)一般都可以。
      具体时间的话,第1题时限1秒512MB,第2题1秒256MB,第3题3秒2GB,第4题2秒512MB。

    1. 以往线下复试的时候都计入复试成绩的。可能是因为线上复试的监考难免有漏洞所以暂时不计入成绩。

发表评论

电子邮件地址不会被公开。 必填项已用*标注