SortMachine
SRM 306 · 2006-06-08 · by soul-net
Problem Statement
We have a sorting machine that works on a list of distinct numbers. This machine only has one instruction named MOVE that takes one element of the list as a parameter. The MOVE instruction removes the element from the list and then appends it to the end of the remaining list.
For example, the sequence {19,7,8,25} can be sorted in ascending order using 2 instructions:
MOVE 19, to get {7,8,25,19}
MOVE 25, to get {7,8,19,25}
You will be given a
Constraints
- a will have between 1 and 50 elements, inclusive.
- Each element of a will be between -1000 and 1000, inclusive.
- All elements of a will be distinct.
{19,7,8,25}
Returns: 2
The example from the problem statement.
{1,2,3,4,5}
Returns: 0
This list is already sorted, so no instructions are needed.
{1000,-1000,0}
Returns: 1
This list can be sorted with a single instruction: MOVE 1000.
{2,1,3,4,5,6,7,8,9}
Returns: 8
{4,5,1,6,7,2,8,9,3,10,11}
Returns: 8
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SortMachine with a public method int countMoves(vector<int> a) · 107 test cases · 2 s / 256 MB per case