# CodeChef - Please like me

In a far away dystopian world, the measure of the quality of a person’s life is the numbers of likes he gets for an article about their life. For a person to stay alive, he has to acquire at least L number of likes before D days pass.

People in this world employ various techniques to increase the number of likes. One of the famous ones is to dis-like and re-like their own article once per day. On doing so you can assume that the number of likes for the post increase by a constant factor C.

So if one starts with S likes on Day-1, he would have D2 = S + C * S likes on Day-2, D3 = D2 + D2 * C on Day-3 etc. You are to answer if the person would survive at the end of Day-D or not.

Input

First line contains a single positive integer T denoting the number of test cases. The following T lines represent a test case each. Each test case contains 4 space-separated integers L, D, S and C.

Output

For each test case, print a single line containing “ALIVE AND KICKING” if the person would live, otherwise print, “DEAD AND ROTTING”.

Constraints

1 <= T <= 1000

1 <= L <= 1000000000

1 <= D <= 1000000000

1 <= S <= 1000000000

1 <= C <= 1000000000

Sample cases:

Input

2

5 1 5 1

10 2 2 2

Output

ALIVE AND KICKING

#include <stdio.h>

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
long long int l,d,s,c;
scanf("%lld%lld%lld%lld",&l,&d,&s,&c);
long long int i;
long long int x=s;
for(i=2;i<=d;i++)
x*=(1+c);
if(x>=l)
printf("ALIVE AND KICKING\n");
else
}
return 0;
}


How do I improve efficiency so that the time limit does not get exceeded?

• Use the power operator: pow, from math.h. 5*5*5*5=pow(5,4). So (d-1) times (1+c) multiplied is: pow( (1+c),(d-1) ). I think you can work it out from here. Apr 27, 2015 at 7:15
• i made my own power function (refer to exponentiation by squares) but that gave me wrong answer Apr 27, 2015 at 7:19
• Check this answer for a reference implementation of an integer power function. Much faster than pow too. Apr 27, 2015 at 7:53

I think the key thing you are missing isn't a better pow function. The problem is that you are iterating d times without checking whether you have surpassed l. Notice that for the lowest c of 1, you are multiplying by 2 every loop. The maximum l is 1000000000 which is less than 2^30. Therefore the max number of loops you will ever need is 30.

If you simply checked every loop:

if (x >= l)
break;


then you limit your loop to 30 iterations instead of 1000000000 iterations.

The problem with using a power function was that it returns a floating value. My variables are of type int. I changed them to double and used the pow function from math.h library and it worked.

I was also successful by using my own power function using the exponentiation by squares algorithm.

Here is my power function (using the exponentiation by squaring algorithm):

int power(int x, int n)
{
if(n==0)
return 1;
else if(n==1)
return x;
else if(n%2==0)
return power(x*x,n/2);
else if(n%2!=0)
return x*power(x*x,(n-1)/2);
}

• Great that you solved it. For completeness, could you add you implementation of the integer pow function in your answer? Apr 27, 2015 at 7:54
• @AtulShanbhag Since your function only operates on integers, so that's not a problem. Negative exponents don't really make sense for integer return values, since x can't take values in the range ]0,1[, so for any negative exponent the result would be in this range as well. You might want to consider error handling, should someone provide a negative exponent or just change the parameter type to unsigned int. Apr 27, 2015 at 8:37
• In that case, I would simply change my function and variable x from int type to double type. Then I would add an extra if statement that if(n<0) return power(1/x,-n); Apr 27, 2015 at 8:39
• Use bitwise operators to speed it up even more: n&1 to test uneven (logical AND); n<<1 for *2 (bitshift left) and n>>1 to /2 (bitshift right). Apr 27, 2015 at 11:06
• You need to handle overflow, otherwise your function could end up returning anything, including 0 or a negative number.
– JS1
Apr 28, 2015 at 17:20