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.

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.

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 ﬁrst 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. wxy说道：

问一下m大，这些题目的时间限制是多少？Eoj平台1秒能跑多少呢？

1. malic说道：

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

2. wxy说道：

Eoj一秒可以跑1e10吗，这么快吗。。。

3. aqa芭蕾，eqe亏内说道：

复试时英语与面试的权重还是1:2吗

1. malic说道：

复试之前会收到复试通知的Email，当中会清楚地说明的。

4. aqa芭蕾，eqe亏内说道：

以后的机试也不直接计入复试成绩吗

1. malic说道：

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