Can Leo just stand at the location of the possible chest that is closer to $$$a$$$? What if $$$x$$$ and $$$y$$$ are in opposite directions from $$$a$$$?

For Leo to beat Maya, he must pick a starting position $$$z$$$ that is strictly closer to $$$x$$$ than $$$a$$$ is, AND strictly closer to $$$y$$$ than $$$a$$$ is.

If $$$x$$$ and $$$y$$$ are on the same side of $$$a$$$ (e.g., $$$a \lt x$$$ and $$$a \lt y$$$), Leo can simply start at the chest position that is closest to $$$a$$$. For instance, if $$$a \lt x \lt y$$$, Leo can choose $$$z = x$$$. His distance to $$$x$$$ will be $$$0 \lt |a-x|$$$, and his distance to $$$y$$$ will be $$$y-x$$$, which is strictly less than Maya's distance of $$$y-a$$$. In this case, Leo is guaranteed to win.

If $$$x$$$ and $$$y$$$ are on opposite sides of $$$a$$$ (e.g., $$$x \lt a \lt y$$$), any position $$$z$$$ that is strictly closer to $$$x$$$ than $$$a$$$ must satisfy $$$z \lt a$$$. However, any position strictly closer to $$$y$$$ than $$$a$$$ must satisfy $$$z \gt a$$$. It is mathematically impossible for $$$z$$$ to be both strictly less than and strictly greater than $$$a$$$ simultaneously.

Thus, the answer is YES if and only if $$$x$$$ and $$$y$$$ are on the same side of $$$a$$$, which can be checked using the condition (x < a) == (y < a) or (x - a) * (y - a) > 0.

• Time Complexity: $$$O(1)$$$ per test case.
• Space Complexity: $$$O(1)$$$

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data: return
    t = int(input_data[0])
    out = []
    for i in range(1, 3 * t, 3):
        a, x, y = int(input_data[i]), int(input_data[i+1]), int(input_data[i+2])
        if (x < a) == (y < a):
            out.append("YES")
        else:
            out.append("NO")
    print("\n".join(out))

if __name__ == '__main__':
    solve()

When $$$n$$$ is odd, how many moves does Aqua make? Which positions can she mark? What does this mean for the final remaining digit?

The game depends entirely on the parity of $$$n$$$.

• If $$$n$$$ is odd: A total of $$$n-1$$$ turns will be made. Since $$$n-1$$$ is even, Ignis and Aqua will each make exactly $$$\frac{n-1}{2}$$$ moves. However, there are exactly $$$\frac{n-1}{2}$$$ even positions in the number. This means Aqua is forced to mark every single even position, so the last remaining digit is guaranteed to be on an odd position. Ignis gets to choose which odd position to save. If there is at least one odd digit on any odd position, Ignis can simply mark all other odd positions and win. If all digits on odd positions are even, Ignis will lose.
• If $$$n$$$ is even: The logic flips. Ignis will make $$$\frac{n}{2}$$$ moves and Aqua will make $$$\frac{n-2}{2}$$$ moves. Since there are $$$\frac{n}{2}$$$ odd positions, Ignis is forced to mark all of them, meaning the final digit will definitely come from an even position. Aqua gets to pick which one survives. If there is at least one even digit on an even position, Aqua will save it and win. Otherwise, Ignis wins.

• Time Complexity: $$$O(n)$$$ per round.

• Space Complexity: $$$O(n)$$$ or $$$O(1)$$$ to store the string.

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data: return
    t = int(input_data[0])
    idx = 1
    out = []
    for _ in range(t):
        n = int(input_data[idx])
        s = input_data[idx+1]
        idx += 2
        
        if n % 2 != 0:
            ignis_wins = False
            for i in range(0, n, 2):
                if int(s[i]) % 2 != 0:
                    ignis_wins = True
                    break
            out.append("1" if ignis_wins else "2")
        else:
            aqua_wins = False
            for i in range(1, n, 2):
                if int(s[i]) % 2 == 0:
                    aqua_wins = True
                    break
            out.append("2" if aqua_wins else "1")
            
    print("\n".join(out))

if __name__ == '__main__':
    solve()

If a beast starts at position $$$x$$$, how many seconds do you have to kill it? Does the side (left or right) matter?

Every beast essentially acts as a job with a strict deadline. A beast at position $$$x_i$$$ will reach the shrine in exactly $$$|x_i|$$$ seconds. Since we want to stop it before it reaches the shrine, we must fully deplete its endurance within the first $$$|x_i|$$$ seconds.

The side from which a beast approaches doesn't matter; only its absolute distance $$$d_i = |x_i|$$$ matters.

Because we can distribute our $$$k$$$ arrows completely arbitrarily each second, we just need to make sure we aren't overwhelmed at any point. By second $$$d$$$, we can fire at most $$$d \times k$$$ arrows in total. Therefore, the total endurance of all beasts that started at distance $$$d$$$ or closer must not exceed $$$d \times k$$$.

We can simply group the beasts by their initial absolute distance, compute the prefix sums of their endurances, and check if $$$S_d \le d \times k$$$ holds for all $$$d \in [1, n]$$$. If it holds for all distances, the answer is YES. Otherwise, it is NO.

• Time Complexity: $$$O(n)$$$ per test case.
• Space Complexity: $$$O(n)$$$ to store the accumulated endurances.

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data: return
    t = int(input_data[0])
    idx = 1
    out = []
    
    for _ in range(t):
        n = int(input_data[idx])
        k = int(input_data[idx+1])
        idx += 2
        
        endurance_at_dist = [0] * (n + 1)
        
        a = []
        for _ in range(n):
            a.append(int(input_data[idx]))
            idx += 1
            
        for i in range(n):
            x = int(input_data[idx])
            idx += 1
            dist = abs(x)
            if dist <= n:
                endurance_at_dist[dist] += a[i]
                
        possible = True
        current_sum = 0
        for d in range(1, n + 1):
            current_sum += endurance_at_dist[d]
            if current_sum > d * k:
                possible = False
                break
                
        if possible:
            out.append("YES")
        else:
            out.append("NO")
            
    print("\n".join(out))

if __name__ == '__main__':
    solve()

If you have two separate segments of crystals, you have two choices: detonate them separately, or plant crystals in the gap between them to connect them into a single segment. Which choice is better?

First, if there are no crystals in the kingdom (the string is all 0s), the cost is obviously 0. Otherwise, we can group the 1s into contiguous segments. For example, 01100101 has 3 segments of 1s.

To clear the first segment, we must pay $$$a$$$ coins to detonate it. For every subsequent segment, we have a choice: 1. Treat it as a separate segment and pay another $$$a$$$ coins to detonate it. 2. Bridge the gap between it and the previous segment by planting crystals. If the gap consists of $$$L$$$ zeros, this costs $$$L \times b$$$ coins, and effectively merges the two segments so they can be detonated together with the previous one.

Naturally, we should choose the cheaper option for each gap. Thus, for each gap of length $$$L$$$ between two segments of 1s, we add $$$\min(a, L \times b)$$$ to our total cost.

• Time Complexity: $$$O(n)$$$ to parse the string.
• Space Complexity: $$$O(n)$$$ or $$$O(1)$$$ to store the string and count gaps.

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data: return
    t = int(input_data[0])
    idx = 1
    out = []
    
    for _ in range(t):
        a = int(input_data[idx])
        b = int(input_data[idx+1])
        s = input_data[idx+2]
        idx += 3
        
        first_one = s.find('1')
        if first_one == -1:
            out.append("0")
            continue
            
        last_one = s.rfind('1')
        
        ans = a
        current_zero_len = 0
        
        for i in range(first_one, last_one + 1):
            if s[i] == '0':
                current_zero_len += 1
            else:
                if current_zero_len > 0:
                    ans += min(a, current_zero_len * b)
                    current_zero_len = 0
                    
        out.append(str(ans))
        
    print("\n".join(out))

if __name__ == '__main__':
    solve()

Can you rephrase the problem in terms of intervals? Every time a seal matches a part of the scroll, it covers a specific range $$$[L, R]$$$. The goal is to cover the entire range $$$[1, |t|]$$$ with the minimum number of intervals.

This problem boils down to finding all occurrences of all seals in the scroll $$$t$$$, turning them into intervals, and then solving the classic "Minimum Interval Cover" problem.

1. String Matching: For each seal $$$s_i$$$, we can slide a window across $$$t$$$ to find all starting positions where $$$s_i$$$ exactly matches a substring of $$$t$$$. If it matches starting at position $$$p$$$, it covers the interval $$$[p, p + |s_i| - 1]$$$. We collect all such intervals.
2. Greedy Coverage: We want to cover the interval $$$[1, |t|]$$$. We maintain a variable covered (initially 0), meaning we have covered everything up to index covered. At each step, we look at all available intervals $$$[L, R]$$$ that start within or immediately after our covered region (i.e., $$$L \le \text{covered} + 1$$$). Among all these valid candidates, we greedily pick the one that extends our coverage the furthest (i.e., the one with the maximum $$$R$$$). We then update covered = R and record this seal and its position. We repeat this process until covered $$$\ge |t|$$$.

If at any point no valid interval can extend our coverage (all valid intervals have $$$R \le \text{covered}$$$), it means there is a gap we can never stain, so we output -1.

• Time Complexity: $$$O(|t| \cdot \sum |s_i|)$$$ for string matching, and $$$O(K \log K)$$$ or $$$O(K \cdot |t|)$$$ for the greedy step, where $$$K$$$ is the number of valid occurrences. Given the small constraints, this is practically instantaneous.
• Space Complexity: $$$O(K)$$$ to store the intervals.

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data: return
    q = int(input_data[0])
    idx = 1
    out = []
    
    for _ in range(q):
        t_str = input_data[idx]
        n = int(input_data[idx+1])
        idx += 2
        
        seals = []
        for _ in range(n):
            seals.append(input_data[idx])
            idx += 1
            
        intervals = []
        for i, s in enumerate(seals):
            seal_len = len(s)
            for j in range(len(t_str) - seal_len + 1):
                if t_str[j:j+seal_len] == s:
                    intervals.append((j + 1, j + seal_len, i + 1, j + 1))
                    
        covered = 0
        ans = []
        possible = True
        
        while covered < len(t_str):
            best_r = -1
            best_seal = -1
            best_pos = -1
            
            for L, R, seal_idx, pos in intervals:
                if L <= covered + 1:
                    if R > best_r:
                        best_r = R
                        best_seal = seal_idx
                        best_pos = pos
                        
            if best_r <= covered:
                possible = False
                break
                
            ans.append((best_seal, best_pos))
            covered = best_r
            
        if not possible:
            out.append("-1")
        else:
            out.append(str(len(ans)))
            for seal_idx, pos in ans:
                out.append(f"{seal_idx} {pos}")
                
    print("\n".join(out))

if __name__ == '__main__':
    solve()