×

# PLZLYKME - Editorial

Author: Kaushik Iska
Tester: Mahbub
Editorialist: Jingbo Shang

Simple

# PREREQUISITES:

Programming Language

# PROBLEM:

Define F[1] = 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.

This question is marked "community wiki".

161446375
accept rate: 0%

19.8k350498541

 10 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 #include #include #include #include #include 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 :) Best, Bruno answered 13 Jan '14, 16:40 3★kuruma 17.7k●72●143●209 accept rate: 8%

This one is also simpler .

# 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
}


}

45336
accept rate: 0%

Why long long int does not work on this code?

(30 Oct '14, 20:55)

## 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

elif diff>= 0:
print "ALIVE AND KICKING"


N=int(input.pop(0))

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

2★divy7
11
accept rate: 0%

# 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; }

1
accept rate: 0%

(12 Nov '16, 14:07)

@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.

(12 Nov '16, 14:23) 5★
 0 Long long int also works in this case. answered 16 Jun '17, 11:59 1 accept rate: 0%
 0 import math for _ in range(int(input())): l,d,s,c=input().split() l,d,s,c=int(l),int(d),int(s),int(c) 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 answered 05 Jul '17, 20:34 3★akshaycs 1●1 accept rate: 0% 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 (05 Jul '17, 21:07)
 0 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? answered 26 Oct '17, 00:59 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×1,173
×946
×51

question asked: 13 Jan '14, 15:12

question was seen: 5,164 times

last updated: 26 Oct '17, 01:01