Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:possibly a little too late...

Posted by hasan83 at 2007-04-10 18:24:50 on Problem 1010
In Reply To:possibly a little too late... Posted by:frkstyc at 2007-04-09 20:57:49
This is my new code and its gave me WA again!!!

#include<iostream>
using namespace std;

void print();
void replace(int cur[],int index,int noof);
void gene(int cur[],int curt[],int index,int noof);

int n,m,r,flag,best[4],stamps[25],best_index,best_noof,tie;

int main()
{
    while(!cin.eof())
    {
       cin>>r;              
       if(r!=0&&!flag)
       {
          stamps[m++]=r;
          continue;            
       }
       if(r!=0&&flag)
       {
          n=r;
          int cur[4]={0},curt[25]={0},index=0,noof=0;
          gene(cur,curt,index,noof);
          print();
          for(int i=0;i<4;i++){best[i]=0;}
          best_noof=0,best_index=0,tie=0;
          continue;           
       }
       if(!flag)
       {
           for(int i=0;i<m-1;i++)
           {
              for(int j=0;j<m-1;j++)
              {
                 if(stamps[j]>stamps[j+1])
                 {
                    r=stamps[j];
                    stamps[j]=stamps[j+1];
                    stamps[j+1]=r;                      
                 }     
              }     
           }
       }
       if(flag)
       {
           m=0;    
       }
       flag=!flag;          
    }    
    
    return 0;
}

void gene(int cur[],int curt[],int index,int noof)
{
     if(n==0)
     {
        // process the solution //
        //for(int i=0;i<index;i++)cout<<stamps[cur[i]]<<" ";cout<<endl;    
        //for(int i=0;i<index;i++)cout<<cur[i]+1<<" ";cout<<endl;
        //cout<<noof<<endl;
        if(noof>best_noof)
        {
            replace(cur,index,noof);return;             
        }
        else
        {
            if(noof==best_noof)
            {
                if(index<best_index)
                {
                    replace(cur,index,noof);return;                
                }
                else
                {
                    if(index==best_index)
                    {
                         if(stamps[cur[index-1]]>stamps[best[best_index-1]])
                         {
                             replace(cur,index,noof);return;
                         }
                         else
                         {
                             if(stamps[cur[index-1]]==stamps[best[best_index-1]])
                             {
                                 tie=1;return;                                                
                             }
                         }                
                    }
                }               
            }
        }
        return;
     }
     if(index<4)
     {
        for(int i=0;i<m&&stamps[i]<=n;i++)
        {
           if(index==0||i>=cur[index-1])     
           {
               noof+=!curt[i]++;
               cur[index]=i;
               n-=stamps[i];
               gene(cur,curt,index+1,noof);
               noof-=!(--curt[i]);     
               n+=stamps[i];
           }
        }        
     }
}

void replace(int cur[],int index,int noof)
{
     for(int i=0;i<index;i++)best[i]=cur[i];
     best_index=index;
     best_noof=noof;
     tie=0;
}

void print()
{
     if(!best_noof)
     {
        cout<<n<<" ---- none"<<endl;return;        
     }
     if(tie)
     {
        cout<<n<<" ("<<best_noof<<"): tie"<<endl;return;    
     }
     cout<<n<<" ("<<best_noof<<"): ";
     for(int i=0;i<best_index;i++)
     {
        cout<<stamps[best[i]]<<" ";    
     }
     cout<<endl;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator