2869: The Snail Wants to Climb Up

Baekjoon Online Judge #2869

Following the problem's requirements,

we can just use a while loop to compute the number of days.

Since the snail keeps climbing and sliding back "repeatedly" until it finally gets past the top of the pole,

we can set that point (a height greater than the top) as the break condition and run the while loop to solve it.

def getDay(a, b, v):
    day = 0;
    # current height
    height = 0; 

    while True:
        day += 1;
        height += a;
        if height >= v:
            return day;
        height -= b;
    return;

def solution():

    # a : height climbed during the day
    # b : height slid down during the night
    # v : height of the tree
    a, b, v = map(int, input().split())

    day = getDay(a,b,v);
    print(day);

solution();

Running it against the example input given in the problem produced the correct output.

Such a simple problem, so all that's left is to submit it!

Wait, what is this?

"Time Limit Exceeded"?

How expensive could this computation possibly be for it to time out?

In this cutting-edge era where AI keeps advancing and the RTX 5090 has already been released, is it really plausible that this small a calculation can't be handled?

It isn't.

There's a specific reason I picked this problem to study algorithms with.

It's not because simply solving the problem matters,

but because finding the optimal way to solve it is what's actually needed.

This is exactly the moment where coding needs "math."

(* This algorithm isn't one introduced in a textbook.)

Let's go back to the problem and think about how to solve it properly.

📌 The core of the problem

The snail climbs up by A during the day.

It slides down by B during the night.

On the final day, it doesn't slide back down at night — once it reaches the top, it stops.

The goal is to compute the minimum number of days needed to reach height V.

Since it climbs up by A during the day

and slides down by B during the night,

the net height gained per day is (A - B).

On the final day (the moment it passes the pole), it doesn't slide down, so it moves by A - δ instead.

( δ = some positive value that corrects for not exceeding A while not going past V → S - V )

S = (A - B) * (day -1) + A

V = (A - B) * (day -1) + ( A - δ )

| 🚀c.f] V is an identity — it takes the form of the division algorithm.

* When dividing a polynomial B(x) by a polynomial A(x),
there exist unique polynomials Q(x) and R(x) satisfying
B(x)=A(x)*Q(x)+R(x), (0 ≤ deg R(x) < deg A(x)).
Here, Q(x) is called the quotient and R(x) the remainder.

V = (A−B) * Q(DAY−1) + R | R is ( A - δ ) | | --- |

That's how it can be expressed.

We just need to find the minimum day satisfying S ≥ V.

Rewriting that,

we get (A - B) * (day -1) + A ≥ V.

Solving this for day,

day ≥ [ (V - A) / (A - B) ] + 1

Since day must be an integer, we need to round up any decimal, because day's domain is int.

For example, if 3.47 days were needed,

3 days wouldn't be enough, so we'd have to wait until the next day, meaning 4 days are actually required.

def getDay_v2(a, b, v):
    # the moment math becomes necessary
    import math

    return math.ceil((v - a) / (a - b)) + 1

Through the mathematical reasoning above, I derived a formula that satisfies the requirements.

I improved the brute-force getDay into getDay_v2.

🔥A further thought

Also,

V = (A - B) * (day -1) + ( A - δ )

if we want to find δ from this,

we can rearrange the equation above in terms of δ.

δ = (A - B) * (day -1) + (A - V)

Since getDay_v2 already gives us day, and we know A, B, V, and day, we can compute this directly.

🤔 Why would you even need this?

Suppose, for example, that some organization's budget allocation system works as follows.

Since a budget is always limited, in order to prevent it from being over-concentrated in one place,

it's designed to apply a kind of pagination concept, distributing funds sequentially according to priority.

So let's assume that when carrying out a grant program, funds are disbursed (as transactions) in units of 1 million won.

In other words, if the maximum amount that can be transferred in a single transaction is 1 million won,

then a system is needed that splits the required budget across multiple disbursements.

Suppose we're building such a system and writing the budget allocation module.

If the required budget is 5.3 million won, 5 disbursements aren't enough — 6 are needed.

So a total of 6 million won ends up being disbursed,

which is a 700,000-won gain for the recipient but a 700,000-won extra cost for whoever is allocating the budget.

Therefore, to guard against this kind of loophole in the system,

when carrying out a disbursement where the transfer amount would exceed the required budget,

a condition should be added so that only the remaining balance gets sent.

The remaining balance = (amount per disbursement - δ).

That's why δ is needed — to compute this remaining balance.

🕵️ Or, alternatively, this δ could be exploited the way "salami slicing" works.

Suppose, for example, that at the system level, transfers happen in fixed-size blocks.

In that case, even if a δ arises, it doesn't strictly have to be sent to the requesting institution.

Because as long as the institution's requested budget amount is satisfied, nothing looks wrong at the system level.

Also, from the perspective of the institution responsible for allocating the budget,

since the expected number of block-sized transactions occurred normally,

the anomaly might not be easy to detect.

So if this structure is exploited well, whenever a δ arises,

it could be implemented so that amount gets deposited into a separate account (say, the module developer's).

😎 If you ever need someone to build a budget allocation module like this, call me!