2048 Game

间接性划水，持续性自闭。

2048 Game

题目链接

A. 2048 Game

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are playing a variation of game 2048. Initially you have a multiset ss of nn integers. Every integer in this multiset is a power of two.

You may perform any number (possibly, zero) operations with this multiset.

During each operation you choose two equal integers from ss, remove them from ss and insert the number equal to their sum into ss.

For example, if s={1,2,1,1,4,2,2}s={1,2,1,1,4,2,2} and you choose integers 22 and 22, then the multiset becomes {1,1,1,4,4,2}{1,1,1,4,4,2}.

You win if the number 20482048 belongs to your multiset. For example, if s={1024,512,512,4}s={1024,512,512,4} you can win as follows: choose 512512 and 512512, your multiset turns into {1024,1024,4}{1024,1024,4}. Then choose 10241024 and 10241024, your multiset turns into {2048,4}{2048,4} and you win.

You have to determine if you can win this game.

You have to answer qq independent queries.

Input

The first line contains one integer qq (1≤q≤1001≤q≤100) – the number of queries.

The first line of each query contains one integer nn (1≤n≤1001≤n≤100) — the number of elements in multiset.

The second line of each query contains nn integers s1,s2,…,sns1,s2,…,sn (1≤si≤2291≤si≤229) — the description of the multiset. It is guaranteed that all elements of the multiset are powers of two.

Output

For each query print YES if it is possible to obtain the number 20482048 in your multiset, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

Example

input

6
4
1024 512 64 512
1
2048
3
64 512 2
2
4096 4
7
2048 2 2048 2048 2048 2048 2048
2
2048 4096

output

YES
YES
NO
NO
YES
YES

Note

In the first query you can win as follows: choose 512512 and 512512, and ss turns into {1024,64,1024}{1024,64,1024}. Then choose 10241024 and 10241024, and ssturns into {2048,64}{2048,64} and you win.

In the second query ss contains 20482048 initially.

这道题和我们玩得游戏2048一样，只要你能够凑出2048，you win！！！

一开始，没有想那多,就是想直接模拟一下。

AC_1

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[1010];
bool cmp(int a,int b)
{
	return a>b;
 } 
int main()
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		int m,flag=0;
		scanf("%d",&m);
		for(int i=0;i<m;++i)
		{	
			scanf("%d",&a[i]);
		}
		sort(a,a+m,cmp);
		int k =2048;
		int sum=0;
		for(int i =0;i<m;++i)
		{
			if(k>=a[i]&&k%a[i]==0)
			{
				sum += a[i];
			}
			if(k == sum)
			{
				flag = 1;
				break;
			}
		}
		if(flag==1)
			printf("YES\n");
		else
			printf("NO\n");
		
	}
	return 0;
 }

AC_2

之后有人跟我说，这是分治，我也没听懂他在说什么，就去了CSDN，找了教程。

分治：原来就是把问题划分为相互独立的子问题进行处理。（必然联系到递归）

• 比如，你想找是否有没有2048，此时把2048分成1024 1024，你可以找1024，然后看看集合中有几个1024，是否满足条件。

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
//int a[100005];
map<int,int> mp;
int dfs(int x,int n)
{
	if(x<1) return 0;
	if(mp[x] >= n)
		return 1;
	return dfs(x/2,n*2-2*mp[x]);
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		mp.clear(); 
		int m;
		cin>>m;
		for(int i =0;i<m;++i)
		{
			int s;
			cin>>s;
			mp[s]++;
		}
		int flag = dfs(2048,1);
		if(flag)
			printf("YES\n");
		else
			printf("NO\n");
	}
 }