/*TASK:I Count Two Three 2^a*3^b*5^c*7^d的最小的大于等于n的数是多少LANG:C++URL:http://acm.hdu.edu.cn/showproblem.php?pid=5878*/#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#define ll long longusing namespace std;const int N=32;const ll M=1e9+1;int tw,th,fi,se,t,n;ll two[N]={1},three[N]={1},five[N]={1},seven[N]={1};ll ans[7000],cnt;int main() {	for(int i=1;two[i-1]<M;i++,tw++)		two[i]=two[i-1]*2;	for(int i=1;three[i-1]<M;i++,th++)		three[i]=three[i-1]*3;	for(int i=1;five[i-1]<M;i++,fi++)		five[i]=five[i-1]*5;	for(int i=1;seven[i-1]<M;i++,se++)		seven[i]=seven[i-1]*7;			for(int i=0;i<tw;i++)	for(int j=0;three[j]*two[i]<M&&j<th;j++)	for(int k=0;five[k]*three[j]*two[i]<M&&k<fi;k++)	for(int g=0;seven[g]*five[k]*three[j]*two[i]<M&&g<se;g++)		ans[cnt++]=two[i]*three[j]*five[k]*seven[g];			sort(ans,ans+cnt);		scanf("%d",&t);	while(t--){		scanf("%d",&n);		printf("%lld\n",ans[lower_bound(ans,ans+cnt,n)-ans]);	}}

/*TASK:求∑1/k^2 k=1到nLANG:C++URL:http://acm.hdu.edu.cn/showproblem.php?pid=5879*/#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#define ll long long#define N 115000using namespace std;char n[1000000];double ans[N];void init(){	for(ll i=1;i<N;i++)		ans[i]=ans[i-1]+1.0/(i*i);}double get(){	int a=0,len=0;	for(int i=0;n[i]&&len<7;i++,len++)		a=a*10+n[i]-‘0‘;	if(len==7||a>=N)return 1.64493;	return ans[a];}int main() {	init();	while(~scanf("%s",n)){		printf("%.5f\n",get());		memset(n,0,sizeof n);	}}

/*TASK:壶里有L到R区间的水，倒俩杯里，倒完时相差不超过1，壶里最多可以余1，求最少多少次一定能倒完。LANG:C++URL:http://acm.hdu.edu.cn/showproblem.php?pid=5881*/#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#define ll long longusing namespace std;ll l,r,ans;int main() {	while(~scanf("%lld%lld",&l,&r)){		if(r<=1)			ans=0;		else if(r<=2)			ans=1;		else if(l==r)			ans=2;		else if(l==0)//第一次倒l/2+0.5，第二次倒l/2+1.5，然后2、2、2、如果l==0，不如第一次就倒1，然后2、2、2			ans=1+(r-1)/2;		else{			r-=l+2;//前两次倒的			ans=2+r/2;		}		printf("%lld\n",ans);	}	return 0;}

/*TASK:The Best Path 求经过连通图的所有边一次且经过点异或起来值最大的路的异或值LANG:C++URL:http://acm.hdu.edu.cn/showproblem.php?pid=5883*/#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#define ll long long#define N 100005using namespace std;int t,n,m,a[N];int du[N];void solve(){	int num=0;	for(int i=1;i<=n;i++)		if(du[i]%2)			num++;	if(num!=2&&num){		puts("Impossible");		return;	}	int ans=0;	for(int i=1;i<=n;i++)		for(int j=1;j<=(du[i]+1)/2;j++)			ans^=a[i];	if(!num){		int tans=ans;		for(int i=1;i<=n;i++)			ans=max(ans,tans^a[i]);	}	printf("%d\n",ans);}int main() {	scanf("%d",&t);	while(t--){		memset(du,0,sizeof du);		scanf("%d%d",&n,&m);		for(int i=1;i<=n;i++)			scanf("%d",&a[i]);		for(int i=1;i<=m;i++){			int u,v;			scanf("%d%d",&u,&v);			du[u]++;			du[v]++;		}		solve();	}	return 0;}

/*TASK:Sort 合并数列，每次合并花费数列大小之和，求总代价不超过T的最小的每次最多合并个数k。LANG:C++URL:http://acm.hdu.edu.cn/showproblem.php?pid=5884*/#include<cstdio>#include<algorithm>#include<cstring>#define N 100005#define ll long longusing namespace std;ll n,t,p;ll a[N],h[N],cost;//h是合并后的优先队列ll solve(int k){	memset(h,0,sizeof h);	t=(n-1)/(k-1);//需要减少n-1堆，每次减少k-1堆能合并几次。	p=(n-1)%(k-1);//还要减少p堆（p<k-1）	for(int i=0; i<=p; i++)//那就合并前p+1堆		h[0]+=a[i];	int top=p+1,htop=0;	ll ans=p?h[0]:0;//第一次有合并则加上合并的代价。	for(int i=1; i<=t; i++)//k个k个合并t次	{		for(int j=0; j<k; j++)//合并k个			if(htop>=i||a[top]<h[htop]&&top<n)//如果合并队列里没有了可选的了，或者未合并队列的更小，则取未合并队列的。				h[i]+=a[top++];			else				h[i]+=h[htop++];		ans+=h[i];//累加答案		if(ans>cost)			return 0;	}	if(ans>cost)		return 0;	return 1;}int main(){	int t;	scanf("%d",&t);	while(t--){		scanf("%lld%lld",&n,&cost);		for(int i=0; i<n; i++)			scanf("%lld",&a[i]);		sort(a,a+n);		int l=2,r=n;		while (l<r) {			int m=(l+r)/2;			if(solve(m))				r=m;			else				l=m+1;		}		printf("%d\n",l);	}	return 0;}

/*TASK:Herbs Gathering 容量很大，价值也很大，数量少的01背包问题。LANG:C++URL:http://acm.hdu.edu.cn/showproblem.php?pid=5887*/#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <map>#define ll long longusing namespace std;const int N=108;map<ll,ll>mm[N];map<ll,ll>::iterator it,ij;int n,t;ll a[N],b[N];int main() {	while(~scanf("%d%d",&n,&t)){		for(int i=0;i<=n;i++)		mm[i].clear();		mm[0][0]=0;		for(int i=1;i<=n;i++){			scanf("%lld%lld",&a[i],&b[i]);			mm[i][0]=0;		}				for(int i=1;i<=n;i++){			for(it=mm[i-1].begin();it!=mm[i-1].end();it++){				if(it->first+a[i]<=t)				{					if(mm[i].count((it->first)+a[i]))						mm[i][(it->first)+a[i]]=max(it->second+b[i],mm[i][(it->first)+a[i]]);					else mm[i][(it->first)+a[i]]=it->second+b[i];				}				if(mm[i].count((it->first)))					mm[i][(it->first)]=max(it->second,mm[i][it->first]);				else					mm[i][it->first]=it->second;								ll rm=0;				for(ij=mm[i].begin();ij!=mm[i].end();ij++){					//printf("%d [%lld %lld]:[%lld %lld]\n",i,ij->first,ij->second,it->first,it->second);					if(ij->first>it->first &&ij->second<it->second)						rm=ij->first;					else if(ij->first<it->first && ij->second>it->second)						rm=it->first;				}				if(rm)					mm[i].erase(rm);			}		}		ll ans=0;		for(it=mm[n].begin();it!=mm[n].end();it++)			ans=max(ans,(it->second));				printf("%lld\n",ans);	}	}

/*TASK:Barricade 求最短路的最小割LANG:C++URL:http://acm.hdu.edu.cn/showproblem.php?pid=5889*/#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#define ll long long#define N 1005#define M 40010#define inf 0x3f3f3f3fusing namespace std;struct edge{	int to,next,cap,flow;}e[M];int head[N],cnt;int gap[N],dep[N],cur[N];void init(){	cnt=0;	memset(head, -1, sizeof head);}void add(int u,int v,int w,int rw=0){	e[cnt]=(edge){v,head[u],w,0};	head[u]=cnt++;	e[cnt]=(edge){u,head[v],rw,0};	head[v]=cnt++;}int q[N];void bfs(int st,int ed){	memset(dep,-1,sizeof dep);	memset(gap,0,sizeof gap);	gap[0]=1;	int front=0,rear=0;	dep[ed]=0;	q[rear++]=ed;	while(front!=rear){		int u=q[front++];		for(int i=head[u];~i;i=e[i].next){			int v=e[i].to;			if(dep[v]!=-1)continue;			q[rear++]=v;			dep[v]=dep[u]+1;			gap[dep[v]]++;		}	}}int s[N];int sap(int st,int ed,int n){	bfs(st,ed);	memcpy(cur,head,sizeof head);	int top=0;	int u=st;	int ans=0;	while(dep[st]<n){		if(u==ed){			int Min=inf;			int inser;			for(int i=0;i<top;i++)				if(Min>e[s[i]].cap-e[s[i]].flow){					Min=e[s[i]].cap-e[s[i]].flow;					inser=i;				}			for(int i=0;i<top;i++){				e[s[i]].flow+=Min;				e[s[i]^1].flow-=Min;			}			ans+=Min;			top=inser;			u=e[s[top]^1].to;			continue;		}		bool flag=false;		int v;		for(int i=cur[u];~i;i=e[i].next){			v=e[i].to;			if(e[i].cap-e[i].flow&&dep[v]+1==dep[u]){				flag=true;				cur[u]=i;				break;			}		}		if(flag){			s[top++]=cur[u];			u=v;			continue;		}		int Min=n;		for(int i=head[u];~i;i=e[i].next)			if(e[i].cap-e[i].flow &&dep[e[i].to]<Min){				Min=dep[e[i].to];				cur[u]=i;			}		gap[dep[u]]--;		if(!gap[dep[u]])return ans;		gap[dep[u]=Min+1]++;		if(u!=st)u=e[s[--top]^1].to;	}	return ans;}int n,m;int g[N][N],vis[N],d[N];void solve(){	int l=0,r=0;	q[0]=1;	d[1]=0;	memset(vis,0,sizeof vis);	while(l<=r){		int k=q[l++];		for(int i=2;i<=n;i++)if(g[k][i]!=-1){			if(vis[i])continue;			q[++r]=i;			vis[i]=1;			d[i]=d[k]+1;		}	}	init();	for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	if(g[i][j]!=-1&&d[j]==d[i]+1)		add(i,j,g[i][j]);		printf("%d\n",sap(1,n,n));}int main() {	int t;	scanf("%d",&t);	while(t--){		scanf("%d%d",&n,&m);		memset(g,-1,sizeof g);		for(int i=1;i<=m;i++){			int u,v,w;			scanf("%d%d%d",&u,&v,&w);			g[v][u]=g[u][v]=w;		}		solve();	}	return 0;}