What's the problem about this program?

[Mathsniper]

I am doing a problem about http://acm.hnu.cn:8080/online/?actio...=show&id=10238
I have uploaded it for many time but get WRONG ANSWER. So I hope someone can help me. This is my solution below. (input K_i < 2^31 =2147483648)

#include <stdio.h>
#include <math.h>

int main()
{
	int i, n;
	long long x, k;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%lld", &x);
		k = 8*x-7;
		if ((sqrt(k) == (int)sqrt(k)) && ((int)sqrt(k) % 2 != 0))
			if (i < n) printf("1 ");
			else printf("1");
		else if (i < n) printf("0 ");
			else printf("0");
	}
	printf("\n");
	return 0;
}

[swgh]

>long long x, k;

Shouldnt that be

long x, k;

[spoon!]

		k = 8*x-7;
		if ((sqrt(k) == (int)sqrt(k)) && ((int)sqrt(k) % 2 != 0))
			if (i < n) printf("1 ");
			else printf("1");
		else if (i < n) printf("0 ");
			else printf("0");

can you explain what all this is supposed to do? and why you think it accomplishes the task?

[ssharish2005]

oooooooo, this looks really useless in the code. cos its always going to be 1 and 0 printed

if (i < n) 
    printf("1 ");
else 
    printf("1");

else if (i < n) 
    printf("0 ");
else 
    printf("0");

ssharish2005

[Mathsniper]

can you explain what all this is supposed to do? and why you think it accomplishes the task?

Assume a[k] stands for "1" index. "1" will appear in 1,2, 4, 7, 11, 16, 22, 29,....
Which means a[k]=a[k-1]+k-1, so we can find that a[n]=(n-1)n/2 + 1. If we assume a[n] = k. Then we obtian n^2-n+2-2k=0. then n = (1+sqrt(8k-7))/2. If n is confirmed, we can know n is integer or other. Therefore, 8k-7 must be a square and sqrt(8k-7) is odd. Here is output data form my program.

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0

I think it works but I don't know why I cannot pass the task.

[Mathsniper]

who can know that what's the problem here?

[spoon!]

i dunno, it appears to work

does it tell you what the problem is? compile error? wrong output?

in case they were picky for some reason, here are some things you might try:
* change "long long" to "long" and "lld" to "ld"
* print the output after all the input is done

[vart]

Why do you think your get wrong output?

Maybe you should print your results into some buffer and print out the buffer after you finish your tests?
Also note that you calculating sqrt(k) 3 times - better do it once and use temporary variable


And the code

if ((sqrt(k) == (int)sqrt(k)) && ((int)sqrt(k) % 2 != 0))
			if (i < n) printf("1 ");
			else printf("1");
		else if (i < n) printf("0 ");
			else printf("0");

For me is simplier to understand in the form

if ((sqrt(k) == (int)sqrt(k)) && ((int)sqrt(k) % 2 != 0))
{
	printf("1");
}
else
{
	printf("0");
}
if (i < n) printf(" ");

[Salem]

> sqrt(k) == (int)sqrt(k)
This comparison is going to be performed using floating point arithmetic.
http://c-faq.com/fp/strangefp.html
Mathematical equality doesn't always mean computational equality, because all floats are ultimately approximations.

It takes a lot of care to compare floats (read more of that FAQ)

How about using this test?

int root = sqrt(k);
if ( root*root == k && root % 2 != 0 )

[coder8137]

int root = sqrt(k);

Shouldn't you round, incase sqrt() is say 5.99999...? E.g:

int root = sqrt(k) +0.5;

Anyways, vart already said what Salem posted above in one of your other threads about how to determine if a number is a perfect square, Mathsniper. No point asking if you're not going to use the suggestions.

[Mathsniper]

I'm sorry I don't reply the post for a long time. After I edit the code, it cannot be passed.

#include <stdio.h>
#include <math.h>

int main()
{
	int i, n;
	long x, k;
	int root;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%ld", &x);
		k = 8*x-7;
		root = sqrt(k)+0.5;
		if (root*root == k && root % 2 != 0)
			printf("1");
		else
			printf("0");
		if (i < n) printf(" ");
	}
	printf("\n");
	return 0;
}

Judge Result = Wrong Answer
Is my solution wrong? or?

[Salem]

I dunno, until you post an example input which is supposed to pass the test, which your code fails, it's really hard to figure out what the problem is.
Do you get to see what input the judge provides or not?

Though looking at the contest, it seems that you're supposed to deal with arbitrary large numbers, so using long long or double might not be good enough.

[vart]

Your output is mixed with the input - you should allocate buffer dynamically, based on the number of inputs you read from the first line and fill that buffer

After you finish reading the input - print your buffer

Or - alternatively - allocate arry for the input, read all the input, then process the array to print all the output in a way you're doing now...

That' my guess, why the output is descarded by the Judge

[Mathsniper]

No, the data maynot be saved as buffer and print it at time.
I wrote it by pascal. It can pass. But C doesn't.

var t:int64;
    n,j:longint;
begin
  readln(n);
  for j:=1 to n do
  begin
    readln(t);
    if trunc(sqrt(1+4*2*(t-1)))=sqrt(1+4*2*(t-1))  then
   begin
    if j<>n then write('1',' ') else write('1');
   end
   else
   begin
    if j<>n then  write('0',' ') else write('0');
   end;
  end;
end.

C code

#include <stdio.h>
#include <math.h>

int main()
{
	long i, n;
	unsigned long long x, k;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%lld", &x);
		k = sqrt(8*x-7);
		if (k == sqrt(8*x-7))
			printf("1");
		else
			printf("0");
		if (i != n) printf(" ");
	}
	return 0;
}

[vart]

Shouldn't you use I64d format instead of lld?