10023 - Square root

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 10023 - Square Root

Post by sazzadcsedu » Wed Jan 21, 2009 11:23 am

whats wrong with my code???
why WA????

Code: Select all


              #include<stdio.h>
          #include<math.h> 
 
             int  main()

			   {

				   long double y;
				   int ncase;

				    scanf("%d",&ncase);
                     

					while(ncase>0)
					{

			
				   scanf("\n\n%Lf",&y);
				   
				   printf("%.0Lf",sqrtl(y));
				    
				

				     if(ncase>1)
						 printf("\n\n");
		
				      ncase--;
					}

					return 0;

			   }
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10023 - Square Root

Post by mf » Wed Jan 21, 2009 1:22 pm

Have you even read the last few messages in this thread?

Why do you think your code should get AC? long double != infinite precision arithmetic, go learn how floating-point numbers are really represented on a computer.

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Re: 10023 - Square Root

Post by Ron » Wed Jan 21, 2009 5:38 pm

hi mf sir,
could you please tell me the mistake in my above code.
I used BigInt. Just see my approach and tell me mistake ( if it is ).
Thanking You...!!!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10023 - Square Root

Post by mf » Wed Jan 21, 2009 5:47 pm

When I tried to run your code on my computer, it doesn't work for small, two-digit inputs - the very first such test case runs ok, but for subsequent test cases it just prints "0". And also you're not reading the input properly - the test cases are separated by a blank line.

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Runtime Error

Post by WingletE » Thu Jul 02, 2009 10:06 am

My code runs okay on my computer and I really don't know why it got an RTE.
I've tried to enlarge the array of my BigInt to 2500, and checked that no divide-by-zero will possibly happen.
I think it's not the problem of array-index-out-of-bound because that should have caused a WA on my computer.
I'd be grateful if someone's willing to give me some suggestions or take a look at my code (tell me and I'll post it here or send it to you, because I think there's been too much code posted here).
Thanks in advance! =)

noor_aub
New poster
Posts: 26
Joined: Sat Aug 22, 2009 12:16 pm

Re: 10023 - Square Root

Post by noor_aub » Tue Aug 25, 2009 11:33 am

This code I get wrong answer. Why

Code: Select all


Last edited by noor_aub on Sun Aug 15, 2010 7:41 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10023 - Square Root

Post by mf » Tue Aug 25, 2009 12:44 pm

This code I get wrong answer. Why
Why not?

Read the last few replies posted in this thread.

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

Re: 10023 - Square Root

Post by Bruno » Thu Nov 05, 2009 3:09 pm

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 :o

EDIT---

Got accpeted finally! :P
The problem was that in the last result I was printing a blank line too :evil: . 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
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Re: 10023 - Square Root

Post by mukeshtiwari » Sun May 16, 2010 7:34 pm

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

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

Problem 10023 Square Root

Post by mukeshtiwari » Sun May 16, 2010 8:46 pm

Could some one please tell me why i am getting Run Time Error for this code.
Thank You

Code: Select all

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

//package uvaproblem_10023;
import java.io.*;
import java.math.BigInteger;

/**
 *
 * @author user
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       try
       {
         BufferedReader stdin= new BufferedReader(new InputStreamReader(System.in));
         String s_1=stdin.readLine();
         stdin.readLine();//for blank line
         int n=Integer.parseInt(s_1);
         boolean  f=false;
         for(int i=0;i<n;i++)
         {
            if(f)System.out.println();
            f=true;
            String    s_2=stdin.readLine();
            BigInteger x=new BigInteger(s_2);
            BigInteger lo=BigInteger.ZERO,hi=x,mid;
            while(lo.compareTo(hi)<0)
            {
               mid=(lo.add(hi)).divide(new BigInteger("2"));
               BigInteger res=mid.pow(2);
               if(res.compareTo(x)<0) lo=mid.add(new BigInteger("1"));
               else hi=mid;

            }
            mid=(lo.add(hi)).divide(new BigInteger("2"));
            //System.out.println(lo+" "+mid+" "+hi+" "+mid.pow(2));
            System.out.println(mid);
         }

       }catch (NumberFormatException e){}
       catch(IOException e){}
    }

}


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

Re: Problem 10023 Square Root

Post by mukeshtiwari » Fri Oct 01, 2010 9:45 pm

Today i tried again with try and catch block but no luck.I am still getting RTE. I guess this community not active as it was initially when i joined this site[around 2006-07].
Thank you

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

Re: 10023 - Square Root

Post by moron_venom » Sat Mar 12, 2011 12:09 pm

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;

}


ojha
New poster
Posts: 7
Joined: Wed May 22, 2013 9:07 am

Re: 10023 - Square Root

Post by ojha » Sun May 26, 2013 11:02 pm

Is there any better logic than Newton's method ?? I'm getting Time Limit here:

Code: Select all

import java.math.BigInteger;
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner scanf = new Scanner(System.in);
		int time;
		time = scanf.nextInt();
		System.out.println("");
		
		for(int i = 0; i<time; i++){
			BigInteger input = scanf.nextBigInteger();
			if(i > 0)
				System.out.println("");
			BigInteger previous = input;
			BigInteger distance, post, Two = BigInteger.valueOf(2), Negative = BigInteger.valueOf(-1);
			if(input.equals(BigInteger.ZERO)){
				System.out.println("0");
				continue;
			}
			while(true){
		        post = input.divide(previous);
		        post = post.add(previous);
		        post = post.divide(Two);
		        distance = post.subtract(previous);
		        if(distance.equals(BigInteger.ONE)){
		            
		            System.out.println(previous);
		            break;
		        }
		        int d = distance.compareTo(BigInteger.ZERO);
		        if(d < 0)
		            distance = distance.multiply(Negative);
		        else if(distance.equals(BigInteger.ZERO)){
		        	
		            System.out.println(post);
		            break;
		        }
		        previous = post;
		    }
		}

	}

}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10023 - Square Root

Post by brianfry713 » Wed May 29, 2013 1:11 am

Code: Select all

initialize temp to a guess of sqrt(Y)
while(1) {
  X = (temp + (Y / temp)) / 2;
  if(temp == X)
    break;
  temp = X;
}
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10023 - Square Root

Post by lighted » Mon Jun 30, 2014 3:54 pm

Is it possible to get acc using methods different from Pells and Newtons method?

I used square method which i learned at scholl and got TLE. I also got TLE using my own bigint + binary search

Code: Select all

removed, after acc.. 
I got acc with runtime 1.509. I found my bug. It was problem with reading number.

Then i changed base from 10 to 10000 + avoided all div and mod operations (by using some memory + precalc) + binary search for finding roots next digit (0..9) and some other optimizations and got acc with runtime 0.472.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 100 (10000-10099)”