IOI '21 P5 - Dungeons Game

View as PDF

Points: 30 (partial)
Time limit: 4.0s
Memory limit: 1G

Problem types
Allowed languages
C++

Robert is designing a new computer game. The game involves one hero, opponents and dungeons. The opponents are numbered from to and the dungeons are numbered from to . Opponent is located in dungeon and has strength . There is no opponent in dungeon .

The hero starts off entering dungeon , with strength . Every time the hero enters any dungeon , they confront opponent , and one of the following occurs:

• If the hero's strength is greater than or equal to the opponent's strength , the hero wins. This causes the hero's strength to increase by . In this case the hero enters dungeon next .
• Otherwise, the hero loses. This causes the hero's strength to increase by . In this case the hero enters dungeon next.

Note may be less than, equal to, or greater than . Also, may be less than, equal to, or greater than . Regardless of the outcome of the confrontation, the opponent remains in dungeon and maintains strength .

The game ends when the hero enters dungeon . One can show that the game ends after a finite number of confrontations, regardless of the hero's starting dungeon and strength.

Robert asked you to test his game by running simulations. For each simulation, Robert defines a starting dungeon and starting strength . Your task is to find out, for each simulation, the hero's strength when the game ends.

Implementation Details

You should implement the following procedures:

void init(int n, int[] s, int[] p, int[] w, int[] l)

• : number of opponents.
• , , , : arrays of length . For :
• is the strength of the opponent . It is also the strength gained by the hero after winning against opponent .
• is the strength gained by the hero after losing against opponent .
• is the dungeon the hero enters after winning against opponent .
• is the dungeon the hero enters after losing against opponent .
• This procedure is called exactly once, before any calls to simulate (see below).
int64 simulate(int x, int z)

• : the dungeon the hero enters first.
• : the hero's starting strength.
• This procedure should return the hero's strength when the game ends, assuming the hero starts the game by entering dungeon , having strength .
• The procedure is called exactly times.

Examples

Consider the following call:

init(3, [2, 6, 9], [3, 1, 2], [2, 2, 3], [1, 0, 1])


The diagram above illustrates this call. Each square shows a dungeon. For dungeons , and , the values and are indicated inside the squares. Magenta arrows indicate where the hero moves after winning a confrontation, while black arrows indicate where the hero moves after losing.

Let's say the grader calls simulate(0, 1).

The game proceeds as follows:

Dungeon Hero's strength before confrontation Result
Lose
Lose
Win
Lose
Win
Win
Game ends

As such, the procedure should return .

Let's say the grader calls simulate(2, 3).

The game proceeds as follows:

Dungeon Hero's strength before confrontation Result
Lose
Lose
Win
Lose
Win
Win
Game ends

As such, the procedure should return .

Constraints

• for all
• for all
• for all

1. ( points) for all
2. ( points) for all
3. ( points) , all opponents have the same strength, in other words, for all .
4. ( points) , there are at most distinct values among all values of .
5. ( points)
6. ( points) No additional constraints.

• line :
• line :
• line :
• line :
• line :
• line : for the -th call to simulate.

• line : the return value of the -th call to simulate.