What's the problem about this program?

This is a discussion on What's the problem about this program? within the C Programming forums, part of the General Programming Boards category; 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 ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    77

    What's the problem about this program?

    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)
    Code:
    #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;
    }

  2. #2
    Its hard... But im here swgh's Avatar
    Join Date
    Apr 2005
    Location
    England
    Posts
    1,479
    >long long x, k;

    Shouldnt that be

    Code:
    long x, k;
    I'm just trying to be a better person - My Name Is Earl

  3. #3
    Registered User
    Join Date
    Dec 2006
    Posts
    30
    Quote Originally Posted by Mathsniper
    Code:
    		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?

  4. #4
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,682
    oooooooo, this looks really useless in the code. cos its always going to be 1 and 0 printed

    Code:
    if (i < n) 
        printf("1 ");
    else 
        printf("1");
    
    else if (i < n) 
        printf("0 ");
    else 
        printf("0");
    ssharish2005

  5. #5
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    Quote Originally Posted by spoon!
    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.
    Code:
    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.
    Last edited by Mathsniper; 12-15-2006 at 11:31 PM.

  6. #6
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    who can know that what's the problem here?

  7. #7
    Registered User
    Join Date
    Dec 2006
    Posts
    30
    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

  8. #8
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    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
    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
    Code:
    if ((sqrt(k) == (int)sqrt(k)) && ((int)sqrt(k) % 2 != 0))
    {
    	printf("1");
    }
    else
    {
    	printf("0");
    }
    if (i < n) printf(" ");
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,830
    > 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?
    Code:
    int root = sqrt(k);
    if ( root*root == k && root % 2 != 0 )
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #10
    Registered User
    Join Date
    Nov 2006
    Posts
    65
    int root = sqrt(k);
    Shouldn't you round, incase sqrt() is say 5.99999...? E.g:
    Code:
    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.

  11. #11
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    I'm sorry I don't reply the post for a long time. After I edit the code, it cannot be passed.
    Code:
    #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?

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,830
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  13. #13
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  14. #14
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    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.
    Code:
    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
    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;
    }

  15. #15
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    Shouldn't you use I64d format instead of lld?
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Multi Thread Program Problem
    By ZNez in forum C Programming
    Replies: 1
    Last Post: 01-03-2009, 11:10 AM
  2. Program Termination Problem
    By dacbo in forum C Programming
    Replies: 3
    Last Post: 01-23-2006, 02:34 AM
  3. Inheritance and Dynamic Memory Program Problem
    By goron350 in forum C++ Programming
    Replies: 1
    Last Post: 07-02-2005, 03:38 PM
  4. Replies: 20
    Last Post: 06-13-2005, 12:53 AM

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