Stone Game IV
Real-world version: Square Cut Cable DuelThe statement here is our own: the same inputs, outputs and technique.
Two riggers, Ada and Boaz, share one spool holding n whole metres of cable. Ada acts first and then they act alternately.
On a turn the rigger whose turn it is must cut away exactly k * k metres for some positive whole number k. The cut may not exceed what is left on the spool, and skipping a turn is not allowed. A rigger who starts a turn with an empty spool has no legal cut and loses the duel.
Both riggers see the whole spool and never misplay. Return True when Ada can win against every defence, and False when Boaz can.
Examples
Example 1
- Input
- n = 83
- Output
- true
Ada opens by cutting 16 metres, and from the length that is left she has an answer to every defence Boaz plays, so Boaz is the rigger who eventually starts a turn with nothing to cut. An opening cut of 81 metres also wins for her.
Example 2
- Input
- n = 39
- Output
- false
Ada has only a handful of legal openings from 39 metres, and Boaz forces the win after each of them.
Example 3
- Input
- n = 30
- Output
- true
Ada opens by cutting 25 metres, leaving 5 metres on the spool, and wins from there.
Constraints
- 1 <= n <= 10^5
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def winner_square_game(n: int) -> bool:public boolean winnerSquareGame(int n)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's