## 10023 - Square Root

Moderator: Board moderators

### Re: 10023 - Square Root

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)
Bruno
New poster

Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

### Re: 10023 - Square Root

Edit; Posted in Java forum.Sorry for posting here.
mukeshtiwari
Learning poster

Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

### Re: 10023 - Square Root

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;}`
moron_venom
New poster

Posts: 1
Joined: Sat Mar 12, 2011 11:59 am

Previous