### 10023 - Square root

Posted:

**Fri May 23, 2003 9:40 am**is there any special input to be considered ... ?

the input will always be an ordinary numbers right ?

the input will always be an ordinary numbers right ?

Page **1** of **9**

Posted: **Fri May 23, 2003 9:40 am**

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

the input will always be an ordinary numbers right ?

the input will always be an ordinary numbers right ?

Posted: **Fri May 23, 2003 11:32 am**

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:

Bear in mind that this is a

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

Output:5

7206604678144

9152324687831194092834914521

186755313003091766118189319724929

1

0

If you really couldn't figure out what's wrong, why don't you share your algorithm with us??2684512

95667782914789

13665844759951423

1

0

Posted: **Sat May 24, 2003 7:04 am**

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

please help

Posted: **Mon May 26, 2003 1:00 pm**

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* < 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[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]

[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

return -1;

else if (a.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

rv.d

rv.d

}

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]

Posted: **Mon May 26, 2003 2:06 pm**

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

Maybe it help us ...

Best regards

DM

Posted: **Tue May 27, 2003 6:39 am**

--

i used string manipulation but can't solved.

i have tried all critical input i made.

but no prob.

so why wa.

--

anupam

Posted: **Tue May 27, 2003 6:41 am**

please forgive & forget.

anupam

Posted: **Tue May 27, 2003 7:41 am**

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

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

Posted: **Sat Jun 07, 2003 3:33 pm**

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*);*

printf("\n");

}

for(i=0;i<t;i++)

printf("%.0Lf\n\n",sqrtl(n*));*

}

}[/c]

[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

printf("\n");

}

for(i=0;i<t;i++)

printf("%.0Lf\n\n",sqrtl(n

}

}[/c]

Posted: **Thu Jul 31, 2003 6:21 am**

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!

There should be a fix!

Posted: **Thu Jul 31, 2003 6:47 am**

I think for this prob, you don't need special algo.

My friend told me to just use the command 'sqrtl'.

My friend told me to just use the command 'sqrtl'.

Posted: **Thu Jul 31, 2003 11:32 am**

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]

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

Posted: **Sun Mar 21, 2004 6:54 am**

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

Posted: **Sun Mar 21, 2004 7:16 am**

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.

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.

Posted: **Fri May 28, 2004 9:23 am**

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

[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