long minimumPasses(long m, long w, long p, long n) { using i128 = __int128_t; long long passes = 0; long long best = (long long)ceil((long double)n / (long double)(m * 1.0L * w)); long long candies = 0; while (true) { long long prod = (long long)min((i128)m * (i128)w, (i128)LLONG_MAX / 2); if (candies >= n) { best = min(best, passes); break; } best = min(best, passes + (long long)((n - candies + prod - 1) / prod)); if (candies < p) { long long need = p - candies; long long wait = (need + prod - 1) / prod; if (wait <= 0) wait = 1; passes += wait; i128 gained = (i128)prod * (i128)wait; if (gained > (i128)LLONG_MAX - candies) gained = (i128)LLONG_MAX - candies; candies += (long long)gained; continue; } long long canBuy = candies / p; candies -= canBuy * p; if (m < w) { long long diff = w - m; long long add = min(diff, canBuy); m += add; canBuy -= add; } else if (w < m) { long long diff = m - w; long long add = min(diff, canBuy); w += add; canBuy -= add; } long long half = canBuy / 2; m += half; w += (canBuy - half); passes += 1; i128 gained = (i128)m * (i128)w; if (gained > (i128)LLONG_MAX - candies) gained = (i128)LLONG_MAX - candies; candies += (long long)gained; } return best; }

Solution in Python 3

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'minimumPasses' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts following parameters:
#  1. LONG_INTEGER m
#  2. LONG_INTEGER w
#  3. LONG_INTEGER p
#  4. LONG_INTEGER n
#

def checkIfMidPassesPossible(m, w, p, n, rounds):
    candies = 0
    while rounds > 0:
        if m * w >= n:
            return True
        remaining_candies = n - candies
        needed_rounds = math.ceil(remaining_candies / (m * w))
        if needed_rounds <= rounds:
            return True
        if candies < p:
            rounds_needed_to_buy = math.ceil((p - candies) / (m * w))
            if rounds_needed_to_buy >= rounds:
                return False
            rounds -= rounds_needed_to_buy
            candies += rounds_needed_to_buy * m * w
        candies -= p
        if m <= w:
            m += 1
        else:
            w += 1
    return False

def minimumPasses(m, w, p, n):
    #Write your code here
    if p > n:
        return math.ceil(n / (m * w))
    low, high = 1, 10**12
    while low < high:
        mid = (low + high) // 2
        if checkIfMidPassesPossible(m, w, p, n, mid):
            high = mid
        else:
            low = mid + 1
    return low

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    m = int(first_multiple_input[0])

    w = int(first_multiple_input[1])

    p = int(first_multiple_input[2])

    n = int(first_multiple_input[3])

    result = minimumPasses(m, w, p, n)

    fptr.write(str(result) + '\n')

    fptr.close()

Is the assumption that you should buy production resources every time correct? Assume m=1, w=1, p=100, n=101 After 100 rounds we have 100 candies. If we run just one more round we can get to 101 If we "invest" these 100, then at the 101st round we only have 2 candies. What am I missing?

Many accepted submissions (that use greedy algo) are actually wrong.

Need to add these tests: ` Input: 5 5 25 50 Output: 2 And Input: 5 5 1 100 Output: 2

Many accepted submissions (that use greedy algo) are actually wrong. Need to add these tests: ` Input: 5 5 25 50 Output: 2 And Input: 5 5 1 100 Output: 2