Mancunian Hoards Black Money，贪心，思维-Toy模板网

这篇具有很好参考价值的文章主要介绍了Mancunian Hoards Black Money，贪心，思维。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Mancunian Hoards Black Money - Problems - CodeChef

Mancunian is a real estate dealer in Mancunia. He is part of The Elite Builders Society who work hard day and night to improve the infrastructure of thecity, but they need cash to do this. They have a unique way to increase the amount of black money they possess. They start with a pile of cash amounting to S dollars. Then they repeat the following process N times. Before the ith step, there are already i piles of cash on the table. They create another pile amounting to the sum of amounts of all the i previous piles and add another Ci dollars to it.

A hot piece of property priced at X dollars has just appeared on the market and the society decided that they must buy it at all costs. They need to select a few of the piles from the ones on the table, whose sum is exactly X.

Although shrewd businessmen, they lack mathematical skills. Can you help them decide whether it is possible or not?

Input

The first line of the file contains an integer T denoting the number of test cases.

Each case consists of two lines.

The first line contains three integers S, N and X denoting the amount of cash in the first pile, the number of times the society creates a new pile and the cost of the in-demand property respectively.

The second line contains N integers denoting the values Ci mentioned in the problem description.

Output

Output T lines. In each line, output "yes" if the society can buy the property and "no" otherwise.

Constraints

1 ≤ T, N ≤ 105
1 ≤ sum of N over all test cases ≤ 105
1 ≤ S, X, Ci ≤ 1018

Example

Input:
2
1 4 6
1 2 4 2
100 2 500
51 749

Output:
yes
no

Explanation

Example case 1: The piles of cash are 1, 2, 5, 12 and 22. The society will use the piles of cash amounting to 1 and 5 to get a total of 6.

Example case 2: The piles of cash are 100, 151 and 1000. The society cannot buy the property costing 500 using any of the piles of cash they have.

解析：

贪心；
我们需要根据题目所给的 S 和 c[i] 推出每堆 cash 的值 a[i] ，在此过程中我们还会推出 a[i] 的前缀和数组 sum[[i];
通过观察我们发现如果 X > sum[i] 那么 X 一定加数中一定有 a[i+1];
因为:

sum[i+1]>X>sum[i],如果没有 a[i+1]，那么 sum[i] 中一定没有能够凑到 X 的数，且通过a序列的生成方式我们知道 a[i+2] 一定大于 sum[i] ,所以当 sum[i+1]>X ，X 的加数中一定不可能存在 a[i+1] 后的数。

让我们举一个例子。对于给定的${C_i} 值，设级数为${1,3,6,15,30,70}$。让我们看看值为30的桩。在此之前的所有桩的总和为1+3+6+15=25，小于30。
现在，如果$X$的值在（30,70）范围内，你会怎么做？注意，如果我们去掉堆30，我们就不能形成30到70之间的任何值。如果我们排除桩30，则桩30之前的桩不能用于形成桩30和70之间的值。这是因为即使包括30之前的所有桩，我们也无法形成超过30的值。我们完全依赖于桩30来形成30-70之间的值。
文章来源地址https://www.toymoban.com/news/detail-723864.html

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
LL S ,n,X;
LL c[N],a[N], sum[N];


int main() {
	int T;
	cin >> T;
	while (T--) {
		scanf("%lld%lld%lld", &S, &n, &X);
		for (int i = 1; i <= n; i++) {
			scanf("%lld", &c[i]);
		}
		a[1] = S;
		sum[1] = S;
		int cnt = 1;
		for (int i = 2; i <= n+1; i++) {
			if (sum[i - 1] + c[i - 1] > 1e18)
				break;
			a[i] = sum[i - 1] + c[i - 1];
			sum[i] = sum[i - 1] + a[i];
			cnt++;
		}
		for (int i = cnt; i >= 0; i--) {
			if (X>sum[i]) {
				X -= a[i+1];
			}
		}
		if (X == 0)
			cout << "yes" << endl;
		else
			cout << "no" << endl;
	}
	return 0;
}

到了这里，关于Mancunian Hoards Black Money，贪心，思维的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！