御坂美琴
misaka是呱太爷爷的小粉丝,呱太爷爷有一句话说的好:"一尺之棰,日取其半,万世不竭"。
misaka现在有 n 个呱太玩偶放在一堆,每一次操作,misaka会选择当前个数 > 1 的一堆呱太玩偶。并将这一堆呱太玩偶分成 和 两堆,x 是当前这一堆玩偶的个数。现在 misaka 想将玩偶分成 m 堆,其中第 i 堆呱太玩偶的个数是 ai ,你需要告诉 misaka 是否能通过若干次操作将玩偶分成指定的这 m 堆。如果可以输出 ,否则输出 。
输入描述:
第一行两个数 n, m 。
接下来一行 m 个数 ai 。
输出描述:
输出共一个字符串 ,表示 misaka 能否将玩偶分成指定的 m 堆。
输入
4 1
5
输出
ham
备注:
1 ≤ n ≤ 10^18, 1 ≤ m ≤ 10^5, 1 ≤ ai ≤ 10^18。
题意很简单,n个物品,有m次,每次按题意分成两堆物品,求是否可以这样分;
用map标记可以分的数组,
#include <iostream>#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=1e5+5;ll s[maxn];map<ll,ll>mp;void fun(ll n){if(mp[n])return ;mp[n]=1;if(n==1)return;f(n/2);f(n-n/2);}int main(){ll n,m;cin>>n>>m;ll ans=0;for(ll i=0; i<m; i++){cin>>s[i];ans+=s[i];}if(ans!=n){cout<<"ham"<<endl;return 0;}fun(n);for(ll i=0; i<m; i++)if(!mp[s[i]]){cout<<"ham"<<endl;return 0;}cout<<"misaka"<<endl;return 0;}