Skip to content

The Guess-and-Prove Workflow

The Problem That Requires Thinking Before Coding

You have a pet. It starts with strength X. To evolve, it needs strength ≥ Y. Two gyms:

  • Multiply gym: multiply current strength by A. Costs 1 EXP.
  • Add gym: add B to current strength. Costs 1 EXP.

Constraint: You can only use a gym if the result stays strictly below Y (no overshoot). The game ends when neither gym is safe anymore. Maximize total EXP.

(ABC180D — Takahashi Unevolved. Constraints: 1 ≤ X < Y ≤ 10^18, 2 ≤ A ≤ 10^9, 1 ≤ B ≤ 10^9.)

The Greedy Choice: Only multiply when multiplication grows X slower than addition. Once multiplication is the bigger jump, switch to adding permanently.

There are two operations. You can interleave them arbitrarily. The question is: what ordering maximizes the number of operations before the game ends?

Here's something that takes a while to click: maximizing operations means keeping X as small as possible for as long as possible. Every operation that makes X jump high is an operation that kills future operations. The greedy choice isn't "do the biggest thing" — it's "do the slowest-growing thing."

Step 1: Brute Force Small Cases

For tiny values we can enumerate everything.

X=2, Y=10, A=3, B=1:

Every possible sequence (up to length 7): - Pure adds: 2→3→4→5→6→7→8→9 (9+1=10≥10, stop). Total: 7. - M first: 2→6. Then adds: 6→7→8→9 (9+1=10≥10, stop). Total: 1+3 = 4. - A,M: 2→3→9 (9×3=27≥10, can't M; 9+1=10≥10, can't A). Total: 2. - A,A,M: 2→3→4→12? 4×3=12≥10. Can't M. 4→5→6→7→8→9. Total: 2+5 = 7. - A,A,A,M: 2→3→4→5. 5×3=15≥10. Then adds: 5→6→7→8→9. Total: 3+4 = 7. - M,A×3: 2→6→7→8→9. Total: 4.

The maximum is 7. Pure additions win here! Multiplying by 3 makes X jump too fast — it gobbles up the space below \(Y\) in one gulp.

Now try X=2, Y=1000, A=3, B=1:

Pure adds: 2→3→4→...→999. That's 997 ops.

Add a few first, then multiply: 2→3→9→27→81→243→729 (729×3=2187≥1000, stop). Then 270 adds. Total: 1+5+270 = 276 ops.

Multiply first as much as possible: 2→6→18→54→162→486 (486×3=1458≥1000, stop). Then 513 adds. Total: 5+513 = 518 ops.

Wait — 997 > 518 > 276. For \(B=1\), pure addition is still better! But what about X=2, Y=1000, A=3, B=100?

Pure adds: \((1000 - 2 - 1) / 100 = 9\) ops.

Multiply then add: 2→6→18→54→162→486 (5 multiplications). Then \((1000 - 486 - 1) / 100 = 5\) adds. Total: 10 ops. Better!

The pattern is clear: multiplying is only worth it when it grows X more slowly than adding B would. When \(X\) is small and \(X \times A < X + B\), multiplication is the slower option. Once \(X\) gets large enough that \(X \times A \geq X + B\), multiplication becomes the aggressive move and we should switch to addition permanently.

Step 2: State the Conjecture

Greedy rule: At each step, compare the two growth amounts. Multiplying increases X by \(X \times (A - 1)\). Adding increases X by \(B\). Only multiply while multiplication grows X by less: \(X \times A < X + B\) (equivalently, \(X \times (A-1) < B\)). The moment multiplication would grow X at least as fast as addition, switch to adding permanently.

Also, multiplication must not overshoot: \(X \times A < Y\).

So the multiply phase continues while both conditions hold: - \(X < Y / A\) (safe, no overshoot) - \(X \times A < X + B\) (multiplication is the slower-growing option)

Step 3: Prove It with the Exchange Argument

The proof has two parts.

Part 1: Multiplications must come before additions.

Suppose at some point we add (getting \(X + B\)) and then multiply (getting \((X + B) \times A\)). Compare with doing these in the opposite order: multiply then add gives \(X \times A + B\).

  • Add-then-Multiply result: \((X + B) \times A = XA + BA\)
  • Multiply-then-Add result: \(XA + B\)
  • Difference: \((XA + BA) - (XA + B) = B(A - 1) \geq B \geq 1\) (since \(A \geq 2\))

Add-then-Multiply gives a strictly larger intermediate value. A larger value means we're closer to \(Y\), which means fewer future operations. So for any adjacent (Add, Multiply) pair, swapping to (Multiply, Add) gives a smaller intermediate value — more room below \(Y\) — weakly more operations.

By repeatedly applying this swap (like bubble sort), we can move all multiplications before all additions without losing EXP.

Conclusion: all multiplications first, then all additions.

Part 2: Only multiply while it's the slower growth.

This is the key insight the ordering proof doesn't give us. Knowing multiplications come first doesn't tell us how many to do. We want to maximize total operations, so we want X to grow as slowly as possible at each step.

  • Multiplying increases X by \(X \times A - X = X(A-1)\)
  • Adding increases X by \(B\)

When \(X(A-1) < B\), multiplication grows X less than addition — so multiply (it wastes less of the space below \(Y\)). When \(X(A-1) \geq B\), addition is the smaller step — switch to adding.

Since \(X\) only increases, once \(X(A-1) \geq B\) it stays that way. The transition point is a clean cutoff: multiply while \(X \times A < X + B\), add forever after.

Step 4: Handle the Two Phases

Phase 1 — Multiply: Keep multiplying while X < Y / A AND X * A < X + B. This runs at most \(\log_A(Y) \leq \log_2(10^{18}) \approx 60\) times. Very fast.

Phase 2 — Add: After all multiplications, we add as many times as possible. Each add is \(+B\). We need \(X + kB < Y\).

Here's the math, broken down for clarity:

  • We need \(X + kB < Y\) (strictly less than \(Y\))
  • In integers, strictly less than \(Y\) is the same as less than or equal to \(Y - 1\)
  • So \(X + kB \leq Y - 1\)
  • Rearranging: \(kB \leq Y - X - 1\)
  • Therefore: \(k \leq (Y - X - 1) / B\)

Using integer division: k = (Y - X - 1) / B.

Let's verify: - X=486, Y=1000, B=100: k = (1000 - 486 - 1) / 100 = 513/100 = 5. Check: 486 + 5×100 = 986 < 1000 ✓. 486 + 6×100 = 1086 ≥ 1000 ✓. - X=6, Y=10, B=1: k = (10 - 6 - 1) / 1 = 3. Check: 6→7→8→9, three adds. 9+1=10 ≥ 10, stop. ✓

Step 5: The Overflow Trap

The constraint \(Y \leq 10^{18}\) means values fit in long long. But X * A might overflow during the multiply phase.

Unsafe check: while (X * A < Y) — if \(X = 10^{9}\) and \(A = 10^{9}\), then \(X \times A = 10^{18}\). Borderline, but larger values would overflow.

Safe check: while (X < Y / A). Since Y/A uses integer division, this is equivalent to \(X \times A < Y\) for positive values, but without risking overflow.

The Full Trace

X=2, Y=10, A=3, B=1:

Phase 1 — Multiply: | Op # | X before | X < Y/A? (10/3=3) | X×A < X+B? (6 < 3) | Action | X after | |------|----------|-------------------|---------------------|--------|---------| | — | 2 | 2 < 3 ✓ | 6 < 3 ✗ | stop | 2 |

Zero multiplications! Multiplying 2→6 is a jump of 4, but adding gives a jump of only 1. Addition is slower, so we skip straight to Phase 2.

Phase 2 — Add: k = (10 - 2 - 1) / 1 = 7 additions. X goes 2→3→4→5→6→7→8→9.

Total: 0 + 7 = 7 EXP. Matches our brute force.

X=2, Y=1000, A=3, B=100:

Phase 1 — Multiply: | Op # | X before | X < Y/A? (333) | X×A < X+B? | Action | X after | |------|----------|----------------|------------|--------|---------| | 1 | 2 | 2 < 333 ✓ | 6 < 102 ✓ | Multiply | 6 | | 2 | 6 | 6 < 333 ✓ | 18 < 106 ✓ | Multiply | 18 | | 3 | 18 | 18 < 333 ✓ | 54 < 118 ✓ | Multiply | 54 | | — | 54 | 54 < 333 ✓ | 162 < 154 ✗ | stop | 54 |

3 multiplications. At X=54, multiplying would give 162 (jump of 108), but adding gives 154 (jump of 100). Addition is now slower, so we switch.

Phase 2 — Add: k = (1000 - 54 - 1) / 100 = 945/100 = 9 additions.

Total: 3 + 9 = 12 EXP.

X=2, Y=100, A=2, B=1:

Phase 1 — Multiply: | Op # | X before | X < Y/A? (50) | X×A < X+B? | Action | X after | |------|----------|---------------|------------|--------|---------| | 1 | 2 | 2 < 50 ✓ | 4 < 3 ✗ | stop | 2 |

Zero multiplications! When B=1, doubling is always a bigger jump than adding 1 (for X ≥ 2). Pure addition.

Phase 2 — Add: k = (100 - 2 - 1) / 1 = 97. Total: 97 EXP.

The 5-Step Workflow (Summary)

The guess-and-prove workflow: brute force, observe, conjecture, stress test, prove — with feedback loop on failure

Step Action This Problem
1. Brute force Enumerate all orderings for small inputs Tried all sequences for Y=10
2. Observe What does the optimal look like? Multiply only when it's the slower option
3. Conjecture State a rule "Multiply while X×A < X+B and safe, then add"
4. Stress test Greedy vs brute force on random cases Would catch the B=1 case immediately
5. Prove Exchange argument Part 1: ordering. Part 2: growth-rate cutoff

Don't skip step 4. Even a proof can have gaps. The stress test catches what the proof misses. If we had only proved Part 1 (multiplications first) and skipped Part 2, we'd have coded "multiply as much as possible" — and gotten X=2, Y=10, A=3, B=1 wrong (4 instead of 7).

The Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long X, Y, A, B;
    cin >> X >> Y >> A >> B;

    long long ops = 0;

    while (X < Y / A && X * A < X + B) {
        X *= A;
        ops++;
    }

    if (X + B < Y) {
        ops += (Y - X - 1) / B;
    }

    cout << ops << "\n";
    return 0;
}

Try It

Input: 2 10 3 1
Output: 7

Trace: no multiplications (3×2=6 > 2+1=3, multiplication is faster). Pure adds: 2→3→...→9. Seven ops.

Input: 2 1000 3 100
Output: 12

Input: 3 10 2 5
Output: 1

Trace: 3 < 10/2=5 ✓, 6 < 8 ✓ → multiply to 6. Then 6+5=11 ≥ 10, can't add. Total: 1.

Input: 1 1000000000 2 1
Output: 999999998

For the last case: 1×2=2 vs 1+1=2, equal, so the condition X*A < X+B is 2 < 2 = false. No multiplications. Pure adds: (10^9 - 1 - 1) / 1 = 999999998.

Challenge: What if A = 2 and B = 1000000000? The multiply condition \(X \times A < X + B\) simplifies to \(X < B\). How many multiplications happen before the switch? Think about it, then verify with the code.

Problems

Problem Link Difficulty
ABC180D — Takahashi Unevolved atcoder.jp/contests/abc180/tasks/abc180_d 400pts