CF 2090A - Treasure Hunt

CF 2090A - Treasure Hunt

Rating: 800
Tags: implementation, math
Solve time: 1m 26s
Verified: yes

Solution

Problem Understanding

We are asked to determine who will dig up a buried treasure first between two people, Little B and Little K. The treasure is buried at a fractional depth a.5 meters, which is key: it means the threshold is always .5 meters beyond the integer a. Little B digs x meters each of his days, Little K digs y meters on hers, and they alternate starting with Little B. For each test case, we are to print NO if Little B digs up the treasure first, and YES if Little K does.

The input consists of multiple test cases, each providing the integers x, y, and a. Each value can be as large as 10^9, and there can be up to 1000 test cases. The constraints rule out simulating day-by-day digging because a direct simulation could require billions of iterations in the worst case, which exceeds 1-second limits. The problem is inherently mathematical, and the key is to reason about the cumulative depth and turn order algebraically.

A subtle edge case arises when both dig amounts are equal. For instance, if x = y = 2 and a = 1, the treasure is at 1.5 meters. Little B digs 2 meters on the first day, immediately exceeding 1.5. The naive approach of assuming alternating days without considering partial thresholds might suggest K’s turn matters, but in reality, the first dig is enough. Another edge case occurs when one dig amount is much larger than the other, which can shift the result to the first person regardless of a.

Approaches

The brute-force approach would simulate the digging process day by day. Initialize a counter for the total depth. On each day, add either x or y depending on whose turn it is. After each addition, check if the cumulative depth exceeds a.5. This works correctly but is inefficient for large inputs. Each test case could require up to a/x + a/y iterations, which is up to 10^9 in the worst case. This clearly exceeds the time limit.

The optimal approach arises from observing that we only care about whose day the cumulative depth exceeds a.5, not the exact daily progression. If we normalize the treasure depth to 2a + 1 to avoid fractions, the problem reduces to comparing the scaled sum of the first and second diggers in turns. The key insight is that the parity of the treasure depth with respect to x + y determines the result. Mathematically, if a // (x + y) full cycles of both B and K still leave a remainder greater than x, then Little B digs past the treasure in the next turn; otherwise, Little K does. This reduces each test case to a few integer operations, O(1) time.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(a / min(x, y))	O(1)	Too slow
Optimal	O(1)	O(1)	Accepted

Algorithm Walkthrough

1. Multiply the treasure depth a.5 by 2 to get an integer threshold threshold = 2 * a + 1. This avoids fractions, which simplifies comparisons and arithmetic.
2. Multiply Little B’s daily dig by 2 to get b2 = 2 * x. Multiply Little K’s daily dig by 2 to get k2 = 2 * y. This puts their dig amounts on the same scale as the threshold.
3. Consider alternating turns as repeating cycles of b2 + k2. Compute how many full cycles fit into the threshold with integer division: cycles = threshold // (b2 + k2).
4. Compute the remaining depth after these full cycles: remainder = threshold - cycles * (b2 + k2). This remainder is less than b2 + k2 and represents the final incomplete day.
5. Compare the remainder with b2. If remainder <= b2, it means Little B exceeds the threshold on the next turn, so the answer is NO. Otherwise, Little K reaches it first, and the answer is YES.

Why it works: scaling everything by 2 converts the fractional threshold into an integer problem while preserving the day order. The invariant is that after each full cycle of both diggers, the remaining depth is always handled by one final turn, and comparing it with B’s dig amount determines exactly who crosses the threshold first. There is no ambiguity or off-by-one error because the scale accounts for the .5 meters explicitly.

Python Solution

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    x, y, a = map(int, input().split())
    threshold = 2 * a + 1
    b2 = 2 * x
    k2 = 2 * y
    remainder = threshold % (b2 + k2)
    if remainder <= b2:
        print("NO")
    else:
        print("YES")

The code reads input efficiently using sys.stdin.readline for multiple test cases. The threshold is scaled by 2 to handle the .5 naturally. We only compute the remainder after full cycles to determine the first digger who exceeds it. The comparison <= b2 directly checks if Little B reaches the treasure first.

The subtle points are the scaling to integers and the modulus operation to isolate the last incomplete turn. Omitting either leads to incorrect results for fractional thresholds or very large a.

Worked Examples

Sample Input 1:

1 2 4

Step	Threshold	b2	k2	Remainder	Comparison	Result
Compute	2*4 +1 = 9	2	4	9 % (2+4) = 9 % 6 = 3	3 <= 2? NO	YES

Little B digs 1 meter, K digs 2 meters, repeating. Scaling by 2, the threshold becomes 9, B = 2, K = 4. After one full cycle (B+K=6), remainder is 3. Since 3 > 2, K crosses the threshold first.

Sample Input 2:

2 1 4

Step	Threshold	b2	k2	Remainder	Comparison	Result
Compute	2*4+1=9	4	2	9 % 6 = 3	3 <= 4? YES	NO

Here, B digs more per day than K. The remainder after the first full cycle is 3, which is <= B’s dig, so B reaches the treasure first.

These traces confirm the algorithm correctly scales, reduces cycles, and handles who exceeds the threshold first.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per test case	Only integer arithmetic and modulus operations
Space	O(1)	No extra data structures, only a few integers

Even with the maximum t = 1000 and x, y, a up to 10^9, the solution executes under 1 second because each test case is constant time.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output
    
    t = int(input())
    for _ in range(t):
        x, y, a = map(int, input().split())
        threshold = 2 * a + 1
        b2 = 2 * x
        k2 = 2 * y
        remainder = threshold % (b2 + k2)
        if remainder <= b2:
            print("NO")
        else:
            print("YES")
    
    return output.getvalue().strip()

# Provided samples
assert run("3\n1 2 4\n2 1 4\n2 2 1\n") == "YES\nNO\nNO", "sample tests"

# Custom cases
assert run("1\n1 1 1\n") == "YES", "equal digs, threshold 1.5"
assert run("1\n10 1 1000000000\n") == "NO", "large a, B digs first enough"
assert run("1\n1 10 1000000000\n") == "YES", "large a, K digs more eventually"
assert run("1\n5 5 5\n") == "NO", "equal digs, B digs first"

Test input	Expected output	What it validates
1 1 1	YES	Threshold .5 meters beyond 1, alternating equal digs
10 1 1000000000	NO	B digs enough to cross large depth first
1 10 1000000000	YES	K digs more, will eventually cross first
5 5 5	NO	Equal digs, first digger wins by default

Edge Cases

If x = y and a = 1, threshold is 2*