Death Battle | TCS MockVIta 2 2020

Death Battle comes from TCS MockVita 2 (2020). Under the anime story it is a probability question: a fixed number of attacks, each normal or boosted with a known chance, and you need the exact probability that total damage is enough. The answer must be a reduced fraction, not a decimal, which is where most people get stuck.

It is worth solving because it teaches the binomial distribution in a concrete way, and because it shows a real Python trap: mixing floats into big-number arithmetic. We will build a solution that stays exact from start to finish.

Problem

Kyoma can stop time for exactly M seconds. In each of those seconds he hits the monster Nomu once. A normal hit does A damage. With probability L = L1/L2 (his luck), the hit is a super attack instead, which does A + C damage. Nomu starts with H health and dies when his health reaches 0. Find the probability that Kyoma kills Nomu within the M seconds. If it cannot happen at all, Kyoma dies, so print RIP.

Input format: the first line has T, the number of test cases. Each test case is one line with six integers: A H L1 L2 M C.

Output format: for each test case, the probability as P1/P2 with P1 ≤ P2 and gcd(P1, P2) = 1, or RIP if killing Nomu is impossible.

Constraints: 0 < T ≤ 50; 1 ≤ A, H, C, L1, L2 ≤ 1000; 1 ≤ M ≤ 20; L1 ≤ L2. Time limit: 1 second.

Input:
2
10 33 7 10 3 2
10 999 7 10 3 2

Output:
98/125
RIP

My reading of the statement: "impossible" means that even if all M hits are super attacks, the total damage M·(A+C) is still below H; in every other case a fraction is printed (which can be 1/1).

Approach

Step 1: count the super attacks you need. Every hit does at least A, so M normal hits do M·A. Each super attack adds C more. If k of the hits are super, total damage is M·A + k·C. Nomu dies when that is at least H. So the smallest useful k is

k_min = ceil(max(0, H − M·A) / C)

If k_min is more than M (equivalently, M·(A+C) < H), print RIP.

Step 2: probability of exactly k super attacks. Each second is an independent coin flip with success chance L1/L2. The chance of exactly k successes out of M is the binomial formula: C(M, k) · (L1/L2)^k · ((L2−L1)/L2)^(M−k).

Step 3: add up and keep it exact. Kyoma wins for any k from k_min to M, so sum those probabilities. Every term has the same denominator L2^M, so the answer is

numerator = sum over k of C(M,k) · L1^k · (L2−L1)^(M−k),   denominator = L2^M.

Both are whole numbers. Divide them by their gcd and print. Even 1000^20 = 10^60 is no problem for Python's integers.

Dry run on the first sample (A=10, H=33, L=7/10, M=3, C=2): three normal hits give 30, so we are 3 short. Each super adds 2, so we need k_min = ceil(3/2) = 2. The numerator is C(3,2)·7^2·3^1 + C(3,3)·7^3 = 441 + 343 = 784. The denominator is 10^3 = 1000. gcd(784, 1000) = 8, which gives 98/125. For the second test case, even three super hits do only 36 damage, far below 999, so the answer is RIP.

Solution in Python

from math import comb, gcd


def kill_probability(a, h, l1, l2, m, c):
    # Best case: every one of the m attacks is a super attack
    if m * (a + c) < h:
        return "RIP"

    # Damage from m normal attacks; each super attack adds c more
    shortfall = max(0, h - m * a)
    k_min = (shortfall + c - 1) // c    # ceil(shortfall / c)

    # P(exactly k supers) = C(m,k) * l1^k * (l2-l1)^(m-k) / l2^m
    # Keep everything as whole numbers so nothing is lost to rounding
    num = 0
    for k in range(k_min, m + 1):
        num += comb(m, k) * l1 ** k * (l2 - l1) ** (m - k)
    den = l2 ** m

    g = gcd(num, den)
    return f"{num // g}/{den // g}"


def main():
    t = int(input())
    for _ in range(t):
        a, h, l1, l2, m, c = map(int, input().split())
        print(kill_probability(a, h, l1, l2, m, c))


if __name__ == "__main__":
    main()

math.comb needs Python 3.8+. (x + c - 1) // c rounds a division up without floats.

What was wrong with the old solution. The earlier code computed C(M, k) with /, which returns a float in Python 3, and multiplied it into the numerator. Once the numerator became a float, numbers like 10^40 lost their lower digits, and the gcd step worked on rounded values. I compared it with an exact brute force on 3,000 random valid inputs and it was wrong on 1,265 of them. For 1 20 999 1000 20 1, twenty normal hits already kill Nomu, so the answer is 1/1, but the old code printed a huge fraction slightly above 1. It passed both samples, which is why the bug was easy to miss.

How I verified it. A brute force that tries all 2^M normal/super patterns with exact Fraction arithmetic agreed with this code on 3,000 random cases (M up to 12). A Monte Carlo run of 200,000 battles on the first sample gave about 0.784, matching 98/125. Edge cases: 5 10 3 3 2 1 (100% luck) gives 1/1, and 1 21 1 2 20 1 (needs at least one super in 20 flips) gives 1048575/1048576.

Output

98/125
RIP

Complexity

At most M + 1 = 21 loop rounds per test case on numbers of about 200 bits, so O(T · M) big-integer operations, far inside 1 second. Space is O(1) apart from those integers.

Common mistakes

• Using floats anywhere (/, a float luck value, Fraction(0.7)). The fraction must be exact.
• Forgetting that Nomu dies at exactly 0 health, so the condition is damage ≥ H, not damage > H.
• Not reducing the fraction. 784/1000 is the right value in the wrong format; the judge wants 98/125.

Another problem from the same round: Grooving Monkeys.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More TCS CodeVita solutions All coding problems MCQ practice