Tournament Champion
National Olympiad — National round (2014 season)
Submission name: champion.cpp
Problem summary
Fighters start numbered in order. Each round pairs adjacent fighters; an unpaired last fighter advances automatically. A + records a win by the lower original number and a − by the higher. Results are given in round and match order. Recover the champion.
Input
A string of + and − signs terminated by a period.
Output
The champion’s original one-based number.
Constraints
The result sequence has at most 256 characters as printed in the statement; it ends with a period.
Worked example
An independently prepared example for this explanation.
Input
+-+-.
Output
5
Solution analysis
- Every actual fight removes exactly one fighter. Therefore a sequence containing M fight results must have started with M+1 fighters.
- Initialize the row with 1…M+1. For each round, process consecutive pairs using the next sign and append the selected fighter to a new row. If one fighter is left without a partner, append it without consuming a sign.
- For +-+-, there are five fighters. Round one retains 1,4,5. Round two retains 1,5. The final − selects 5 as champion.
Why it works
The initial row is determined by the number of eliminations. Each simulated match uses the recorded winner rule, and the bye uses no result. Thus by induction every round’s survivor row is the actual row in original order. The sole final survivor is the champion.
Watch out. Byes do not consume signs. Fighters retain original numbers. Results describe whole rounds in sequence, not a recursive bracket traversal.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
int main() {
string results;
char symbol;
while (cin >> symbol && symbol != '.') {
results += symbol;
}
vector<int> fighters(results.size() + 1);
iota(fighters.begin(), fighters.end(), 1);
int nextResult = 0;
while (fighters.size() > 1) {
vector<int> winners;
for (int i = 0; i < static_cast<int>(fighters.size()); i += 2) {
if (i + 1 == static_cast<int>(fighters.size())) {
// A bye advances without consuming a recorded fight result.
winners.push_back(fighters[i]);
} else {
if (results[nextResult] == '+') {
winners.push_back(min(fighters[i], fighters[i + 1]));
} else {
winners.push_back(max(fighters[i], fighters[i + 1]));
}
nextResult++;
}
}
fighters = winners;
}
cout << fighters[0] << '\n';
}