Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
A school team "Cows" is trying to assign jerseys numbered `1,2,…,N` to players.
The size of each jersey is either small (S), medium (M) or large (L).
Each player has requested a specific jersey number and a preferred size. The players will not be
satisfied with a jersey that is the wrong number or that is smaller than their preferred size.
They will be satisfied with a jersey that is their preferred size or larger as long as it is the right number.
Two players cannot be given the same jersey.
Your task is to determine the maximum number of requests that can be satisfied.
The first line of input is the integer `N` (`1\ ≤\ N\ ≤\ 1000000`) which is the number of jerseys.
The second line of input is the integer `M` (`1\ ≤\ M\ ≤\ 1000000`) which is the number of players.
The next `N` lines are each the character S, M or L.
Line `j` gives the size of jersey `j` (`1\ ≤\ j\ ≤\ N`). The last `M` lines are each
the character S, M or L followed by a space followed by an integer.
Line `i` (`1\ ≤\ i\ ≤\ M`) gives the requested size and jersey number `k` (`1\ ≤\ k\ ≤\ N`) for player `i`.
The output will consist of a single integer which is the maximum number of requests that can be
satisfied.
Sample Input #1
4
3
M
S
S
L
L 3
S 3
L 1
Sample Input #2
1
2
M
M 1
S 1
Explanation Sample Output
Jersey 1 cannot be assigned because it is medium and player 3 requested large. No player requested
jersey 2 or 4. Jersey 3 (small) can be assigned player 2 (small) but not player 1 (large).