10023 - Square Root

[Bruno]

Following little joey algorithm (Pells equations, etc..) I got a very fast result! I tryed all the test cases from mukeshtiwari and all answers are equal! But I am getting WA

EDIT---

Got accpeted finally!
The problem was that in the last result I was printing a blank line too . Resuming, for EVERY number output you put a \n in the end, so the last number must have a \n too, between outputs you must print a \n (blank line)

[mukeshtiwari]

Edit; Posted in Java forum.Sorry for posting here.

[moron_venom]

clould anyone help me to find the bug?

for all of test cases i tried, there are all correct

but the online judge always display runtime error ,but i can't find out where i straddle the boundary of array....

or maybe there's another mistake?

I use Square Root Extraction Method... i appreciate your help...

Code: Select all


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int  cal[1100] ,rev_data[1100] ,guess[1100] ,divide_num[1100] ,answer[1100];
int rest[1100];
int rev_mul_test(int *guess ,int current_guess ,int *cal ,int * divide_num,int bottom ,int base ,int top);
int main(int argc, char *argv[])
{
  int i,j  ,casenum ,digit_num ,d_num ,current_guess ,k;
  char char_data;
  int *tmp;
  freopen("test.txt", "r", stdin);
  freopen("dataout.txt", "w", stdout);
  scanf("%d",&casenum);
  for(i=0;i<casenum;i++){
  digit_num = 0;
     while(!isdigit(char_data)){
     scanf("%c",&char_data);
     }
     rev_data[digit_num] = char_data -'0';
     digit_num++;
     while(scanf("%c",&char_data)!=EOF && isdigit(char_data)){
     rev_data[digit_num] = char_data -'0';
     digit_num++;
     }
     d_num = (digit_num+1)/2;
     int top = 0 ,base=0 ,ans_num=0;
     for(j=0;j<d_num;j++){
        if(!j) guess[0] = 0;
     
        if(digit_num%2 && !j){
        divide_num[0] = rev_data[0];
        top++;
        }
        else{
        divide_num[top] = rev_data[top];
        top++;
        divide_num[top] = rev_data[top];
        top++;
        }

        for(current_guess=0;current_guess<10;current_guess++){
        guess[j+1] = current_guess;
           if(!rev_mul_test(guess ,current_guess ,cal ,divide_num ,j+1 ,base ,top)){
           break; 
           }
        }
        guess[j+1] = current_guess-1;   
        rev_mul_test(guess ,current_guess-1 ,cal ,divide_num ,j+1 ,base ,top);   
        answer[j] = current_guess-1;
        ans_num++;
        int pre_allzero=1;
        for(k=base;k<top;k++){
        /*   if(rest[k]) pre_allzero = 0;         
           if(pre_allzero && !rest[k]) base++;*/
           
        divide_num[k] = rest[k];
        }
        int carry = 0,t;       
        for(k=j+1;k>=0;k--){
           if(k==j+1){
           t = (guess[k] + current_guess-1 +carry);
           guess[k] = t % 10;
           carry = t / 10;
           }
           else{
           t = (guess[k] + carry);
           guess[k] = t % 10;
           carry = t / 10;
           }
        }
     }
     for(j=0;j<d_num;j++){
     printf("%d",answer[j]);
     }
     if(i!=casenum-1)
     printf("\n\n");
     else
     printf("\n");
     
  }

}
int rev_mul_test(int *guess ,int current_guess ,int *cal ,int * divide_num,int bottom ,int base ,int top){
  int i,j,carry,t,effect_digit ,stop=0;
  if(bottom==0 && top==0 && current_guess>3)return 0;
  if(!guess[0]) stop=1;
 
  for(i=base;i<top+1;i++) cal[i]=0;

  effect_digit=0;
  carry = 0;
  for(i=bottom;i>=stop;i--){
     t = guess[i] * current_guess + carry;
     cal[top-bottom+i-1] = t % 10;
     carry= t / 10;
       if(current_guess)
       effect_digit++;
  }
    if(carry>0 && top-bottom+i-1 < 0) return 0;
  if(carry>0){
  cal[top-bottom+i-1] = carry;
  effect_digit++;
  }
  if(effect_digit > top-base)return 0;
 
  carry = 0;
  for (i=top-1;i>=base;i--){
  rest[i] = divide_num[i] - cal[i] + carry;
     if (rest[i] < 0) {
     rest[i] = rest[i] + 10;
     carry = -1;
     }
     else
     carry = 0;
  }
  if(carry < 0)return 0;
  else return 1;

}