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

终于也AC了, 超笨的想法

Posted by Tingen at 2005-05-09 22:19:21 on Problem 1787
In Reply To:输出是 1 cents Posted by:breeze at 2004-09-03 21:25:12
#include <stdio.h>

int i1, i2, i3, i4;
int c1, c2, c3, c4;
int p;

bool run()
{
  int sum;

  sum=c1+c2*5+c3*10+c4*25;

  if(p>sum)
    return false;
  if(p==sum)
  {
    i1=c1; i2=c2; i3=c3; i4=c4;
    return true;
  }

  i1=i2=i3=i4=0;

  for(i1=( c1<=p ? c1:p ); i1>=0; i1--)
  {
    i2=i3=i4=0;
    if(p<=i1)
    {
      i1=p;
      return true;
    }
    if((p-i1)%5!=0)
      continue;
    for(i2=( c2<=(p-i1)/5 ? c2:(p-i1)/5 ); i2>=0; i2--)
    {
      i3=i4=0;

      if(p-i1-i2*5==0)
         return true;
      if(p-i1-i2*5<0)
         continue;
      if( (p-i1-i2*5)%5!=0)
         continue;
      for(i3=( c3<=(p-i1-i2*5)/10? c3:(p-i1-i2*5)/10 ); i3>=0;  i3--)
      {
        i4=0;

        if(p-i1-i2*5-i3*10==0)
          return true;
        if(p-i1-i2*5-i3*10<0)
          continue;

        if( (p-i1-i2*5-i3*10)%25!=0)
          continue;
        for(i4=( c4<=(p-i1-i2*5-i3*10)/25? c4:(p-i1-i2*5-i3*10)/25 ); i4>=0; i4--)
        {
          if(p-i1-i2*5-i3*10-i4*25==0)
            return true;

          if(p-i1-i2*5-i3*10-i4*25<0)
            return false;
        }
      }
    }
  }
  return false;
}

int main()
{
  bool flag;
 // freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);

  scanf("%d %d %d %d %d", &p, &c1, &c2, &c3, &c4);
  while(!(p==0&&c1==0&&c2==0&&c3==0&&c4==0))
  {
    flag=run();
    while(c3-i3>=3)
    {
      if(i2>=1 && i4>=1)
      {
        i3+=3;
        i2--;
        i4--;
      }
      else
        break;
    }
    if(flag)
    {
      printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", i1, i2, i3, i4);
    }
    else
    {
      printf("Charlie cannot buy coffee.\n");
    }
    scanf("%d %d %d %d %d", &p, &c1, &c2, &c3, &c4);
  }
}

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