10023 - Square Root

[Almost Human]

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

the input will always be an ordinary numbers right ?

[Observer]

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

[Almost Human]

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

please help

[ec3_limz]

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]

[Dominik Michniewski]

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

[anupam]

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

[anupam]

sorry, for mail and net problem same post was posted twice.
please forgive & forget.
anupam

[Dominik Michniewski]

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

[jai166]

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]

[Whinii F.]

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!

[Joseph Kurniawan]

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

[jai166]

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]

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

[sohel]

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]

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