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
Maybe it help us ...
Best regards
DM
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]
[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.
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.
-
- 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