PLZLYKME - Editorial

During the contest, I simply derived the general formula in terms of day 1, and, afterwards, some simple maths and logarithm application allowed me to test for the problem’s codition simply like this:

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iostream>
using namespace std;

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int L,D,S,C;
		scanf("%d %d %d %d",&L,&D,&S,&C);
		if(log(C+1.0)*(D-1) >= log(L)-log(S))
			puts("ALIVE AND KICKING");
		else
			puts("DEAD AND ROTTING");
	}
	return 0;
}

I guess this a lot less complicated than being mislead or caught in overflow errors :slight_smile:

Best,

Bruno

12 Likes

This one is also simpler .
#include<stdio.h>
#include<math.h>
main()
{
double T,i,D,C,S,L;

scanf("%lf",&T);
for(i=1;i<=T;i++)
{
     scanf("%lf%lf%lf%lf",&L,&D,&S,&C);
     S=S*pow(C+1,D-1);
     if(S>=L)
     printf("ALIVE AND KICKING\n");
     else
     printf("DEAD AND ROTTING\n");
}

}

2 Likes

THIS ONE DERIVES GENERAL FORMULA AND COMPARES THE VALUE IN LOG SPACE INSTEAD,

ITS A FAR SIMPLER METHOD

import sys
from math import log

def solve(value):
if value[2] >= value[0]:
print “ALIVE AND KICKING”
return

n = (value[1]-1)*log(1+value[3])+log(value[2])		# total no of bits and bit representation of the product
p = log(value[0])					# value to be compared with (in log form)
diff = n-p


if abs(diff) < 0.000000000000001 :				# checking difference upto 15 decimal places
	i=1
	product=value[2]
	while i < value[1]:
		product*=value[1]
		if product >= value[0]:
			print "ALIVE AND KICKING"
			break
		i+=1
	
	print "DEAD AND ROTTING"
	

elif diff>= 0:
	print "ALIVE AND KICKING"
else: print "DEAD AND ROTTING"

input = sys.stdin.readlines()

N=int(input.pop(0))

for line in input:
values = [] # values are L,D,S,C
values = map(int,line.split())
solve(values)

#include
#include <math.h>
typedef long double lf;
using namespace std;

int main()
{
lf t,i,s,c,d,l,d1;
cin>>t;
while(t–)
{
cin>>l>>d>>s>>c;
s=s*pow(c+1,d-1);
if(s>=l)
cout<<“ALIVE AND KICKING”<<endl;
else
cout<<“DEAD AND ROTTING”<<endl;
}
return 0;
}

[Ideone][1]
[CodeChef: Practical coding for everyone][2]
[1]: http://ideone.com/unYP4l
[2]: CodeChef: Practical coding for everyone

Long long int also works in this case.

import math
for _ in range(int(input())):
l,d,s,c=input().split()
l,d,s,c=int(l),int(d),int(s),int©
sum=pow((1+c),(d-1))
sum=sum*s
if sum>=l:
print(‘ALIVE AND KICKING’)
else:
print(“DEAD AND ROTTING”)

WHY THIS GET LIME LIMIT EXCEED , HERE M NT USING LOOT SIMPLE MULTIPLICATION

def noOfLikes(d, s, c):
if d == 1:
return s
else:
return noOfLikes(d-1, s, c) + noOfLikes(d-1, s, c) * c

t = int(input())
for testCase in range(t):
    l, d, s, c = map(int, input().split())
    if noOfLikes(d,s,c) >= l:
        print("ALIVE AND KICKING")
    else:
        print("DEAD AND ROTTING")

This is giving a runtime error(NZEC). Any reasons?

Why long long int does not work on this code?

but when i give long long int ,it shows wrong answer…please help!!!.

@vivek7119 size of long double at codechef is 12 bytes and size of long long int is 8 bytes, may be that’s why your program fails on taking long long int.

this will run for smaller D values, when D=10^9, C=10^9, it will be a 9*10^9 digit number :(… but u can optimize whenever D>32 print DEAD. and when D<32 do your algorithm …( wondering about 32??? as min value of c is 1 so (c+1)^32 will have minimum value = (1+1)^32 which is graeater than 10^9) ans 10^9 is max range of L

1 Like

if(log(C+1.0)*(D-1) >= log(L)-log(S)) I dont understand this line. Can someone explain please

How did you get this derivation?

Can someone please explain how this ** log(C+1.0)*(D-1) >= log(L)-log(S) ** formula got drived? Please Help me I’m realy strugling while understanding it.

find the likes on second day and then divide it by s and the whatever the quotient is just power it by (d-1)(i,e d for days ) and then multiply the result with s and u will get the final result .

how did you got this derivation ?

?

I get WA for using long long int but AC using long double, can someone please comment why so? Thanks.

Likes on day 1 = S = S
Likes on day 2 = S * C + S = S(1+C)
Likes on day 3 = (S * C + S) * C + (S * C + S) = S(1+C)^2
Likes on day n = S(1+C)^(N-1)

Ooops I missed that previous time, thanks,

Probably because you’ve exceeded the stack depth in Python