10023 - Square root
Moderator: Board moderators
-
- 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 ?
the input will always be an ordinary numbers right ?
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 multiple-input question......
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
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
-
- 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[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
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 < 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 < 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]
-
- 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 ![:(](./images/smilies/icon_frown.gif)
Maybe it help us ...
Best regards
DM
![:(](./images/smilies/icon_frown.gif)
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)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- 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
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)
Born from ashes - restarting counter of problems (800+ solved problems)
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);
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]
-
- 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!
There should be a fix!
JongMan @ Yonsei
-
- 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]
![:D](./images/smilies/icon_biggrin.gif)
[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]
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.![:-?](./images/smilies/icon_confused.gif)
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.
![:-?](./images/smilies/icon_confused.gif)
-
- 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
[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