## 10023 - Square root

Moderator: Board moderators

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

### 10023 - Square root

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

the input will always be an ordinary numbers right ?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Code: Select all

``````#include <stdio.h>
#include <string.h>

int main ( void )
{
unsigned long NumOfCase , length , i , j ;
long double bedivide , divider ;
char input ;

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' ;
i = 1 ;
}
else
{
bedivide = ( input - '0' ) * 10 - ( input - '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...

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

### 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;
};

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

for (i = 0; i < 2000; i++) {
if (a.d < b.d)
return -1;
else if (a.d > b.d)
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 += a.d + b.d;
rv.d += rv.d / 10;
rv.d %= 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;
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]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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)

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
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
Contact:
sorry, for mail and net problem same post was posted twice.
anupam
"Everything should be made simple, but not always simpler"

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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)

jai166
New poster
Posts: 10
Joined: Mon May 12, 2003 11:10 am

### 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;
while(scanf("%d",&t)==1){
printf("\n");
for(;i<t;i++){
scanf("%Lf",&n);
printf("\n");
}
for(i=0;i<t;i++)
printf("%.0Lf\n\n",sqrtl(n));
}
}[/c]

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

### 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

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
I think for this prob, you don't need special algo.
My friend told me to just use the command 'sqrtl'. jai166
New poster
Posts: 10
Joined: Mon May 12, 2003 11:10 am

### 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]

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Why does the judge accept these solutions? I thought Y can by 10^1000...????? In which case this problem is not easy.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

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

### 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 - leestime.com