2D Array and Operations
Time limit0.5sMemory limit512 MB
Simulate up to 100 seconds of row-sorting or column-sorting on a 3x3 grid, where each sort replaces values by (value, frequency) pairs, and report when A[r][c] becomes k.
- Level
Medium6 of 10
- Topics
- Simulation, Implementation, Sorting, Array
- Solved
- No attempts yet
Problem
There is a 3×3 array A. The indices of the array start at 1. Every second, an operation is applied to the array.
- R operation: sort every row of array A. This is applied when the number of rows ≥ the number of columns.
- C operation: sort every column of array A. This is applied when the number of rows < the number of columns.
To sort the numbers in a row or column, you need to know how many times each number appears. Then sort by increasing count of occurrences, and if several numbers share the same count, sort by increasing value. Then put the sorted result back into array A. When putting the sorted result into the array, put both the number and its count of occurrences, with the number first.
For example, in [3, 1, 1], 3 appears once and 1 appears twice. Therefore the sorted result is [3, 1, 1, 2]. In this array, 3 appears once, 1 appears twice, and 2 appears once. Sorting again gives [2, 1, 3, 1, 1, 2].
Putting the sorted result back into the array may change the size of a row or column. When the R operation is applied, the size of every row changes based on the largest row, and when the C operation is applied, the size of every column changes based on the largest column. Positions where the size of a row or column has grown are filled with 0. When sorting numbers, 0 must be ignored. For example, the result of sorting [3, 2, 0, 0] is the same as the result of sorting [3, 2].
If the size of a row or column exceeds 100, everything after the first 100 elements is discarded.
Given the numbers in array A and r, c, k, find the minimum time for the value at A[r][c] to become k.
Input
The first line gives r, c, k. (1 ≤ r, c, k ≤ 100)
The next 3 lines give the numbers in array A. The numbers in array A are natural numbers less than or equal to 100.
Output
Print the minimum time for the value at A[r][c] to become k. If A[r][c] = k is not reached even after 100 seconds, print -1.
Hint
Consider the case where the initial values of array A are as follows.
1 2 1
2 1 3
3 3 3
At first the number of rows ≥ the number of columns, so the R operation is applied. For convenience, the intermediate sorting step is expressed as (number, count of the number).
1 2 1 → (2, 1), (1, 2) → 2 1 1 2
2 1 3 → (1, 1), (2, 1), (3, 1) → 1 1 2 1 3 1
3 3 3 → (3, 3) → 3 3
The row with the largest size is row 2, and 0 must be appended to the other rows.
2 1 1 2 0 0
1 1 2 1 3 1
3 3 0 0 0 0
The operation applied next is the C operation because the number of rows < the number of columns.
1 3 1 1 3 1
1 1 1 1 1 1
2 1 2 2 0 0
1 2 1 1 0 0
3 0 0 0 0 0
1 0 0 0 0 0
The result of applying the operation is as above.