1084 Highway Lite

Description

Note: this is a simplified version of "Highway"

Overview

In this problem you are asked to implement a simplistic highway simulation. The 'highway' is (rows x cols) grid of cells that can be occupied by a vehicle or not. All traffic starts at the left side of of the grid (at column 0) and travels right on, never switching lane (i.e., row). If a car moves beyond the last column it exits the simulation. As input you will be given a list of arrival times of vehicles, the goal is to produce the state of the highway after a specified number of simulation steps.

The Highway

The highway is a (rows x cols) grid, where row 0 corresponds to the topmost lane, and column 0 is the leftmost segment. I.e., a 3 lane highway of 10 segments looks like this:

.......... <- row 0, is the topmost lane
..........
..........

^
|
column 0, is the leftmost segment

Vehicles

In this version, there is just 1 vehicle type: all vehicles get to move 1 step to the right in each time step.

Movement, Priorities & Arrivals

The simulation is executed in discrete time steps. Each step consists of 2 phases:

1)the movement phase, and
2)the arrival phase.

In the movement phase, all the vehicles that are already on the highway get to move. They do not move synchronous, but one after another: vehicles that entered the simulation first get to move first.

After all vehicles already on the board have been given the opportunity to move, new vehicles can arrive. These are read from a list that serves as the program input.

Detailed 1 lane Example

Here we provide a detailed example of how the simulation should be executed. Suppose this is the input:

1 50 40
2 0
5 0
9 0
11 0
14 0
20 0
21 0
22 0
23 0
24 0
25 0
26 0
28 0
30 0
32 0
34 0
36 0
38 0

Then the following simulation should occur:

(Note, the line after the indicated time step shows the state at the beginning of that time step. So, the first car arrives in the arrival phase of timestep t=2 and therefore is shown at the beginning of time step t=3)

t=0
..................................................
t=1
..................................................
t=2
..................................................
t=3 1.................................................
t=4
.1................................................
t=5
..1...............................................
t=6 1..1..............................................
t=7
.1..1.............................................
t=8
..1..1............................................
t=9
...1..1........................................... t=10
1...1..1.......................................... t=11
.1...1..1......................................... t=12
1.1...1..1........................................ t=13
.1.1...1..1....................................... t=14
..1.1...1..1...................................... t=15
1..1.1...1..1..................................... t=16
.1..1.1...1..1.................................... t=17
..1..1.1...1..1................................... t=18
...1..1.1...1..1.................................. t=19
....1..1.1...1..1................................. t=20
.....1..1.1...1..1................................ t=21
1.....1..1.1...1..1...............................
t=22 11.....1..1.1...1..1..............................
t=23 111.....1..1.1...1..1.............................
t=24 1111.....1..1.1...1..1............................
t=25 11111.....1..1.1...1..1...........................
t=26 111111.....1..1.1...1..1..........................
t=27 1111111.....1..1.1...1..1......................... t=28
.1111111.....1..1.1...1..1........................
t=29
1.1111111.....1..1.1...1..1....................... t=30
.1.1111111.....1..1.1...1..1...................... t=31
1.1.1111111.....1..1.1...1..1..................... t=32
.1.1.1111111.....1..1.1...1..1.................... t=33
1.1.1.1111111.....1..1.1...1..1................... t=34
.1.1.1.1111111.....1..1.1...1..1..................
t=35 1.1.1.1.1111111.....1..1.1...1..1................. t=36
.1.1.1.1.1111111.....1..1.1...1..1................
t=37 1.1.1.1.1.1111111.....1..1.1...1..1............... t=38
.1.1.1.1.1.1111111.....1..1.1...1..1.............. t=39
1.1.1.1.1.1.1111111.....1..1.1...1..1............. t=40
.1.1.1.1.1.1.1111111.....1..1.1...1..1............

As such, the requested output in this case would be:

.1.1.1.1.1.1.1111111.....1..1.1...1..1............

Input

First a row with 3 integers:

number_of_rows number_of_colums number_of_timesteps

that specify the size of the highway and the number of steps to simulate.

This is followed by the aforementioned list of arrivals. Each entry is a row with 2 integers:

arrival_time row_index

• These rows will be ordered based on arrival time.

Output

The state of the highway after number_of_timesteps have been simulated, encoded as follows:

'.' denotes empty space
'1' denotes a vehicle

Sample Input

5 10 20
0 1
0 3
0 4
2 4
4 3
4 4
6 3
6 4
10 0
10 1
12 2
12 4
18 1

Sample Output

.........1
.1.......1
.......1..
..........
.......1..