Overview

Over \(N\) days of watering, you choose method A or B each day, with a penalty that growth is halved the day after choosing method A. The goal is to maximize the total growth. Since \(N\) can be up to \(10^{18}\), which is extremely large, we solve this efficiently using matrix exponentiation over the max-plus semiring.

Analysis

Viewing it as state transitions

Each day’s growth depends only on “what was chosen the previous day.” In other words, the state can be managed with just 2 states: “A was chosen the previous day” and “B was chosen the previous day (or it’s the first day).”

The transitions are summarized as follows:

Previous choice	Today’s choice	Today’s growth
B (or none)	A	\(a\)
B (or none)	B	\(b\)
A	A	\(\lfloor a/2 \rfloor\)
A	B	\(\lfloor b/2 \rfloor\)

Naive DP is too slow

Define \(dp_A(i)\): the maximum total growth when A is chosen on day \(i\), and \(dp_B(i)\): the maximum total growth when B is chosen on day \(i\). Then:

\[dp_A(i) = \max(dp_A(i-1) + \lfloor a/2 \rfloor, \; dp_B(i-1) + a)\]

\[dp_B(i) = \max(dp_A(i-1) + \lfloor b/2 \rfloor, \; dp_B(i-1) + b)\]

This is \(O(N)\), but since \(N \le 10^{18}\), it’s far too slow.

Speeding up with max-plus matrix exponentiation

The above transitions have the form of “taking the maximum while adding.” This can be viewed as matrix multiplication over the max-plus semiring, where the usual \((+, \times)\) in matrix multiplication is replaced by \((\max, +)\).

Define the transition matrix \(T\) as follows (rows represent “today’s state,” columns represent “previous day’s state”):

\[T = \begin{pmatrix} \lfloor a/2 \rfloor & a \\ \lfloor b/2 \rfloor & b \end{pmatrix}\]

Here, \(T[i][j]\) is the growth when “the previous day was state \(j\) and today is state \(i\).”

The initial vector for day 1 is \((dp_A, dp_B) = (a, b)\), and applying \(T\) a total of \((N-1)\) times gives the state on day \(N\).

Concrete example: For \(N=3, a=10, b=7\) - Day 1: \(dp_A=10, dp_B=7\) - Day 2: \(dp_A = \max(10+5, 7+10)=17\), \(dp_B = \max(10+3, 7+7)=14\) - Day 3: \(dp_A = \max(17+5, 14+10)=24\), \(dp_B = \max(17+3, 14+7)=21\) - Answer: \(\max(24, 21) = 24\) (achieved by B → A → A, not A → A → A)

Algorithm

1. If \(N=1\), output \(\max(a, b)\) and terminate.
2. Define the \(2 \times 2\) transition matrix \(T\) over the max-plus semiring.
3. Compute \(T^{N-1}\) using repeated squaring (using max-plus matrix multiplication).
4. Apply \(T^{N-1}\) to the initial vector \((a, b)\), and the maximum of the resulting 2 states is the answer.

Definition of max-plus matrix multiplication: $\(C[i][j] = \max_k \left( A[i][k] + B[k][j] \right)\)$

The identity matrix has \(0\) on diagonal entries and \(-\infty\) on off-diagonal entries (since \(-\infty\) is the identity element for \(\max\), and \(0\) is the identity element for \(+\)).

Complexity

• Time complexity: \(O(\log N)\) (since the matrix is \(2 \times 2\), each step takes constant time)
• Space complexity: \(O(1)\) (the matrix size is fixed at \(2 \times 2\))

Implementation Notes

• Identity element of the max-plus semiring: Handle \(-\infty\) appropriately. In Python, use float('-inf').

• Applying the initial vector: After computing \(T^{N-1}\), obtain the final result via max-plus product with the initial vector \((a, b)\). Specifically, compute \(\max_{i,j}(T^{N-1}[j][i] + \text{init}[i])\).

• Special handling for \(N=1\): To correctly handle the case where the exponent of matrix exponentiation becomes \(0\), it’s safer to handle this case separately beforehand.

• Integer division: Python’s // operator correctly computes \(\lfloor x/2 \rfloor\) for non-negative integers, so it can be used directly.

  Source Code

def solve():
    N, a, b = map(int, input().split())
    
    if N == 0:
        print(0)
        return
    
    # We need to choose A or B each day to maximize total growth.
    # If previous day was A, current day's growth is halved.
    # 
    # Let's think about patterns:
    # - All B: N * b
    # - All A: a + (N-1) * (a // 2)
    # - Alternating A, B, A, B, ...: each A gives a (since prev is B or first day), each B gives b//2 (since prev is A)
    #   Wait, A then B: B gets halved. So pattern AB AB AB...
    #   A gives a, B gives b//2. Per 2 days: a + b//2
    # - Alternating B, A, B, A, ...: B gives b, A gives a (since prev is B). Per 2 days: b + a
    #   Wait, but then the next B after A gets halved: b//2
    #   So pattern: B, A, B, A, B, A, ...
    #   Day 1 (B): b, Day 2 (A): a, Day 3 (B): b//2, Day 4 (A): a, Day 5 (B): b//2, ...
    #   Hmm, not purely periodic from the start.
    #
    # Let me think with DP states. State = what was done previous day (A or B).
    # dp[A] = max total ending with A on last day
    # dp[B] = max total ending with B on last day
    #
    # Transitions:
    # If last day was B, new day A: gain a (no halving)
    # If last day was B, new day B: gain b
    # If last day was A, new day A: gain a//2
    # If last day was A, new day B: gain b//2
    #
    # So this is a 2-state linear recurrence over N days -> matrix exponentiation.
    #
    # State vector: (dp_A, dp_B) after day i
    # But it's max-plus, not standard linear algebra.
    # We can use max-plus matrix exponentiation.
    
    # Max-plus semiring: (max, +) instead of (+, *)
    # Matrix multiplication: C[i][j] = max_k (A[i][k] + B[k][j])
    
    # Transition matrix T (2x2):
    # From state A (col 0) or state B (col 1) to state A (row 0) or state B (row 1)
    # T[0][0] = a//2   (A -> A: gain a//2)
    # T[0][1] = a      (B -> A: gain a)
    # T[1][0] = b//2   (A -> B: gain b//2)
    # T[1][1] = b      (B -> B: gain b)
    
    # Initial (day 1):
    # dp_A = a, dp_B = b
    # Then apply T for (N-1) more days.
    
    # For N=1, answer is max(a, b).
    
    if N == 1:
        print(max(a, b))
        return
    
    NEG_INF = float('-inf')
    
    def mat_mult(A, B, size=2):
        # Max-plus matrix multiplication
        C = [[NEG_INF]*size for _ in range(size)]
        for i in range(size):
            for j in range(size):
                for k in range(size):
                    if A[i][k] != NEG_INF and B[k][j] != NEG_INF:
                        C[i][j] = max(C[i][j], A[i][k] + B[k][j])
        return C
    
    def mat_pow(M, p, size=2):
        # Identity for max-plus: 0 on diagonal, -inf elsewhere
        result = [[NEG_INF]*size for _ in range(size)]
        for i in range(size):
            result[i][i] = 0
        while p > 0:
            if p & 1:
                result = mat_mult(result, M, size)
            M = mat_mult(M, M, size)
            p >>= 1
        return result
    
    ha = a // 2
    hb = b // 2
    
    T = [
        [ha, a],
        [hb, b]
    ]
    
    # Apply T^(N-1) to initial vector (a, b)
    Tn = mat_pow(T, N - 1)
    
    # Result vector: for each final state, max over initial states
    # val[j] = max_i (Tn[j][i] + init[i])
    init = [a, b]
    
    best = NEG_INF
    for j in range(2):
        for i in range(2):
            if Tn[j][i] != NEG_INF:
                best = max(best, Tn[j][i] + init[i])
    
    print(best)

solve()

---

This editorial was generated by claude4.6opus-thinking.