Project Euler Problem 950

Solution

Answer: 429162542

A key observation is that with equal bloodthirstiness $p=\frac1{\sqrt{C}}$, the pirates’ decision rule becomes a threshold comparison between:

surviving later with additional plank-walks (worth $p\cdot \Delta w$),
versus accepting a bribe of coins now.

For irrational $p$, ties never occur, which makes the equilibrium deterministic.

Let $L$ be a pirate count where the senior pirate survives. Between such “reset” points, every new senior pirate is doomed, creating long deterministic death cascades where:

$w(n)$ increases linearly,
$c(n)$ stays constant,
the next survival point can be derived from an integer feasibility inequality involving

$$\left\lceil \frac{d}{\sqrt{C}} \right\rceil,$$

where $d$ is the distance to the next reset.

This reduces the problem from impossible $O(N)$ simulation ($N=10^{16}$) to roughly $O(\sqrt{C}\log N)$ behavior by jumping between reset states.

The following Python computes the exact value and reproduces all supplied checks:

from math import isqrt

MOD = 10**9

def floor_div_sqrt(d, D):
    if d <= 0:
        return 0
    dd = d * d
    t = isqrt(dd // D)

    while (t + 1) * (t + 1) * D <= dd:
        t += 1
    while t * t * D > dd:
        t -= 1

    return t

def ceil_div_sqrt(d, D):
    if d <= 0:
        return 0
    return floor_div_sqrt(d, D) + 1

def initial_prefix_sum(N, C):
    M = min(N, 2 * C)

    if M <= 0:
        return 0

    m = M // 2
    total = 2 * (m * C - (m * (m - 1)) // 2)

    if M % 2 == 1:
        total += C - m

    return total

def next_reset(L, C, D):
    if C == 0:
        return 2 * L

    t = 1
    while t <= C:
        y = C // t
        x = 2 * L - 2 * y
        d = x - L

        if d > 0:
            s = ceil_div_sqrt(d, D)
            if C // s == y:
                return x

        t = (C // y) + 1

    return 2 * L

def T(N, C, D):
    start_reset = 2 * C + 2

    if N <= start_reset:
        return initial_prefix_sum(N, C)

    total = initial_prefix_sum(start_reset, C)

    L = start_reset
    cL = 0

    while L < N:
        x = next_reset(L, C, D)

        if x > N:
            d = N - L + 1
            total += (d - 1) * cL + (d - 1) * d // 2
            break

        d = x - L

        if d > 1:
            total += (d - 1) * cL + (d - 1) * d // 2

        required_votes = (x + 1) // 2
        free_votes = d
        need_bribes = max(required_votes - free_votes, 0)

        s = ceil_div_sqrt(d, D)
        cost = need_bribes * s

        cL = C - cost
        total += cL

        L = x

    return total

# Verification
assert T(30, 3, 3) == 190
assert T(50, 3, 31) == 385
assert T(10**3, 101, 101) == 142427

N = 10**16
ans = 0

for k in range(1, 7):
    C = 10**k + 1
    ans += T(N, C, C)

ans %= 10**9
print(ans)

The computation yields:

Answer: 429162542