ZJU 1101 解题报告

Gamblers

Time Limit: 1 Seconds Memory Limit: 32768 KB

A group of n gamblers decide to play a game:

At the beginning of the game each of them will cover up his wager on the table and the assitant must make sure that there are no two gamblers have put the same amount. If one has no money left, one may borrow some chips and his wager amount is considered to be negative. Assume that they all bet integer amount of money.

Then when they unveil their wagers, the winner is the one who's bet is exactly the same as the sum of that of 3 other gamblers. If there are more than one winners, the one with the largest bet wins.

For example, suppose Tom, Bill, John, Roger and Bush bet $2, $3, $5, $7 and $12, respectively. Then the winner is Bush with $12 since $2 + $3 + $7 = $12 and it's the largest bet.

Input

Wagers of several groups of gamblers, each consisting of a line containing an integer 1 <= n <= 1000 indicating the number of gamblers in a group, followed by their amount of wagers, one per line. Each wager is a distinct integer between -536870912 and +536870911 inclusive. The last line of input contains 0.

Output

For each group, a single line containing the wager amount of the winner, or a single line containing "no solution".

Sample Input

5
2 
3 
5 
7 
12
5
2 
16 
64 
256 
1024
0

Output for Sample Input

12
no solution

题目的意思是说,给出一系列的数,找出四个数使a+b+c=d成立,如果有多个符合的答案,输出最大的d,如果没有输出no solution

挺简单的题目,第一种解法是直接暴力搜索,数据量不大不会超时,不过效率不是很高.第二种解法是枚举每个可能的d和b,然后通过两头缩进的办法找出a和c,效率比较高,0ms解决!

CODE1

//暴搜,320ms AC
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
 
int main()
{
  int D[1010];
  int i,j,k,m,n;
  while(scanf("%d",&n),n)
    {
      for(i=0;i<n;++i)
        scanf("%d",&D[i]);
      sort(D,D+n);
      bool T=false;
      for(i=n-1;i>=0;--i)
        {
          for(j=n-1;j>=2;--j)
            {
              if(j==i) continue;
              for(k=j-1;k>=1;--k)
                {
                  if(k==i) continue;
                  for(m=k-1;m>=0;--m)
                    {
                      if(m==i) continue;
                      if(D[m]+D[k]+D[j]==D[i])
                        {
                          printf("%d\n",D[i]);
                          T=true;
                          goto out;
                        }
                    }
                }
            }
        }
out:
      if(T==false) printf("no solution\n");
    }
  return 0;
}

CODE2

//枚举+两头缩进优化,0ms AC
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
 
int main()
{
  int D[1010];
  int i,j,k,m,n;
  while(scanf("%d",&n),n)
    {
      for(i=0;i<n;++i)
        scanf("%d",&D[i]);
      sort(D,D+n);
      bool T=false;
      int q,p,tmp1,tmp2;
      for(i=n-1;i>=0;--i)
        {
          for(j=n-1;j>=0;--j)
            {
              if(j==i) continue;
              tmp1=D[i]-D[j];
              p=0;q=n-1;
              tmp2=D[p]+D[q];
              while(p<q)
                {
                  if(tmp2>tmp1)
                    --q;
                  else if(tmp2<tmp1)
                    ++p;
                  else
                    {
                      if(p==i||p==j) ++p;
                      else if(q==i||q==j) --q;
                      else
                        {
                          printf("%d\n",D[i]);
                          T=true;
                          goto out;
                        }
                    }
                  tmp2=D[p]+D[q];
                }
            }
        }
out:
      if(T==false) printf("no solution\n");
    }
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:
发表评论?

0 条评论。

发表评论

注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>