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

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

bigInt... Large base = more speed? (10023)

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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
I don't see a reason why it should make multiplication significantly slower.

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:
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
*/
I Believe I Can - leestime.com

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:
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
I Believe I Can - leestime.com

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 10023 - Square Root why WA?

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;
}
http://www.newton.0fees.net is enough! subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

10023 - RTE

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

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"));
}
}
There is no knowledge that is no power.

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 10023 - RTE

Try changing

Code: Select all

public class Main {
for

Code: Select all

class Main {

I'm not sure if that is your problem, though.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

Re: 10023 - RTE

I have changed as you say...but still RTE..with time 0.0000
There is no knowledge that is no power.

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 10023 - RTE

Try this input:

Code: Select all

1
1 Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

Re: 10023 - RTE

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

now it's time to face the TLE I got There is no knowledge that is no power.

pok
New poster
Posts: 25
Joined: Sun Nov 09, 2008 11:04 pm

Re: 10023 - Square Root

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10023 - Square Root

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
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 10023 - Square Root

But some of my friends had got Acc
think judge has fixed it.
http://www.newton.0fees.net is enough! mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10023 - Square Root

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
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Wrong Answer .... why ????????

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) 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;
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) {
return true;
}
return false;
}

};

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