Yandex 2013Q(Atoms: There and Back Again-贪心+模拟+List)

Legend

Yura and Roman got bored with the original “Atoms” board game and came up with a better game that uses the same playing set. The game starts with one group of atoms. On each step, a player chooses number X and divides each group of atoms into two non-empty groups, at least one of them consisting ofX atoms. If there is no such X that it can be done, the game stops. The winner in this situation is... Roman and Yura have not decided yet, and it is currently irrelevant. Roman has just distributed some atoms into groups not following any specific rule, and now he wonders: is it possible to get this position while playing this new game?

Input format

The first line of input holds one integer N (1 ≤ N ≤ 10⁵): the number of groups. The second line holds Nspace-separated integers A_i: the number of atoms in i-th group (1 ≤ A_i ≤ 10¹⁸). If you are using stdinin C/C++, use format %lld for reading A_i.

Output format

Output a single word “YES” if the given position can be reached from a single group by the new rules, or “NO” otherwise.

Sample 1

Input	Output
4 1 2 6 1	YES

Sample 2

Input	Output
4 1 2 3 4	NO

Notes

In the first example, players can start with a group of 10, divide it into 3 and 7, then further divide the groups to get 1, 2, 1, 6.

C++ STL 中对List 的第一次运用。。

题目没什么好说的。。

因为每次必定有1个数超过半数（不可能有2个，0个无解）

那么不断模拟往上推就行了。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<list>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (100000+10)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
typedef long long ll;
typedef unsigned long long ull;
int n;
ull a[MAXN];
list<int> L;
int main()
{
//	freopen("yandex-2013 Q-Atoms.in","r",stdin);
	scanf("%d",&n);
	For(i,n) cin>>a[i];
	sort(a+1,a+1+n);
	For(i,n) L.push_back(a[i]);
	while (n>1)
	{
		if (n&1) {puts("NO");return 0;	}
		int tot=0,p=-1;
		for(list<int>::iterator it=L.begin();it!=L.end();it++)
		{
			if (p==*it) tot++;else tot=1,p=*it;
			if (tot>=n/2) break;
		}
		if (tot<n/2) {puts("NO");return 0;	}
		for(list<int>::iterator it=L.begin();it!=L.end();)
		{
			list<int>::iterator it2=it;
			if (p==*it&&tot) tot--,it++,L.erase(it2);else *it+=p,it++;			
		}	
		n>>=1;
	}
	puts("YES");
	
	return 0;
}

Time limit	2 seconds
Memory limit	256Mb
Input	stdin
Output	stdout