BidirectionalQueue
TCO09 Qual 3 · 2009-02-24 · by Nickolas
TCO09 Qual 3 · 2009-02-24 · by Nickolas · Simulation
Problem Statement
Problem Statement
You are given a bidirectional cyclical queue which contains N elements. You need to extract several elements from this queue.
You can do 3 kinds of operations with this queue:int[] indices which contains the initial (1-based) positions of wanted elements in the queue. Return the minimal number of left and right shifts you'll have to perform to extract the wanted elements in the given order.
You can do 3 kinds of operations with this queue:
- Extract first element. After applying this operation, queue a1, ..., aK becomes a2, ..., aK.
- Shift queue elements left. After applying this operation, queue a1, ..., aK becomes a2, ..., aK, a1.
- Shift queue elements right. After applying this operation, queue a1, ..., aK becomes aK, a1, ..., aK-1.
Constraints
- N will be between 1 and 50, inclusive.
- indices will contain between 1 and N elements, inclusive.
- Each element of indices will be between 1 and N, inclusive.
- All elements of indices will be distinct.
Examples
0)
10
{1, 2, 3}
Returns: 0
The elements are extracted in the same order as they appear in the queue, so no shifts are required.
1)
10
{2, 9, 5}
Returns: 8
To extract the first wanted element, 1 left shift is required. After this the next wanted element will be 7th in a queue with 9 elements, so to extract it 3 right shifts are required. Finally, the last wanted element will be 5th in a queue with 8 elements, so either 4 left shifts or 4 right shifts are required.
2)
50
{26, 1, 27, 2, 28, 3, 29, 4, 30, 5, 31, 6, 32, 7, 33, 8, 34, 9, 35, 10, 36, 11, 37, 12, 38, 13, 39, 14, 40, 15, 41, 16, 42, 17, 43, 18, 44, 19, 45, 20, 46, 21, 47, 22, 48, 23, 49, 24, 50, 25}
Returns: 625
3)
1
{1}
Returns: 0
4)
32
{27, 16, 30, 11, 6, 23}
Returns: 59
Submissions are judged against all 94 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BidirectionalQueue with a public method int extractElements(int N, vector<int> indices) · 94 test cases · 2 s / 256 MB per case