You are not logged in. Please login at www.codechef.com to post your questions!

×

PLZLYKME - Editorial

PROBLEM LINK:

Practice
Contest

Author: Kaushik Iska
Tester: Mahbub
Editorialist: Jingbo Shang

DIFFICULTY:

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

asked 13 Jan '14, 15:12

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446375
accept rate: 0%

edited 22 Apr '15, 17:31

admin's gravatar image

0★admin ♦♦
19.8k350498541


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 :)

Best,

Bruno

link

answered 13 Jan '14, 16:40

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

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");
}

}

link

answered 13 Jan '14, 18:39

shantanu10's gravatar image

2★shantanu10
45336
accept rate: 0%

Why long long int does not work on this code?

(30 Oct '14, 20:55) sagar04302★

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)

link

answered 14 Jan '14, 00:27

divy7's gravatar image

2★divy7
11
accept rate: 0%

include <iostream>

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

link

answered 12 Nov '16, 14:06

vivek7119's gravatar image

2★vivek7119
1
accept rate: 0%

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

(12 Nov '16, 14:07) vivek71192★

@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) srd0915★

Ideone
https://www.codechef.com/viewsolution/14262879

Long long int also works in this case.

link

answered 16 Jun '17, 11:59

zeeshan_ju's gravatar image

4★zeeshan_ju
1
accept rate: 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

link

answered 05 Jul '17, 20:34

akshaycs's gravatar image

3★akshaycs
11
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) abhikalpu_1235★
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?

link

answered 26 Oct '17, 00:59

kartikcool712's gravatar image

2★kartikcool712
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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