10023 - Square root

[LithiumDex]

I recently solved 10023 (sqrt) using a method described in the forms, and my bigInt class used base 10 digits, in a time of about 5 seconds -- It's seems pretty obvious too me, that if I had used a higher base (i.e. base 10^9) -- it would have greatly increased the speed of addition and subtraction, although it would have also made multiplication by 10 or 100 slower.. Also conversion to/from base 10^9 would be more difficult.... Would anyone like to comment on this?

[misof]

I don't see a reason why it should make multiplication significantly slower.

[20717TZ]

Thanks. It's works. I also improved some functions, making it more efficient.

memset is useful!

/*
# Problem Verdict Language Run Time Submission Date
6236651 Square root Accepted C++ 1.490 2008-02-16 08:33:31
*/

[20717TZ]

I'm sorry. I forgot to change this line:

Code: Select all

 FILE* fp=fopen("Input.txt","r"); 

To:

Code: Select all

 FILE* fp=stdin; 

Everytime I need to make this change before submission.

However, I'm now using this:

Code: Select all

#ifndef ONLINE_JUDGE
	freopen("Input.txt", "r", stdin);
#endif

[newton]

i cant figure out any reason of WA.
has judge changed the input limit?

Code: Select all

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
int main(){
	int n;
	long double Num;
	scanf("%ld",&n);
	while(n--){
		scanf("%Lf",&Num);
		printf("%.0Lf\n",sqrtl(Num));
	}
	return 0;
}

[subzero]

Hi,
I'm newbie in Java...
since the BigInteger class is needed for this problem I wanted to use JAVA, but I'm getting RTE.. and I don't know why...please, give mea hand.

I'm using jdk 1.6 on Fedora 9 and everything works fine here

Thanks for reading

Code: Select all

import java.io.*;
import java.util.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		Integer t,i;
		BigInteger x,xant,error,n;
		t = in.nextInt();
		for ( ;t>0;t--){
			n=in.nextBigInteger();
			x=n.divide(new BigInteger("2"));
			do{
				xant=x;
				x=x.subtract((func(n,x)).divide(dfunc(x)));
				//error=(x.subtract(xant)).divide(x);
			}while (xant.compareTo(x)!=0);
			while ((x.multiply(x)).compareTo(n)==1){
				x=x.subtract(new BigInteger("1"));
			}
			System.out.println(x);
		}
		
		in.close();
        }
	public static BigInteger func(BigInteger n,BigInteger x){
		return n.subtract(x.multiply(x));
	}
	public static BigInteger dfunc(BigInteger x){
		return x.multiply(new BigInteger("-2"));
	}
}

[andmej]

Try changing

Code: Select all

public class Main {

for

Code: Select all

class Main {

I'm not sure if that is your problem, though.

[subzero]

I have changed as you say...but still RTE..with time 0.0000

[andmej]

Try this input:

Code: Select all

1
1

[subzero]

Thanks!! andmej, that was de error...

now it's time to face the TLE I got

[pok]

what is the problem in this code ?
i got WA in this problem..

#include<stdio.h>
#include<math.h>

int main()
{
long int n,i;

scanf("%ld",&n);

for(i=0;i<n;i++)
{
printf("\n");

long double x,y;

scanf("%Lf",&y);

printf("\n");

x=sqrt(y);

printf("%.0Lf\n",x);
}

return 0;
}

[mf]

long double is not precise enough for this problem.
It has only 64 bits of precision, while you actually need log_2(10^1000) ~= 3321 bits for this problem!

[newton]

But some of my friends had got Acc
think judge has fixed it.

[mf]

A few years ago a solution like yours was indeed accepted by the judge, because it had a very weak input file.

But now that's finally fixed, and you have no easy way to avoid coding bignums here.

[Ron]

I submitted around 50 submissions for this problem .
I am not able to get AC.
( FRUSTRATED NOW )
Why im getting WA ?
I checked by Random generator inputs of length greater than 100 also.

Code: Select all

#include <time.h>
#include <algorithm> 
#include <iostream>  
#include <sstream> 
#include <string> 
#include <vector> 
#include <queue> 
#include <stack>
#include <set> 
#include <map> 
#include <cstdio> 
#include <cstdlib> 
#include <cctype> 
#include <cmath> 
#include <cassert>
using namespace std;
typedef long long int LL;
#define ALL(s) (s).begin(),(s).end()
#define R(i,m,n)	for(i=m;i>=n;i--)
#define FF(i,m,n)	for(i=m;i<n;i++)
#define F(i,n)	FF(i,0,n)
#define VI vector<int>
#define PB push_back
void _reverse(char s[]){
	int i=0,l=strlen(s)-1;
	char ch;
	while(i<l){
		ch=s[i];
		s[i]=s[l];
		s[l]=ch;
		i++;l--;
	}
}

char* to_str(int x){
	char* s;
	int i=0;
	while(x){
		s[i++]=(char)(x%10+'0');
		x/=10;
	}
	_reverse(s);
	return s;
}

int to_int(char *s){
	int i,l=strlen(s);
	int k=0;
	F(i,l)
		k=10*k+(s[i]-'0');
	return k;
}

const int MAX = 1100;
class HugeInt {
public:

	// vars
	char number[MAX];
	int length;

	// constructors
	HugeInt() {
		memset(number,0,sizeof(number));
		length = 1;
	}

	HugeInt(int n) {
		*this = n;
	} 

	// operators
	// takes 'r' as right number and writes result to 'this'
	// *veryfied*
	HugeInt* operator= (const HugeInt* r) { 
		memset(number,0,sizeof(number));
		strcpy(number,r->number);
		length = r->length;
		return this;
	}

	// *veryfied*
	HugeInt* operator= (const int r) {
		memset(number,0,sizeof(number));
		sprintf(number,"%d",r);
		length = strlen(number);
		for (int i = 0; i < (length >> 1); i++) {
			char c = number[i];
			number[i] = number[length-i-1];
			number[length-i-1] = c;
		}
		for (int j = 0; j < length; j++)
			number[j] -= '0';
		return this;
	}

	// *veryfied*
	const HugeInt operator+ (const HugeInt& r) {
		int n = max(length,r.length), carry = 0, k, i;
		HugeInt theNew;
		for (i = 0; i < n || carry; i++) {
			k = number[i] + r.number[i] + carry;
			theNew.number[i] = k % 10;
			carry = k / 10;
		}
		theNew.length = i;
		return theNew;
	}

	// slightly veryfied
	void operator+= (const HugeInt& r) {
		*this = *this + r;
	}

	const HugeInt operator- (const HugeInt& r) {
		int n = length, b = 0, k, i;
		HugeInt theNew;
		for (i = 0; i < n ; i++) {
			if(number[i]-r.number[i]-b<0){
				theNew.number[i] = 10 + number[i] - r.number[i] -b;
				b=1;
			}
			else{
				theNew.number[i] = number[i] - r.number[i] -b;
				b=0;
			}
		}
		for (; i < n ||b; i++) {
			if(number[i]-b<0)
				theNew.number[i] = 10 + number[i] -b;
			else{
				theNew.number[i] = number[i] -b;
				b=0;
			}
		}
		theNew.length = i;
		truncate(theNew);
		return theNew;
	}

	// slightly veryfied
	void operator-= (const HugeInt& r) {
		*this = *this - r;
	}

	// *slightly veryfied*
	const HugeInt operator* (const int r) {
		int i, k, carry = 0;
		HugeInt theNew;
		for (i = 0; i < length || carry; i++) {
			k = number[i] * r + carry;
			theNew.number[i] = k % 10;
			carry = k / 10;
		}
		theNew.length = i;
		return theNew;
	}

	// *slightly veryfied*
	void operator*= (const int r) {
		*this = *this * r;
		//return this;
	}

	// shifts number left by 'shift' positions
	// useful when multiplying two HugeInt's
	HugeInt operator<< (const int shift) {
		int i;
		HugeInt theNew;
		// don't shift if number is 0 and there is no number
		//if (length == 0 || length == 1 && number[0] == 0) return;
		for (i = length - 1; i >= 0; i--)
			theNew.number[i + shift] = number[i];
		for (i = 0; i < shift; i++)
			theNew.number[i] = 0;
		theNew.length = length + shift;
		return theNew;
	}

	HugeInt operator* (HugeInt& r) {
		int i;
		HugeInt theNew = 0;
		for (i = 0; i < length; i++)
			theNew += (r << i) * number[i];
		truncate(theNew);
		return theNew;
	}

	HugeInt operator*= (HugeInt& r) {
		*this = *this * r;
		return *this;
	}

	int operator % (int r) {
		int n = 0;
		for (int i = length - 1; i >= 0; i--)
			n = (n * 10 + number[i]) % r;
		return n;
	}

	int operator %= (int r) {
		return (*this % r);
	}

	HugeInt operator/ (int r) {
		HugeInt I = 0;
		int n = 0;
		int j = 0;
		for (int i = length - 1; i >= 0 || n >= r; i--) {
			n = (n * 10 + number[i]);
			I.number[j++] = n / r;
			n %= r;
		}

		// reverse string
		for (int i = 0; i < j / 2; i++)
			swap(I.number[i],I.number[j-i-1]);
		I.length = j;
		truncate(I);

		return I;
	}

	HugeInt operator /= (int r) {
		return (*this / r);
	}

	// functions
	// *veryfied*
	void print() {
		for (int i = length - 1; i >= 0; i--)
			putchar(number[i] + '0');
	}

	void truncate(HugeInt& n) {
		for (int i = n.length - 1; i >= 0 && n.number[i] == 0; i--)
			n.length--;
		if (n.length == 0) {
			n.number[0] = 0;
			n.length = 1;
		}
	}

	HugeInt power(int p) {
		HugeInt theNew = 1;
		for (int i = 0; i < p; i++)
			theNew *= *this;
		return theNew;
	}

	bool operator<(const HugeInt& rhs) {
		if (this->length != rhs.length)
			return this->length < rhs.length;
		for (int i = this->length-1; i >=0; i--)
			if (this->number[i] != rhs.number[i])
				return this->number[i] < rhs.number[i];
		return true;
	}

	bool isnull() {
		if (length == 1 && number[0] == 0) {
			return true;
		}
		return false;
	}
	
};

int main() {
	int t,i,j,l,k,n;
	HugeInt sm,ml,tmp,tmp2;
	char ans[1000],s[1100],f[2];
	scanf("%d",&t);
	gets(f);
	gets(f);
	while(t--){
		gets(s);
		l=strlen(s);
		if(l<2){
			if(s[0]=='1')	printf("1\n");
			else if(s[0]=='4')	printf("2\n");
			else if(s[0]=='9')	printf("3\n");
			else{
				k=s[0]-'0';
				printf("%.0lf\n",sqrt(1.0*k));
			}
			continue;
		}
		j=0;
		sm = 0;
		if(l % 2){
			k=s[0]-'0';
			ml=k;
			i=1;
		}
		else{
			k=10*(s[0]-'0')+(s[1]-'0');
			ml=k;
			i=2;
		}
		while(i<l){
			k=1;
			sm*=10;
			tmp=sm+k;
			tmp2=tmp*k;
			while( tmp2 < ml){
				k++;
				tmp=sm+k;
				tmp2=tmp*k;
			}
			k--;
			ans[j++]=(char)(k+'0');
			tmp=sm+k;
			tmp*=k;
			ml -= tmp;
			ml*=100;
			n=10*(s[i]-'0')+(s[i+1]-'0');
			ml += n;
			i+=2;
			sm+=2*k;
		}
		k=1;
		tmp=k;
		sm*=10;
		while( tmp2 < ml){
			k++;
			tmp=k;
			tmp2=sm+tmp;
			tmp2*=k;
		}
		k--;
		ans[j++]=(char)(k+'0');
		ans[j]='\0';
		puts(ans);
		if(t)	printf("\n");
	}
	return 0;
}