1071 - 赌徒
有n个赌徒打算赌一局。规则是：
每人下一个赌注，赌注为非负整数，且任意两个赌注都不相同。胜者为赌注恰好是其余任意三个人的赌注之和的那个人。如果有多个胜者，我们取赌注最大的那个为最终胜者。
例如，A，B，C，D，E分别下赌注为2、3、5、7、12，最终胜者是E，因为12=2+3+7。
Input
输入包含多组测试数据。每组首先输入一个整数n（1<=n<=1000），表示赌徒的个数。
接下来n行每行输入一个非负整数b（0<=b<32768），表示每个赌徒下的赌注。
当n=0时，输入结束。
Output
对于每组输入，输出最终胜者的赌注，如果没有胜者，则输出no solution。
Examples
Input
5 2 3 5 7 12 5 2 16 64 256 1024 0
Output
12 no solution
Solution C
#include<stdio.h> #include<string.h> #include<stdlib.h> int number[1003]; int word[100000]; void make(int head,int ptail,int mid) { int i,j,k; int *x=(int *)malloc((ptail-head+1)*sizeof(int)); for (i=head,j=mid+1,k=0;i<=mid&&j<=ptail;k++) { if (number[i]<number[j]) x[k]=number[i++]; else x[k]=number[j++]; } while(i<=mid) x[k++]=number[i++]; while(j<=ptail) x[k++]=number[j++]; for (i=head,j=0;j<k;i++,j++) number[i]=x[j]; free(x); } void sort(int head,int ptail) { if (head>=ptail) return; int mid=(head+ptail)/2; sort(head,mid); sort(mid+1,ptail); make(head,ptail,mid); } int main(void) {//freopen("love.txt","r",stdin); int n,i,j; while(scanf("%d",&n)!=EOF) { if (n==0) break; memset(number,0,sizeof(number)); memset(word,0,sizeof(word)); scanf("%d",&number[0]); for (i=1;i<n;i++) { scanf("%d",&number[i]); for (j=i-1;j>=0;j--) { int sum=number[i]+number[j]; word[sum]=1; } } sort(0,n-1); int flag=0; for (i=n-1;i>=0;i--) { for (j=i-1;j>=0;j--) { int sum=number[i]-number[j]; if (word[sum]!=0) { flag=1; printf("%d\n",number[i]); break; } } if (flag==1) break; } if (flag==0) printf("no solution\n"); } return 0; }
Solution C++
#include<cstdio> #include<algorithm> using namespace std; int bs(int a[],int l,int r,int x) { int m; while(l<r) { m=(l+r)>>1; if(a[m]==x) return m; if(a[m]<x) l=m+1; else r=m; } return -1; } int main() { int n,a[1000],i,j,k,bet,p,flag,ans; while(scanf("%d",&n)!=EOF,n) { for(i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); for(flag=0,i=n-1;i>=0;i--) { for(j=0;j<i;j++) { for(k=j+1;k<n;k++) { bet=a[i]-a[j]-a[k]; p=bs(a,k+1,n,bet); if(p!=-1&&p!=i) { ans=i; flag=1; break; } } if(flag) break; } if(flag) break; } if(flag) printf("%d\n",a[ans]); else puts("no solution"); } return 0; }