Triplex Solitaire
National Olympiad — National round (2021 season)
Submission name: solitaire.cpp
Problem summary
Reveal cards one at a time. Whenever the new card and two visible cards form {x,x,2x}, remove those three immediately. Removed cards never return. Find the number of removed triples, the remaining-card count, and their minimum and maximum, or NONE when none remain.
Input
N, followed by N card values in reveal order.
Output
First line: triples and remaining cards. Second line: minimum maximum, or NONE.
Constraints
3 ≤ N ≤ 1,000,000; 1 ≤ card values ≤ 100,000.
Worked example
An independently prepared example for this explanation.
Input
11 8 4 2 6 2 1 4 9 6 6 4
Output
2 5 1 9
Solution analysis
- Keep the frequency of each currently visible value. For a new value v, it can be the large card if v is even and two v/2 cards are present. It can be a small card if a v card and a 2v card are present.
- Check those two possibilities before inserting v. On a match, remove the required two old cards and count one triple; otherwise insert v. The visible cards before a reveal contain no triplex, so both different match types cannot be available simultaneously.
- In the sample, revealing the second 2 removes 2,2,4. The final 4 later joins an existing 4 and 8 to remove 4,4,8. The five survivors are 6,1,9,6,6, with minimum 1 and maximum 9.
Why it works
Initially the visible multiset has no triplex. Any new triplex must include the newly revealed card; its role is exactly one of the two checked cases. Removing it and the matching old cards leaves a subset of the formerly triplex-free multiset. If both cases held, the old cards would already contain v/2,v/2,v, a contradiction. Thus the simulation maintains exactly the prescribed multiset.
Watch out. Do not remove three copies of the same positive number. Check 2v ≤ V before indexing. Print NONE when all cards disappear.
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);
const int limit = 100000;
vector<int> count(limit + 1, 0);
int n;
cin >> n;
int triples = 0;
for (int i = 0; i < n; i++) {
int value;
cin >> value;
// The new card is either the doubled value or a repeated small value.
if (value % 2 == 0 && count[value / 2] >= 2) {
count[value / 2] -= 2;
triples++;
} else if (2 * value <= limit && count[value] > 0 && count[2 * value] > 0) {
count[value]--;
count[2 * value]--;
triples++;
} else {
count[value]++;
}
}
int remaining = n - 3 * triples;
cout << triples << ' ' << remaining << '\n';
if (remaining == 0) {
cout << "NONE\n";
} else {
int minimum = 1;
int maximum = limit;
while (count[minimum] == 0) {
minimum++;
}
while (count[maximum] == 0) {
maximum--;
}
cout << minimum << ' ' << maximum << '\n';
}
}