## 10023 - Square Root

Moderator: Board moderators

### 10023 - Square Root

is there any special input to be considered ... ?

the input will always be an ordinary numbers right ?
Almost Human
Learning poster

Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

The input contains +ve integers only(is that what you mean by "ordinary numbers"?).

Bear in mind that this is a multiple-input question......

For sample i/o, I've only tried easy cases. For instance:
5

7206604678144

9152324687831194092834914521

186755313003091766118189319724929

1

0

Output:
2684512

95667782914789

13665844759951423

1

0

If you really couldn't figure out what's wrong, why don't you share your algorithm with us??
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer
Guru

Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Code: Select all
`#include <stdio.h>#include <string.h>int main ( void ){  unsigned long NumOfCase , length , i , j ;  long double bedivide , divider ;  char input[10000] ;  freopen ( "10023.in" , "r" , stdin ) ;  freopen ( "10023.out" , "w" , stdout ) ;  scanf ( "%li\n\n" , &NumOfCase ) ;  while ( NumOfCase -- )  {    gets ( input ) ;    scanf ( "\n" ) ;    length = strlen ( input ) ;    if ( length % 2 )    {      bedivide = input[0] - '0' ;      i = 1 ;    }    else    {      bedivide = ( input[0] - '0' ) * 10 - ( input[1] - '0' ) ;      i = 2 ;    }    for ( divider = 0 ; ; )    {      for ( j = 0 ; j <= 9 ; j ++ )        if ( ( divider * 10 + j ) * j > bedivide ) break ;      j -- ;      printf ( "%li" , j ) ;      bedivide -= ( ( divider * 10 + j ) * j ) ;      if ( input[i] == 0 ) break ;      bedivide = bedivide * 100 + ( input[i] - '0' ) * 10 + ( input[i+1] - '0' ) ;      i += 2 ;      divider = divider * 10 + j + j ;    }    printf ( "\n\n" ) ;  }  return 0 ;}`

I've tried so many sample input range from 0 to 1e1000 it self but it's still WA...

Almost Human
Learning poster

Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

### I got TLE

Sadly, I got a TLE for this problem. Any good algorithms out there?

[cpp]#include <stdio.h>
#include <string.h>

typedef struct bignum_t {
char d[2000];
};

int cmp(bignum_t a, bignum_t b) {
int i;

for (i = 0; i < 2000; i++) {
if (a.d[i] < b.d[i])
return -1;
else if (a.d[i] > b.d[i])
return 1;
}

return 0;
}

bignum_t sum(bignum_t a, bignum_t b) {
bignum_t rv;
int i;

memset(rv.d, 0, sizeof(rv.d));
for (i = 1999; i > 0; i--) {
rv.d[i] += a.d[i] + b.d[i];
rv.d[i - 1] += rv.d[i] / 10;
rv.d[i] %= 10;
}

return rv;
}

bignum_t getavg(bignum_t a, bignum_t b) {
bignum_t rv;
int i;

rv = sum(a, b);
for (i = 0; i < 2000; i++) {
if (i < 1999)
rv.d[i + 1] += (rv.d[i] % 2) * 10;
rv.d[i] /= 2;
}

return rv;
}

bignum_t multiply(bignum_t a, bignum_t b) {
bignum_t prod, sub;
int end1, end2, i, j, k;

for (end1 = 0; end1 < 2000 && a.d[end1] == 0; end1++);
for (end2 = 0; end2 < 2000 && b.d[end2] == 0; end2++);

memset(prod.d, 0, sizeof(prod.d));
for (i = 1999; i >= end1; i--) {
memset(sub.d, 0, sizeof(sub.d));

for (j = 1999, k = i; j >= end2; j--, k--) {
sub.d[k] += a.d[i] * b.d[j];
sub.d[k - 1] += sub.d[k] / 10;
sub.d[k] %= 10;
}

prod = sum(prod, sub);
}

return prod;
}

void process() {
char str[1010];
bignum_t target, lo, hi, avg, sq;
int comp, i, j;

scanf("%s", &str);
if (strcmp(str, "1") == 0) {
printf("1\n\n");
return;
}
memset(target.d, 0, sizeof(target.d));
memset(lo.d, 0, sizeof(lo.d));
memset(hi.d, 0, sizeof(hi.d));
for (i = strlen(str) - 1, j = 1999; i >= 0; i--, j--)
hi.d[j] = target.d[j] = str[i] - '0';

while (true) {
avg = getavg(lo, hi);
sq = multiply(avg, avg);

comp = cmp(sq, target);
if (comp == -1)
lo = avg;
else if (comp == 1)
hi = avg;
else
break;
}

for (i = 0; i < 2000 && avg.d[i] == 0; i++);
if (i >= 2000)
printf("0\n\n");
else {
while (i < 2000)
printf("%d", avg.d[i++]);
printf("\n\n");
}
}

int main() {
int ntest;

#ifndef ONLINE_JUDGE
freopen("input.dat", "r", stdin);
freopen("output.dat", "w", stdout);
#endif

scanf("%d", &ntest);
while (ntest-- > 0)
process();

return 0;
}
[/cpp]
ec3_limz
Learning poster

Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

I don't know is there still true, but I remember, than judge's input contians values Y such than X*X < Y and X is solution
Maybe it help us ...

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

shouldn't these should be removed if it is true?
--
i used string manipulation but can't solved.
i have tried all critical input i made.
but no prob.
so why wa.
--
anupam
"Everything should be made simple, but not always simpler"
anupam
A great helper

Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm

sorry, for mail and net problem same post was posted twice.
anupam
"Everything should be made simple, but not always simpler"
anupam
A great helper

Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm

No problem.
I use string operations too and got TLE first time. I change only one thing to get Acc - I realize that my code may hang if and only if X*X < Y ... So I add one more condidtion and I got Acc .

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### 10023

Sorry, but why 10023 Accepted (P.E.)? Could you help me? Thank you!
[c]#include<stdio.h>
#include<math.h>
void main(void)
{
int i=0,t;
long double n[20];
while(scanf("%d",&t)==1){
printf("\n");
for(;i<t;i++){
scanf("%Lf",&n[i]);
printf("\n");
}
for(i=0;i<t;i++)
printf("%.0Lf\n\n",sqrtl(n[i]));
}
}[/c]
jai166
New poster

Posts: 10
Joined: Mon May 12, 2003 11:10 am

### ooh..

I suffered a few WAs from this problem and concluded that Dominik is definitely right. You should output largest X where X * X <= Y. The problem statement is completely wrong.

There should be a fix!
JongMan @ Yonsei
Whinii F.
Experienced poster

Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea

I think for this prob, you don't need special algo.
My friend told me to just use the command 'sqrtl'.
Joseph Kurniawan
Experienced poster

Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

### Thank you, and I've solved it!

Thank you, and I've solved it!
[c]#include<stdio.h>
#include<math.h>
void main(void)
{
int t;
long double n;

scanf("%d",&t);
for(;t;t--){
scanf("%Lf",&n);
printf("%.0Lf\n",sqrtl(n));
if(t>1)putchar('\n');
}
}[/c]
jai166
New poster

Posts: 10
Joined: Mon May 12, 2003 11:10 am

Why does the judge accept these solutions? I thought Y can by 10^1000...????? In which case this problem is not easy.
minskcity
Experienced poster

Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

### same question

Hmm,
I have the same question.
Can long double handle numbers of size 10^1000......... I don't think so.
Now then : why does the posted code get AC.

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

### 10023 I think this code is wrong, but accepted!!!!!!

I think this code is wrong, but accepted!!!!!! Only use sqrtl()!!!!!!!!!!

[cpp]
//I think this code is wrong, but accepted!!!!!!
#include <cstdio>
#include <cmath>
void main()
{
FILE* fp=fopen("Input.txt","r");
int N,i;
long double Y;

fscanf(fp,"%d\n",&N);
for(i=0;i<N;i++)
{
fscanf(fp,"%Lf\n",&Y);
if(i)putchar('\n');
printf("%.Lf\n",sqrtl(Y));
}
}[/cpp]

Should sb. fix it
I Believe I Can.
20717TZ
New poster

Posts: 21
Joined: Tue Apr 27, 2004 7:41 pm

Next