10023 - Square root
Moderator: Board moderators
-
- 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?
- Chris Adams
-
- 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:
To:
Everytime I need to make this change before submission.
However, I'm now using this:
Code: Select all
FILE* fp=fopen("Input.txt","r");
Code: Select all
FILE* fp=stdin;
However, I'm now using this:
Code: Select all
#ifndef ONLINE_JUDGE
freopen("Input.txt", "r", stdin);
#endif
I Believe I Can - leestime.com
-
- 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?
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;
}
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
Thanks for reading
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"));
}
}
There is no knowledge that is no power.
Re: 10023 - RTE
Try changing
for
I'm not sure if that is your problem, though.
Code: Select all
public class Main {
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
Are you dreaming right now?
http://www.dreamviews.com
Re: 10023 - RTE
I have changed as you say...but still RTE..with time 0.0000
There is no knowledge that is no power.
Re: 10023 - RTE
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
Re: 10023 - RTE
Thanks!! andmej, that was de error...
now it's time to face the TLE I got![:(](./images/smilies/icon_frown.gif)
now it's time to face the TLE I got
![:(](./images/smilies/icon_frown.gif)
There is no knowledge that is no power.
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;
}
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;
}
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!
It has only 64 bits of precision, while you actually need log_2(10^1000) ~= 3321 bits for this problem!
-
- 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.
think judge has fixed it.
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.
But now that's finally fixed, and you have no easy way to avoid coding bignums here.
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.
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;
}