4558208_ac_172ms_272k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 121 行

#include<iostream>
using namespace std;
int m[100],un[100],bestun[100],total,best[5],typen,bestnum,bestmax,tie,maxnum;
void copyun()
{
  int i,j=1;
  for(i=1;i<=m[0];i++)
  if(un[i]!=0){bestun[i]=un[i];}
}
int comparison()
{
  int i,j=0,k=0,max=0;
  for(i=1;i<=m[0];i++)
  if(un[i]!=0){k++;j=j+un[i];}
  for(i=1;i<=m[0];i++)if(un[i]!=0&&m[i]>max)max=m[i];
  if(k>typen){typen=k;bestmax=max;bestnum=j;tie=0;copyun();return 1;} 
  else if(k==typen)
    {   
      if(j<bestnum){bestnum=j;bestmax=max;tie=0;copyun();return 1;}
      else if(j==bestnum)
      {
          if(max>bestmax){bestmax=max;tie=0;copyun();return 1;}
          else if(max==bestmax)
          {
              tie=0;
              for(i=1;i<=m[0];i++)
              { 
                  if(un[i]!=bestun[i])tie=1; 
              }    
              return 0;
          }
      }
    }    
  return 0;
}
void copynum()
{
  int i,j,k=0;
  for(i=0;i<5;i++)best[i]=0;
  for(i=1;i<=m[0];i++)
  {
    if (un[i]!=0)
    for(j=0;j<un[i];j++)
    {best[k]=m[i];k++;}
  }  
}
void output()
{
  int i,k=0;
  while(best[k]!=0)k++;
  cout<<" ("<<typen<<"):";
  if(tie==0)
  {
    for(i=0;i<k;i++)cout<<' '<<best[i];
    cout<<endl;
  }
  else if(tie==1)cout<<" tie"<<endl;     
}
void stamp(int n,int current)
{
  int i,j; 
  for(i=current;i<=m[0];i++)
  {
    if(n-m[i]>0&&total<4)
    {current=i;n=n-m[i];total++;un[i]++;stamp(n,current);n=n+m[i];un[i]--;total--;}
    if(n-m[i]==0&&total<4)
    {
      un[i]++;total++;
        if(comparison())
        copynum();
      total--;un[i]--; 
    }      
  }     
}
int judge(int b)
{
    if(b<=4*maxnum)return 1;
    else cout<<" ---- none"<<endl;
    return 0;
}
void countmax()
{
  int i;
  for(i=1;i<=m[0];i++)
  if (m[i]>maxnum)maxnum=m[i];
}
void initnum()
{
    int i;
    for(i=1;i<=m[0];i++){un[i]=0;bestun[i]=0;}
    total=0;typen=0;bestnum=0;tie=0;bestmax=0,maxnum=0;
}
int main()
{
  int a,b;
  char s[100];  
  while(cin>>a)
  {
    m[0]=0;m[1]=a;
    while(a!=0){m[0]++;m[m[0]]=a;cin>>a;}
    cin>>b;
    while(b!=0)
    {
      cout<<b;
      initnum();
      countmax();
      if(judge(b))
      {
          stamp(b,1);  
          if (typen!=0)output();
          else cout<<" ---- none"<<endl;
      }    
      cin>>b;
    }      
  }    
  return 0;
}