 PLZLYKME - Editorial

Author: Kaushik Iska
Tester: Mahbub
Editorialist: Jingbo Shang

Simple

PREREQUISITES:

Programming Language

PROBLEM:

Define F = S, F[i > 0] = F[i - 1] * (C + 1). Determine whether F[D] >= L.

EXPLANATION:

First of all ,we need to observe that F[] is monotone increasing, because of (C + 1) > 1.

Second, F[] is increasing exponentially, while L is smaller than 10^9. That means, only O(log L) days are needed for F[D] to exceed L.

Third, when F[] exceed L, it is possible about 10^18 (exceeding int in C++ and Java). So please choose the appropriate type to store.

In summary, what we need to do is calculate F[0…D] one by one, until all D + 1 ones are got or some one is greater than L. The time complexity is in O(min{D, log L}).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

4 Likes

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
}
return 0;
}

I guess this a lot less complicated than being mislead or caught in overflow errors Best,

Bruno

11 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

");
else
");
}
}

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 >= value:
print “ALIVE AND KICKING”
return

n = (value-1)*log(1+value)+log(value)		# total no of bits and bit representation of the product
p = log(value)					# 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
while i < value:
product*=value
if product >= value:
print "ALIVE AND KICKING"
break
i+=1

print "DEAD AND ROTTING"

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

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
}
return 0;
}

Long long int also works in this case.

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

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:

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

Why long long int does not work on this code?