FoxAndFencing

SRM 598 · 2013-06-25 · by cgy4ever

SRM 598 · 2013-06-25 · by cgy4ever · Greedy, Math

Show categories

Class Name: FoxAndFencing

Return Type: String

Method Name: WhoCanWin

Arg Types: (int, int, int, int, int)

Problem Statement

Fox Ciel is playing a board game with her friend Squirrel Liss. The game is played on an infinite strip of paper. The strip of paper is divided into consecutive cells. Each cell has an integer coordinate. Formally, for each integer i, the left neighbor of cell i is cell (i-1) and the right neighbor of cell i is cell (i+1).

Each of the players has a single token called the fencer. At the beginning of the game, Ciel's fencer is in cell 0 and Liss's fencer is in cell d. Each of the fencers has two limits: its maximum move length and its hitting range. For Ciel's fencer the maximum move length is mov1 and the hitting range is rng1. Similarly, for Liss's fencer we have the parameters mov2 and rng2. Note that the parameters of Liss's fencer may differ from the ones of Ciel's fencer.

The players take alternating turns. Ciel goes first. In each turn the current player starts by moving her fencer. The distance between the original cell and the destination cell must be at most equal to the fencer's maximum move length. (It is also allowed to leave the fencer in the same cell.) Then, the current player checks whether the other fencer lies within the hitting range - that is, whether the current distance between the fencers is at most equal to the current fencer's hitting range. If that is the case, the game ends and the current player wins.

You are given the ints mov1, mov2, rng1, rng2, and d. Return "Ciel" (quotes for clarity) if Fox Ciel has a winning strategy, "Liss" if Squirrel Liss has a winning strategy, and "Draw" otherwise.

Constraints

mov1 will be between 1 and 100,000,000, inclusive.
mov2 will be between 1 and 100,000,000, inclusive.
rng1 will be between 1 and 100,000,000, inclusive.
rng2 will be between 1 and 100,000,000, inclusive.
d will be between 1 and 100,000,000, inclusive.

Examples

1
58
1
58
2
Returns: "Ciel"

The attributes of Ciel's fencer are much smaller than the attributes of Liss's fencer. Luckily for Ciel, she can win the game in her first turn: she should move her fencer to cell 1 and from there she can hit the other fencer.

2
1
1
100
50
Returns: "Liss"

Ciel cannot score a hit in the first turn. After Ciel's turn, her fencer will be on one of the cells {-2,-1,0,1,2}. Regardless of its precise location, Liss can always move her fencer one cell to the left and then hit Ciel.

2
1
1
100
150
Returns: "Draw"

Clearly, Ciel has no chance of winning this game. However, this time the initial distance d is big enough for Ciel to escape.

100
100
100
100
100000000
Returns: "Draw"

100
1
100
1
100000000
Returns: "Ciel"

Submissions are judged against all 258 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FoxAndFencing with a public method string WhoCanWin(int mov1, int mov2, int rng1, int rng2, int d) · 258 test cases · 2 s / 256 MB per case