2
\$\begingroup\$

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

DEAD AND ROTTING

#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
            printf("DEAD AND ROTTING\n");
    }
    return 0;
}

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – agtoever Apr 27 '15 at 7:15
  • \$\begingroup\$ i made my own power function (refer to exponentiation by squares) but that gave me wrong answer \$\endgroup\$ – Atul Shanbhag Apr 27 '15 at 7:19
  • 1
    \$\begingroup\$ Check this answer for a reference implementation of an integer power function. Much faster than pow too. \$\endgroup\$ – agtoever Apr 27 '15 at 7:53
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ Great that you solved it. For completeness, could you add you implementation of the integer pow function in your answer? \$\endgroup\$ – agtoever Apr 27 '15 at 7:54
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Ext3h Apr 27 '15 at 8:37
  • \$\begingroup\$ 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); \$\endgroup\$ – Atul Shanbhag Apr 27 '15 at 8:39
  • \$\begingroup\$ 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). \$\endgroup\$ – agtoever Apr 27 '15 at 11:06
  • \$\begingroup\$ You need to handle overflow, otherwise your function could end up returning anything, including 0 or a negative number. \$\endgroup\$ – JS1 Apr 28 '15 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.