Black Peter Card Cuts
National Olympiad — National round (2015 season)
Submission name: blackp.cpp
Problem summary
Start with a deck ordered n, n−1, …, 1 from top to bottom, as in the official example. A cut removes c consecutive cards beginning at position p (one-based) and places that block on top without changing its order. Find the top card after r cuts.
Source clarification. The prose says the deck is numbered 1…n starting at the top, but the official worked example explicitly starts at n…1 and its output 4 requires that decreasing order. This solution follows the example; an ascending initial deck would produce 2 for the same input.
Input
n r, then r pairs p c.
Output
The number on the final top card.
Constraints
1 ≤ n, r ≤ 50; 1 ≤ p, c and p + c ≤ n + 1.
Worked example
An independently prepared example for this explanation.
Input
5 2 3 1 3 1
Output
4
Solution analysis
- The deck has at most 50 cards, so an explicit vector is sufficient. Store its top at index zero and initialize it in decreasing card-number order, following the sample.
- For a cut, first copy the selected block, then append the cards before it, then the cards after it. These three disjoint pieces form the new deck in exactly the prescribed order.
- With deck [5, 4, 3, 2, 1], cutting position 3 with length 1 produces [3, 5, 4, 2, 1]. The same cut again produces [4, 3, 5, 2, 1], so the top is 4.
Why it works
Each update puts the selected block first in its original order, followed by every unselected card in its previous relative order. It therefore exactly performs one cut. Induction over all r cuts shows that the stored deck is the resulting deck; its first element is the requested top.
Watch out. Convert p from one-based input to a zero-based index. Preserve the selected block order. The initial-order discrepancy in the source is material.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, r;
cin >> n >> r;
vector<int> deck(n);
for (int i = 0; i < n; ++i) {
deck[i] = n - i;
}
for (int cut = 0; cut < r; ++cut) {
int p, c;
cin >> p >> c;
--p;
// Reassemble selected block, preceding cards, then following cards.
vector<int> next;
for (int i = p; i < p + c; ++i) {
next.push_back(deck[i]);
}
for (int i = 0; i < p; ++i) {
next.push_back(deck[i]);
}
for (int i = p + c; i < n; ++i) {
next.push_back(deck[i]);
}
deck = next;
}
cout << deck[0] << '\n';
return 0;
}