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

请前辈们指教一下,样例过了,但我的程序总是 wrong answer。

Posted by standy at 2009-04-22 22:53:41 on Problem 1001
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <math.h>

using namespace std;

int f[5][160],ans[160];
int cnt[5],cans;
int s[160];
int N,dot;

void multip( int a[], int La, int b[], int Lb) 
{
    memset(s,0,sizeof(s));
    int i,j;
    for(i=0;i<La;i++)
      for(j=0;j<Lb;j++)
      {
         s[i+j+1] += (s[i+j]+a[i]*b[j])/10 ; 
         s[i+j] = (s[i+j]+a[i]*b[j])%10;               
      }
}

int main()   //pku1001
{
     char ss[10];
     int i,j,k,H; 
   while(scanf("%s %d",ss,&N)==2)
     {
          memset(cnt,0,sizeof(cnt));
          memset(f,0,sizeof(f));
         
            int L=strlen(ss);        
          for(i=L-1;i>0;i--)
            if(ss[i] > '0' && ss[i] <= '9')   
                break;
           for(k=0;k<L;k++)
            if(ss[k] == '.' ) 
                break;
          dot = (i-k)*N ; 
          for(j=0;j<L;j++)
            if(ss[j] != '0' && ss[j] != '\0')
                break;
          for( ; i>=j;i--)
             if(ss[i] != '.')   f[0][cnt[0]++] = ss[i]-'0';
     
          for(H=4;H>=0;H--)
            if(N & (1<<H))   break ;//找N的二进制中不为0的最高位。
           
          for(k=1;k<=H;k++)
           {
                 multip( f[k-1], cnt[k-1], f[k-1], cnt[k-1] ); 
                 if(s[cnt[k-1]*2-1] == 0)
                         cnt[k] = 2*cnt[k-1]-1;
                 else    cnt[k] = 2*cnt[k-1]; 
                 for(i=0;i<cnt[k];i++)
                     f[k][i] = s[i] ;
           }
         for(i=0;i<cnt[H];i++)
               ans[i] = f[H][i] ;
               cans = cnt[H] ;
          for(k=H-1;k>=0;k--)
            if(N & (1<<k))
              {
                   multip(ans, cans, f[k], cnt[k]);
                   if(s[cans+cnt[k]-1] == 0)
                           cans = cans+cnt[k]-1;
                   else    cans = cans+cnt[k] ;
                   for(i=0;i<cans;i++)
                       ans[i] = s[i] ;
              }
         
          
          if(N == 0)
             printf("1\n");
          
          else if(cnt[0]==0)
             printf("0\n");
          
          else if(dot == -N)
          {
             for(i=cans-1;i>=0;i--)
                printf("%d",ans[i]);
             printf("\n");
          }
          
          else  if(dot == -2*N)
          {
                for(i=cans-1;i>=0;i--)
                    printf("%d",ans[i]);
                for(i=0;i<N;i++)
                    putchar('0');
                    printf("\n");  
          }
          
          else if(dot < cans)
            {   
              for(i=cans-1; i>=dot;i--)
                 printf("%d",ans[i]);
                 putchar('.');
              for( ; i>=0;i--)
                 printf("%d",ans[i]);
                 printf("\n"); 
            }
          
          else
          {
                 printf(".");
              for(i=cans;i<dot;i++)
                 putchar('0');
              for(i=cans-1;i>=0;i--)
                 printf("%d",ans[i]);
                 printf("\n");
                 
          } 
      //      memset(ss,0,sizeof(ss));       
     }
                 
    return 0;
}

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