Sunday 3 June 2012

UVa 11614 Etruscan Warriors Never Play Chess Solution

# include <stdio.h>
# include <math.h>
int main()
{
    long long i,n,t,sum;
   scanf("%lld",&t);
   for(i=1;i<=t;i++)
   {
       scanf("%lld",&n);
       sum = (sqrt(1+8*n)-1)/2;
       printf("%lld\n",sum);
   }
    return 0;
}

5 comments:

  1. Can you please discuss how you found the equation sum = (sqrt(1+8*n)-1)/2 ?

    ReplyDelete
    Replies
    1. suppose, n=3
      then,
      c=sqrt(1+8*3);
      x=c-1;
      y=x/2;
      printf("%lld",y);

      Delete
  2. Can you please discuss how you found the equation sum = (sqrt(1+8*n)-1)/2 ?

    ReplyDelete
  3. imple math problem

    n*(n+1)/2 = s
    n^2+n=2*s
    n^2+n+(-2*s)=0

    Using quadratic equation ax^2+bx+c=0

    del = sqrt(b*b-4*a*c) = sqrt(1-4*1*(-2s)) = sqrt(1+8s)
    we know x = (-b(+-) del)/2a

    Here i use only + value because del is always positive

    so n = (-1+sqrt(1+8s))/2

    Input as double s
    then print n (where n is convert from double to lo

    ReplyDelete