Contest Python: USACO Bronze › Unit 7 — Simulation & Ad Hoc

Exercises: Unit 7 — Simulation & Ad Hoc

Each problem is a program that reads the whole input from stdin and prints the exact output (real contest style — no solve() wrapper): import sys; data = sys.stdin.read(), parse it, follow the rules, then print. Write each program in a .py file and run it with piped input, e.g. python my_solution.py < case.txt.

Exercise 1: Museum Robot

The first line contains R C, the second line contains a zero-indexed starting row and column, the next R lines form a grid whose open cells contain uppercase letters and whose walls are #, and the final line is a nonempty string of U, D, L, and R commands; for every command, attempt to move one cell in that direction, staying in place if the destination is outside the grid or is a wall, then print the letter in the robot's cell after all commands. In the sample, the first two commands test a wall and the left boundary, and the final U changes the answer from R to M.

Constraints. 1 <= R, C <= 200. 1 <= number of commands <= 200000. The starting cell is open, and every grid row has exactly C characters.

Sample Input

4 5
1 0
ABCDE
F#GHI
JKLMN
OPQRS
RLDDRRRU

Sample Output

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

For parents and teachers: report a problem

Exercise 2: Battery Ticks

The first line contains a battery's positive capacity and starting charge, the second line is N, and the third line contains N integer charge changes in tick order; on each tick add that tick's change to the current charge, immediately replace a result above the capacity with the capacity or a result below 0 with 0, and print the charge after exactly N ticks. In the sample, intermediate ticks hit both limits, so combining the changes first is wrong, and the final -2 changes the answer from 10 to 8.

Constraints. 1 <= capacity <= 1000000000. 0 <= starting charge <= capacity. 1 <= N <= 200000, and -1000000000 <= change <= 1000000000.

Sample Input

10 4
6
9 -3 -20 5 8 -2

Sample Output

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

For parents and teachers: report a problem

Exercise 3: Jumping Event Log

The first line is N, and each of the next N lines contains an event's integer points and positive jump length; begin at event index 0 with score 0, repeatedly add the current event's points and advance the index by that event's jump, and stop when the index is at least N, without deleting or moving any events, then print the score. In the sample, the final visited event is index 6, its 9 points decide the answer, and its jump lands beyond the list to terminate the walk.

Constraints. 1 <= N <= 200000. -1000000000 <= points <= 1000000000. 1 <= jump <= 200000, so every loop pass moves toward termination.

Sample Input

Sample Output

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

without deleting or moving any events

For parents and teachers: report a problem

Exercise 4: Mood Dial

The first line contains the number M of dial positions, a starting position, and N, and the second line contains N nonnegative move sizes; positions are numbered 0 through M - 1, and for each move use the position before that move to choose the direction—move clockwise by adding the size when the position is even, or counterclockwise by subtracting it when the position is odd—then set the new position to (changed position) % M and print the position after all moves. In the sample, moves wrap past both ends of the dial, and the final move changes the answer from 9 to 7.

Constraints. 2 <= M <= 1000000000. 0 <= starting position < M. 1 <= N <= 200000, and 0 <= move size <= 1000000000.

Sample Input

10 2 4
9 4 8 2

Sample Output

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

For parents and teachers: report a problem

Exercise 5: Neighbor Tiles

The first line is a nonempty string of A and B tiles, the second line is N, and the third line contains N zero-indexed positions; process the positions in order, changing only the chosen tile from A to B when it is A, but when it is B, change it to A and then flip its right neighbor if that neighbor exists, and print the entire tile string after all steps. In the sample, the final step chooses the last tile while it is B, so the missing right neighbor is an edge case and that step changes the answer from AABBB to AABBA.

Constraints. 1 <= number of tiles <= 200000. 1 <= N <= 200000. Every position is between 0 and number of tiles - 1.

Sample Input

ABBBA
4
1 2 4 4

Sample Output

AABBA

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

For parents and teachers: report a problem

Exercise 6: Edge-Light Automaton

The first line contains N T, and the second line is a length-N string of 0 and 1; simulate exactly T rounds in which every position is updated at the same time from the previous round, with a missing neighbor beyond either end treated as 0, and with a position becoming 1 when exactly one of its two neighbors is 1 and otherwise becoming 0, then print the string after round T. In the sample, the two ends use missing zero neighbors, and the final round changes the state from 11100 to 10110.

Constraints. 1 <= N <= 500. 1 <= T <= 500. Build each complete next state from the unchanged previous state before starting another round.

Sample Input

5 3
10010

Sample Output

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

simulate exactly T rounds
Build each complete next state from the unchanged previous state before starting another round.

For parents and teachers: report a problem

Exercise 7: Odd-Card Turn Game

The first line is N, and the second line contains N positive card values; Ali begins as the current player with both scores at 0, and on each turn the current player adds the next card to their score, then the turn switches to the other player if that card is odd and stays with the same player if it is even; after every card has been processed, print ALI, BO, or TIE according to the two scores. In the sample, the even cards test the stay rule, the players are tied before the final card, and that final card makes ALI the answer.

Constraints. 1 <= N <= 200000. 1 <= card value <= 1000000000. The final comparison happens only after all N turns.

Sample Input

5
2 1 2 1 3

Sample Output

ALI

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

For parents and teachers: report a problem

Exercise 8: Rolling Grains

Challenge

The first line contains R C K, the next R lines form a grid of empty cells . and fixed walls #, and the final line contains the zero-indexed starting column of each of K grains; drop the grains in input order from row 0, discarding a grain with result -1 if its starting cell is not empty, but otherwise repeatedly move it down when possible, else down-left when possible, else down-right when possible, and otherwise settle it in its current cell and mark that cell occupied for later grains, then print the settling row of the Kth grain or -1 if that grain was discarded. In the sample, earlier grains redirect later ones, the fifth grain reaches the left edge before settling on row 3, and omitting it would leave the fourth grain's row 2 as the wrong result.

Constraints. 2 <= R, C <= 200. 1 <= K <= 20000. Every starting column is between 0 and C - 1, and each downward move increases the row, so each grain terminates.

Sample Input

5 5 5
.....
.....
.....
.....
#####
2 2 2 2 2

Sample Output

How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output word by word.

Your code

For parents and teachers: report a problem

Exercise 9: Turning Ant Automaton

Challenge

The first line contains R C K, the second line contains a zero-indexed starting row, starting column, and one starting direction N, E, S, or W, and the next R lines form a grid of 0 and 1; for each of exactly K steps, inspect the current cell, changing 0 to 1 and turning right in the cycle N, E, S, W, N, or changing 1 to 0 and turning left through that cycle in reverse, then attempt to move one cell in the new direction while staying in place if that move leaves the grid, and after all steps print the number of 1 cells. In the sample, the final step both toggles a cell and attempts to move north beyond row 0, changing the answer from its step-17 value to 5.

Constraints. 1 <= R, C <= 100. 1 <= K <= 200000. Turn and change the current cell before attempting the move, and process all K steps even after a blocked move.

Sample Input

Sample Output

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

For parents and teachers: report a problem

Back to Unit 7 — Simulation & Ad Hoc