Largest price without exact change
National Olympiad — Regional round
Submission name: change.cpp
Problem summary
A buyer owns banknotes a and a seller owns banknotes b. Find the largest positive price at most the buyer’s total for which exact payment is impossible, even when change may use both people’s banknotes. Return 0 if every affordable integral price can be paid.
Input
m followed by m buyer banknotes; n followed by n seller banknotes.
Output
The largest impossible price, or 0.
Constraints
m,n>0; m+n<1000000; all banknotes positive; their total is below 10^15.
Worked example
An independently prepared example for this explanation.
Input
2 10 1 1 2
Output
7
Solution analysis
- Let A be the buyer’s total. Paying price p is equivalent to selecting banknotes from the combined collection with total A−p: those retained or returned to the buyer.
- Find the smallest unrepresentable subset sum g of the combined positive values. In sorted order, if sums 0 through r are possible, a value v≤r+1 extends coverage through r+v; otherwise g=r+1.
- The answer is max(0,A−g).
Why it works
The complement correspondence is exact. The first gap in subset sums gives the largest impossible price because A−p reverses the order. The sorted coverage invariant proves that gap is minimal.
Watch out. Seller may use received banknotes for change. Checking only the seller’s original subset sums is wrong.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The complement correspondence is exact. The first gap in subset sums gives the largest
// impossible price because A−p reverses the order.
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m,n;
long long A=0,x;
vector<long long>v;
cin>>m;
while(m--){
cin>>x;
A+=x;
v.push_back(x);
}
cin>>n;
while(n--){
cin>>x;
v.push_back(x);
}
sort(v.begin(),v.end());
long long r=0;
for(long long x:v){
if(x>r+1){
break;
}
r+=x;
}
cout<<max(0LL,A-r-1)<<'\n';
}