Trains crossing the Milky Way
Time limit1sMemory limit512 MB
Simulate four seat operations across N trains, then count how many trains have a seating state that appears for the first time.
- Level
Medium4 of 10
- Topics
- Simulation, Hash map, Bit manipulation, Implementation
- Solved
- No attempts yet
Problem
N trains are about to pierce the darkness and cross the Milky Way.
A train has 20 seats in a single row, and one seat holds one person.
The trains are numbered 1 to N, and M commands are given, each aimed at one train.
There are four kinds of commands.
1 i x: seat a person in seat x (1 ≤ x ≤ 20) of train i (1 ≤ i ≤ N). If someone is already sitting there, nothing happens.2 i x: the person sitting in seat x of train i gets off. If nobody was sitting there, nothing happens.3 i: every passenger on train i moves back one seat. A person in seat k moves to seat k+1. If someone was sitting in seat 20, that person gets off after this command.4 i: every passenger on train i moves forward one seat. A person in seat k moves to seat k-1. If someone was sitting in seat 1, that person gets off after this command.
After all M commands are processed, the trains cross the Milky Way one at a time in order from train 1, with one condition. As each train passes, its seating state is recorded in a list, and a train whose state already appears in the list cannot cross.
For example, in the picture below the state of train 1 has not been recorded yet, so train 1 crosses. The state of train 2 has not been recorded either, so train 2 also crosses. Train 3 has the same seating state as train 1, so it cannot cross.
No one is on board any train at the start.
Find how many trains can cross the Milky Way.
Input
The first line contains the number of trains N (1 ≤ N ≤ 100000) and the number of commands M (1 ≤ M ≤ 100000). Each of the next M lines, from the second line through line M+1, contains one command.
Output
Print how many trains can cross the Milky Way.