Reversing Four Deck Blocks
National Olympiad — National round (2015 season)
Submission name: blackd.cpp
Problem summary
Split a deck into four positive consecutive blocks and rebuild them in reverse block order without reversing cards within a block. After repeated splits, find the top card. Initially cards are numbered from the bottom.
Input
N M followed by M triples p q r; the last block length is N−p−q−r.
Output
The final first card label.
Constraints
1 ≤ N,M ≤ 52; every supplied split has four positive lengths.
Worked example
Input and output for the worked example discussed below.
Input
52 5 21 23 3 5 21 21 13 13 13 35 7 7 15 15 11
Output
23
Solution analysis
- Represent the deck top to bottom, initially N,N−1,…,1 because numbering starts at the last card. Explicit simulation is tiny at the stated sizes.
- Compute cut boundaries 0,p,p+q,p+q+r,N. Copy slices four, three, two, one into a new vector, retaining their individual internal order, then replace the deck.
- After the five sample cuts, the first label is 23. A fresh vector prevents overwriting cards that still need copying. The fourth size is inferred from N rather than read.
Why it works
The initial vector follows the numbering convention. Every replacement copies exactly the prescribed blocks in the prescribed order. Induction over splits proves the final vector matches the actual deck and its first entry is the answer.
Watch out. Reverse blocks, not individual cards. Start with N at the top. Do not read a fourth block length.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int count;
int splits;
cin>>count>>splits;
vector<int>deck(count);
for(int i=0;i<count;i++){
deck[i]=count-i;
}
for(int i=0;i<splits;i++){
int p;
int q;
int r;
cin>>p>>q>>r;
int cut[5]={0,p,p+q,p+q+r,count};
vector<int>next;
next.reserve(count);
// Whole blocks move, but their own card order stays unchanged.
for(int block=3;block>=0;block--){
next.insert(next.end(),deck.begin()+cut[block],deck.begin()+cut[block+1]);
}
deck=next;
}
cout<<deck.front()<<'\n';
}