简要题意及解析
1001
给出一个(n imes m)连连看的局面，下面有(q)次询问：两个位置的块能否消去，即两个位置的连线是否能少于两次转折，回答(YES/NO)。与一般的连连看不同之处在于，连线不能从外围绕过
先判断两个位置是否是空地，是否是一种颜色，然后从其中一个位置开始(dfs/bfs)，由于限制条件和转折次数有关，因此要记录转折次数。搜索的时候要先采用转折少的方案，不然复杂度不对。
时间复杂度(O(Tnmq))
(T)为数据组数，(n,m,q)如题意。
1002
在一个(m imes n)的矩形迷宫中，用空地、障碍和楼梯，楼梯有两个方向——左右和上下，而且每过(1)分钟换一次方向，登上楼梯并经过楼梯只需要(1)分钟，不能再楼梯上停留，求从起点到终点最短要多长时间。
与一般的迷宫问题唯一的不同点就是这个楼梯。楼梯的方向其实很好处理，当你处于一个状态((x,y,t))，在位置((x,y))时间为(t)时，你可以判断(t)的奇偶求出某个楼梯的方向。想明白了这个，就可以(dfs/bfs)了，求最短距离最好还是用(bfs)，我不知道为什么脑抽写了个(dfs)。
时间复杂度(O(Tnm))
(T)是数据组数，(n,m)如题意。
1003
给出(n)个数，求最大连续子序列——就是最大子段和呗。
那个经典的线性算法就不提了。刚刚想出另一个线性算法，(sum[i])表示前(i)个的累加和。从小到大枚举子段的右端点(R)，可以尝试求出以(R)为右端点的最大子段和。我们可以找到(min_{i=1}^{ileq R-1}{sum[i]})，设这个位置为(L)，那么([L+1,R])就是所求的最大子段。
从左向右枚举(R)的同时维护这个(min)即可。
时间复杂度(O(Tn))
(T)是数据组数，(n)是序列长度。
1004
有(N)个数，给出他们两两之和，求这(N)个数。保证解存在且唯一。
整理一下数据，和共有(K)种，第(i)种为(a[i])，出现(b[i])次。
最小的和一定是最小两个数相加，先枚举最小数，然后开始(dfs)。
(dfs)每层先找到最小的未出现(b[i])次的和数(a[i])。枚举已经有的加数(x)，认为(a[i])是由(x+y)组成的，并检验加数集合加入(y)是否合法，更新每个和数出现的次数，若可行就进行下一层(dfs)。
时间复杂度(O(TN^{N^3}logN))，可行方案并不多，剪枝可以减掉很多，实际时间远小于上界。
(T)为数据组数，(N)为数字数量。
1005
给出一些单词，你可以使用这个单词把它的首字母变成末字母，问你能否吧(B)变成(M)。
本质上是有向图连通性，怎么写都行(dfs/bfs/floyd)
时间复杂度(O(TL))
(T)为数据组数，(L)为所有单词长度和。
1006
给出(n)个字符串，你要找到最长的一个串使得这个串或者他的反转串在这(n)个串中都出现过。求这个长度。
很暴力的一道题。先枚举(/)二分这个长度(L)，然后从第一个串中枚举长度为(L)的串，判断它或它的反转串在剩下(n-1)个串中是否全部出现，如果全部出现，则答案(L)可行。
时间复杂度(O(Tn^2L^2logL))
(T)为数据组数，(n)字符串数量，(L)为字符串长度。
1007
给出很多组火星单词和对应的地球单词，然后给出一段火星文，把这段火星文中的火星单词全部替换为地球单词输出，如果不能识别某个火星单词，不做替换即可。
输入比较烦，注意是否读入了空行。
其实就是把火星文中的单词提取出来，尝试替换即可，但是这题不给数据范围，还是考虑一些高效的方法。如何判断一个单词是否出现过，可以用字符串(Hash)，也可以用(STL)的(map<string,string>)。不知道为啥我的字符串(Hash)挂了，不得不用(map)。
直接用(map)存好火星单词和地球单词的对应关系。然后从火星文里每次找一个单词，尝试替换。
时间复杂度(O(TmLlogn))
(T)为数据组数，(n)为单词数量，(L)为字符串总长度，(m)为文章数量。
1008
素数环问题。求出字典序最小的(1)到(n)的圆排列，要求相邻两数之和为质数。
(dfs+)回溯，第(i)层枚举第(i)个位置填什么，检验它与前数之和是否为质数。注意枚举了最后一个数之后还要检验最后一个数和第一个数。
时间复杂度(O(Tn^n))，剪枝很有效，实际复杂度远小于上界。
(T)为数据组数，(n)为数字数量。
1009
又是一个类似迷宫问题，不同点在于有些地方有怪物，打怪要消耗一定时间。此题需要输出方案。
求最短时间最好用(bfs)（我怎么又写了(dfs)）。搜索的同时记录前驱位置，最后用这个前驱数组就可可以找到最优方案的路径了。
时间复杂度(O(Tnm))
(T)为数据组数，(n,m)为地图长宽。
1010
门票(50)元，售票处初始没有钱。
有(m)个拿着(50)元大钞的人，(n)个拿着(100)元巨钞的人，求共有多少种排队方案能让这(m+n)个人顺利买到票。
动态规划。
(f[i][j])表示排好了(i)个拿着(50)元的人和(j)个拿着(100)元的人的方案数。
[f[i][j]=f[i-1][j] imes (m-i+1)+f[i][j-1] imes (n-j+1)
]
注意答案会非常大，要使用大数。
时间复杂度(O(Tnm))
(T)为数据组数，(n,m)如题意。
1011
一(n)个节点的树，树的每个节点上可能有一些(bug)。你有(m)组军队，每组军队可以处理一个节点的(20)个(bug)，处理掉一个节点的所有(bug)会有一定收益，你从(1)号节点出发，可以分兵，进入下一个节点之前必须解决掉当前节点的(bug)。求你能获得的最多收益。
树形动态规划，转移类似背包。
(f[i][j])表示在以(i)为根的子树上，分配(j)组兵能获得的最大收益。
[f[x][j+k]=max_{j+kleq m}{{f[x][j+k],f[x][j]+f[y][k]}}
]
其中，(x)为当前节点，(y)为(x)的子节点。最终答案为(f[1][m])
时间复杂度(O(Tnm^2))
(T)为数据组数，(n,m)同题意。
1012
给出一个字符串，输出反转串。
没啥好说的。
时间复杂度(O(Tn))
(T)为数据组数，(n)为字符串长度。
1013
在一个比赛中，有(1)号到(100)号葡萄给两个选手争抢，选手得分为抢到的葡萄编号之积。给出两个选手的得分，保证得分不同，低分选手会质疑高分选手说谎，假定低分选手不说谎(The player with the lower score is presumed to have told the truth)。你要判断高分选手是否说谎，如果说谎，输出低分选手分数，否则输出高分选手分数。
直接(dfs)搜索，每个编号有三种情况，两人都没拿或其中一个人拿。剪剪枝就好了。不过，其实低分选手还是可能说谎的，如果低分选手说谎，输出高分选手分数(与题目描述相悖，但是只有这样能过)。
时间复杂度(O(3^{100}T))，实际复杂度远低于上界。
(T)为数据组数。
1014
有一个(n)层电梯，从第(i)层可以向上或向下(a[i])层，不能到达不存在的楼层。求从第(A)层到第(B)层最少要几次，不能到达则输出(-1)
从第(A)层开始(bfs)，记录当前位置和所用次数，第一次到达第(B)层即为答案。
时间复杂度(O(Tn))
(T)为数据组数，(n)为层数。
1015
给出(m)个木棍，问是否能拼成一个正方形。
(dfs+)剪枝。一定要枚举正方形的(3)条边分别使用了那些木棍，不能搜索第(i)个木棍属于第几条边。至于原因，说不清楚，反正会超时，可能是第二种搜索方式不利于剪枝。
时间复杂度(O(3^mT))
(T)为数据组数，(m)为木棍数量。
代码警告
代码警告
代码警告
代码警告
代码警告
代码警告
代码合集：
//1001
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=1010;
const int ws_[4]={0,1,0,-1},ad_[4]={1,0,-1,0};
int N,M,mp[maxn][maxn],sx,sy,fx,fy;
int vis[maxn][maxn][4];
bool out(int x,int y){
return x<=0||y<=0||x>N||y>M;
}
void dfs(int x,int y,int d,int t){
if(t>2)return;
if(t>=vis[x][y][d])return;
vis[x][y][d]=t;
int tx=x+ws_[d],ty=y+ad_[d];
if(!out(tx,ty))
if(mp[tx][ty]==0||(tx==fx&&ty==fy))
dfs(tx,ty,d,t);
for(int i=0;i<4;i++)
if(d!=i){
tx=x+ws_[i],ty=y+ad_[i];
if(out(tx,ty))continue;
if(mp[tx][ty]!=0&&!(tx==fx&&ty==fy))continue;
dfs(tx,ty,i,t+1);
}
}
bool judge(){
memset(vis,10,sizeof(vis));
dfs(sx,sy,0,0);
dfs(sx,sy,1,0);
dfs(sx,sy,2,0);
dfs(sx,sy,3,0);
return vis[fx][fy][0]<=2||vis[fx][fy][1]<=2||vis[fx][fy][2]<=2||vis[fx][fy][3]<=2;
}
int main(){
//freopen("in","r",stdin);
while(1){
N=read(),M=read();
if(N+M==0)break;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
mp[i][j]=read();
for(int _=read();_;_--){
sx=read(),sy=read(),fx=read(),fy=read();
if(mp[sx][sy]!=mp[fx][fy]||!mp[sx][sy])
puts("NO");
else if(!judge())
puts("NO");
else
puts("YES");
}
}
return 0;
}
//1002
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=25;
const int ws_[4]={1,-1,0,0},ad_[4]={0,0,1,-1};
int N,M,sx,sy,fx,fy;
char mp[maxn][maxn];
int vis[maxn][maxn][2];
void dfs(int x,int y,int t){
if(mp[x][y]=='*')return;
if(t>=vis[x][y][t&1])
return;
vis[x][y][t&1]=t;
dfs(x,y,t+1);
for(int i=0;i<4;i++){
int tx=x+ws_[i],ty=y+ad_[i];
if(mp[tx][ty]=='*')continue;
if(mp[tx][ty]=='|'){
if(i<2&&!(t&1))
dfs(tx+ws_[i],ty,t+1);
else if(i>=2&&(t&1))
dfs(tx,ty+ad_[i],t+1);
}
else if(mp[tx][ty]=='-'){
if(i>=2&&!(t&1))
dfs(tx,ty+ad_[i],t+1);
else if(i<2&&(t&1))
dfs(tx+ws_[i],ty,t+1);
}
else
dfs(tx,ty,t+1);
}
}
int main(){
//freopen("in","r",stdin);
while(scanf("%d%d",&N,&M)!=EOF){
memset(mp,'*',sizeof(mp));
memset(vis,10,sizeof(vis));
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++){
mp[i][j]=one();
if(mp[i][j]=='S')sx=i,sy=j;
if(mp[i][j]=='T')fx=i,fy=j;
}
dfs(sx,sy,0);
printf("%d
",min(vis[fx][fy][0],vis[fx][fy][1]));
}
return 0;
}
//1003
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=10010;
int N,a[maxn];
int main(){
//freopen("in","r",stdin);
while(1){
N=read();
if(!N)break;
for(int i=1;i<=N;i++)
a[i]=read();
long long sum=0,Min=0,ans=-1;
int idMin=0,ansL,ansR;
for(int i=1;i<=N;i++){
sum+=a[i];
if(sum-Min>ans)
ans=sum-Min,ansL=idMin+1,ansR=i;
if(sum<Min)
Min=sum,idMin=i;
}
if(ans==-1)
ans=0,ansL=1,ansR=N;
printf("%I64d %d %d
",ans,a[ansL],a[ansR]);
}
return 0;
}
//1004
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=5010;
int N,M,tot,a[maxn],ans[maxn],vis[maxn];
bool succ;
void dfs(int x){
if(succ)return;
if(x==N+1){
sort(ans+1,ans+1+N);
for(int i=1;i<N;i++)
printf("%d ",ans[i]);
printf("%d
",ans[N]);
succ=1;
return;
}
for(int i=1;i<=tot;i++)
if(vis[i]){
for(int j=1;j<x;j++){
int v=a[i]-ans[j];
if(v<=0)continue;
bool flag=1;
for(int k=1;k<x;k++){
int tmp=v+ans[k];
if(tmp>a[tot]){flag=0;break;}
int pos=lower_bound(a+1,a+1+tot,tmp)-a;
if(a[pos]!=tmp){flag=0;break;}
}
if(!flag)continue;
for(int k=1;k<x;k++){
int tmp=v+ans[k];
int pos=lower_bound(a+1,a+1+tot,tmp)-a;
vis[pos]--;
if(vis[pos]<0)flag=0;
}
ans[x]=v;
if(flag)
dfs(x+1);
for(int k=1;k<x;k++){
int tmp=v+ans[k];
int pos=lower_bound(a+1,a+1+tot,tmp)-a;
vis[pos]++;
}
}
break;
}
}
int main(){
//freopen("in","r",stdin);
while(1){
N=read();M=N*(N-1)/2;tot=0;
if(!N)break;
for(int i=1;i<=M;i++){
int tmp=read();
if(tmp!=a[tot])
a[++tot]=tmp,vis[tot]=1;
else
vis[tot]++;
}
succ=0;
for(int i=1;i<=a[1];i++){
ans[1]=i;
dfs(2);
if(succ)break;
}
}
return 0;
}
//1005
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
char s[1010];
bool e[26][26];
int main(){
//freopen("in","r",stdin);
while(scanf("%s",s+1)!=EOF){
memset(e,0,sizeof(e));
while(1){
int len=strlen(s+1);
if(len==1&&s[1]=='0')break;
e[s[1]-'a'][s[len]-'a']=1;
scanf("%s",s+1);
}
for(int i=0;i<26;i++)
e[i][i]=1;
for(int k=0;k<26;k++)
for(int i=0;i<26;i++)
for(int j=0;j<26;j++)
e[i][j]|=e[i][k]&e[k][j];
if(e['b'-'a']['m'-'a'])
puts("Yes.");
else
puts("No.");
}
return 0;
}
//1006
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=110;
int N,len[maxn];
char s[maxn][maxn];
inline bool match(int a,int la,int ra,int b,int lb,int rb){
for(;la<=ra;la++,lb++){
if(s[a][la]!=s[b][lb])
return 0;
}
return 1;
}
inline bool revmatch(int a,int la,int ra,int b,int lb,int rb){
for(;la<=ra;la++,rb--){
if(s[a][la]!=s[b][rb])
return 0;
}
return 1;
}
bool check(int x){
for(int i=1;i+x-1<=len[1];i++){
bool find=1;
for(int j=2;j<=N;j++){
bool vis=0;
for(int k=1;k+x-1<=len[j];k++)
if(match(1,i,i+x-1,j,k,k+x-1)||revmatch(1,i,i+x-1,j,k,k+x-1)){
vis=1;
break;
}
if(!vis){
find=0;
break;
}
}
if(find)
return 1;
}
return 0;
}
int main(){
//freopen("in","r",stdin);
for(int _=read();_;_--){
int L=0,R=maxn,mid;
N=read();
for(int i=1;i<=N;i++){
scanf("%s",s[i]+1);
len[i]=strlen(s[i]+1);
R=min(R,len[i]);
}
while(L+1<R){
mid=(L+R)/2;
if(check(mid))
L=mid;
else R=mid;
}
printf("%d
",L);
}
return 0;
}
//1007
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
return xx*ff;
}
map<string,string>mp;
string nul,st="START",en="END";
string s1,s2;
char s[3010];
char ch;
int len;
int main(){
//freopen("in","r",stdin);
cin>>s1;
while(1){
cin>>s1;
if(s1==en)
break;
cin>>s2;
mp[s2]=s1;
}
cin>>s1;
getchar();
while(1){
s1="";
gets(s);
len=strlen(s);
if(s[0]=='E'&&s[1]=='N'&&s[2]=='D'&&len==3)
break;
for(int i=0;i<len;i++){
if(s[i]>='a'&&s[i]<='z'){
s1+=s[i];
if(s[i+1]>'z'||s[i+1]<'a'){
if(mp[s1]!=nul)
cout<<mp[s1];
else
cout<<s1;
s1="";
}
}
else
putchar(s[i]);
}
if(s1!=nul)
cout<<s1;
puts("");
}
return 0;
}
//1008
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=25;
int N,a[maxn];
bool isprime[maxn*2];
void get_prime(int n=40){
memset(isprime,1,sizeof(isprime));
isprime[0]=isprime[1]=0;
for(int i=2;i<=n;i++){
if(isprime[i])
for(int j=i*i;j<=n;j+=i)
isprime[j]=0;
}
}
bool use[maxn];
int ans[maxn];
void dfs(int x){
if(x==N+1){
if(isprime[ans[1]+ans[N]]){
for(int i=1;i<N;i++)
printf("%d ",ans[i]);
printf("%d
",ans[N]);
}
return;
}
for(int i=1;i<=N;i++)
if(!use[i]&&isprime[i+ans[x-1]]){
ans[x]=i;
use[i]=1;
dfs(x+1);
use[i]=0;
}
}
int main(){
//freopen("in","r",stdin);
get_prime();
int cas=1;
while(scanf("%d",&N)!=EOF){
printf("Case %d:
",cas++);
use[1]=1,ans[1]=1;
dfs(2);
puts("");
}
return 0;
}
//1009
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=105,ws_[4]={0,1,0,-1},ad_[4]={1,0,-1,0};
int N,M;
char mp[maxn][maxn];
struct status{
int x,y,t;
status(int x=0,int y=0,int t=0){
this->x=x,this->y=y,this->t=t;
}
bool friend operator<(const status&A,const status&B){
return A.t>B.t;
}
}from[maxn][maxn];
priority_queue<status>pq;
int vis[maxn][maxn];
inline bool out(int x,int y){
return x<=0||y<=0||x>N||y>M;
}
void bfs(){
memset(vis,10,sizeof(vis));
pq.push(status(1,1,0));
vis[1][1]=0;
while(!pq.empty()){
status s=pq.top();
pq.pop();
for(int i=0;i<4;i++){
int tx=s.x+ws_[i],ty=s.y+ad_[i],tt=s.t+1;
if(out(tx,ty)||mp[tx][ty]=='X')
continue;
if(mp[tx][ty]>='1'&&mp[tx][ty]<='9')
tt+=mp[tx][ty]-'0';
if(tt<vis[tx][ty]){
vis[tx][ty]=tt;
pq.push(status(tx,ty,tt));
from[tx][ty]=s;
}
}
}
}
void dfs(int x,int y){
if(x==1&&y==1)
return;
status pre=from[x][y];
dfs(pre.x,pre.y);
printf("%ds:(%d,%d)->(%d,%d)
",pre.t+1,pre.x-1,pre.y-1,x-1,y-1);
if(mp[x][y]>='1'&&mp[x][y]<='9')
for(int i=1;i<=mp[x][y]-'0';i++)
printf("%ds:FIGHT AT (%d,%d)
",pre.t+i+1,x-1,y-1);
}
int main(){
//freopen("in","r",stdin);
while(scanf("%d%d",&N,&M)!=EOF){
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
mp[i][j]=one();
bfs();
if(vis[N][M]==vis[0][0])
puts("God please help our poor hero.");
else{
printf("It takes %d seconds to reach the target position, let me show you the way.
",vis[N][M]);
dfs(N,M);
}
puts("FINISH");
}
return 0;
}
//1010
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=110,MOD=10000;
struct big{
int num[200],len;
big(){
memset(num,0,sizeof(num));
len=1;
}
big friend operator+(const big&A,const big&B){
big C;
C.len=max(A.len,B.len);
for(int i=1;i<=C.len;i++){
C.num[i]+=A.num[i]+B.num[i];
int k=i;
while(C.num[k]>=MOD){
C.num[k+1]+=C.num[k]/MOD;
C.num[k]%=MOD;
k++;
if(k>C.len)
C.len=k;
}
}
return C;
}
big friend operator*(big A,int B){
big C;
C.len=A.len;
for(int i=1;i<=A.len;i++){
C.num[i]+=A.num[i]*B;
int k=i;
while(C.num[k]>=MOD){
C.num[k+1]+=C.num[k]/MOD;
C.num[k]%=MOD;
k++;
if(k>C.len)
C.len=k;
}
}
return C;
}
void print(){
printf("%d",num[len]);
for(int i=len-1;i>=1;i--)
printf("%04d",num[i]);
}
}f[maxn][maxn];
int M,N;
int main(){
//freopen("in","r",stdin);
//freopen("out","w",stdout);
int cas=1;
while(1){
M=read(),N=read();
if(M+N==0)break;
printf("Test #%d:
",cas++);
f[0][0].num[1]=1;
for(int i=1;i<=M;i++)
f[i][0]=f[i-1][0]*(M-i+1);
for(int i=1;i<=M;i++)
for(int j=1;j<=min(i,N);j++)
f[i][j]=f[i][j-1]*(N-j+1)+f[i-1][j]*(M-i+1);
f[M][N].print();
puts("");
}
return 0;
}
//1011
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
int N,M,t1,t2;
int cost[110],b[110];
int lin[110],len;
struct edge{
int y,next;
}e[210];
inline void insert(int xx,int yy){
e[++len].next=lin[xx];
lin[xx]=len;
e[len].y=yy;
}
int f[110][110];
void dfs(int x,int fa){
int need=cost[x]/20;
if(cost[x]%20)
need++;
for(int j=M;j>=need;j--)
f[x][j]=b[x];
for(int i=lin[x];i;i=e[i].next){
if(e[i].y==fa)
continue;
dfs(e[i].y,x);
for(int j=M;j>=need;j--)
for(int k=1;k<=M-j;k++)
f[x][j+k]=max(f[x][j+k],f[x][j]+f[e[i].y][k]);
}
}
int main(){
//freopen("in.txt","r",stdin);
while(1){
N=read(),M=read();
if(N==-1&&M==-1)
break;
len=0;
memset(lin,0,sizeof(lin));
for(int i=1;i<=N;i++)
cost[i]=read(),b[i]=read();
for(int i=1;i<N;i++){
t1=read(),t2=read();
insert(t1,t2),insert(t2,t1);
}
if((!M)||(!N)){
printf("0
");
continue;
}
memset(f,0,sizeof(f));
dfs(1,0);
printf("%d
",f[1][M]);
}
return 0;
}
//1012
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=80;
int N;
char s[maxn];
int main(){
//freopen("in","r",stdin);
for(int _=read();_;_--){
gets(s+1);
N=strlen(s+1);
for(int i=N;i>=1;i--)
printf("%c",s[i]);
puts("");
}
return 0;
}
//1013
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
int N,M;
bool succ;
void dfs(int x,long long a,long long b){
if(x==101||succ)return;
if(N%a||M%b)return;
if(a==N&&b==M){
succ=1;
return;
}
dfs(x+1,a*x,b);
dfs(x+1,a,b*x);
dfs(x+1,a,b);
}
int main(){
//freopen("in","r",stdin);
while(scanf("%d%d",&N,&M)!=EOF){
if(N>M)swap(N,M);
succ=0;
dfs(2,1,M);
if(!succ){
printf("%d
",M);
continue;
}
succ=0;
dfs(2,1,1);
if(succ)printf("%d
",M);
else printf("%d
",N);
}
return 0;
}
//1014
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=210,INF=1<<30;
int N,A,B,a[maxn];
int q[maxn],head,tail;
int vis[maxn];
void bfs(){
for(int i=1;i<=N;i++)
vis[i]=INF;
vis[A]=0;
head=tail=1;
q[head]=A;
for(;head<=tail;head++){
int tmp=q[head]+a[q[head]];
if(tmp<=N&&vis[tmp]>vis[q[head]]+1){
q[++tail]=tmp;
vis[tmp]=vis[q[head]]+1;
}
tmp=q[head]-a[q[head]];
if(tmp>0&&vis[tmp]>vis[q[head]]+1){
q[++tail]=tmp;
vis[tmp]=vis[q[head]]+1;
}
}
if(vis[B]==INF)
puts("-1");
else
printf("%d
",vis[B]);
}
int main(){
//freopen("in","r",stdin);
while(1){
N=read();
if(!N)break;
A=read(),B=read();
for(int i=1;i<=N;i++)
a[i]=read();
bfs();
}
return 0;
}
//1015
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='
')
ch=getchar();
return ch;
}
const int maxn=25;
int A,N,a[maxn];
bool succ,use[maxn];
bool cmp(const int&x,const int&y){
return x>y;
}
void dfs(int x,int sum,int p){
if(x==4){
succ=1;
return;
}
if(succ)return;
if(sum==A){
dfs(x+1,0,0);
return;
}
for(int i=p+1;i<=N;i++)
if(!use[i]&&a[i]+sum<=A){
use[i]=1;
dfs(x,sum+a[i],i);
use[i]=0;
}
}
int main(){
//freopen("in","r",stdin);
for(int _=read();_;_--){
N=read();A=0;
for(int i=1;i<=N;i++)
a[i]=read(),A+=a[i];
if(A%4)
puts("no");
else{
sort(a+1,a+1+N,cmp);
A/=4;succ=0;
dfs(1,0,0);
if(succ)
puts("yes");
else
puts("no");
}
}
return 0;
}