Unpaid Phone Bills
National Olympiad — Municipal round (2014 season)
Submission name: phones.cpp
Problem summary
Given a multiset of phone bills and a multiset of payments for some of those bills, print all unpaid amounts in decreasing order, preserving duplicates.
Input
M N, M bill amounts, then N payment amounts.
Output
The remaining amounts in decreasing order, separated by spaces, with exactly two decimals.
Constraints
1<N<M≤1000000; amounts have two decimal places and do not exceed 400 leva.
Worked example
An independently prepared example for this explanation.
Input
7 4 0.13 22.78 33.00 323.12 22.78 27.38 27.38 27.38 0.13 323.12 33.00
Output
27.38 22.78 22.78
Solution analysis
- Convert every amount into cents, an integer from 0 to 40000. Use a frequency array, incrementing for bills and decrementing for payments.
- Scan the possible cent values from 40000 down to 0. Print each value as many times as its remaining frequency. This performs a multiset subtraction, so equal bills are treated as separate obligations.
- The sample has two bills of 27.38 but only one matching payment, leaving one unpaid. Both bills of 22.78 remain, so the result is 27.38 22.78 22.78.
Why it works
For each cent value, increments count all bills and decrements remove exactly its payments. The resulting count is precisely its unpaid multiplicity. Descending traversal prints exactly that multiset in the requested order.
Watch out. Use integer cents rather than binary floating-point keys. One payment removes one occurrence, not all equal bills.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
// Algorithm: Convert every amount into cents, an integer from 0 to 40000.
using namespace std;
int readCents(){
string value;
cin>>value;
size_t point=value.find('.');
return stoi(value.substr(0,point))*100+stoi(value.substr(point+1));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int bills,payments;
cin>>bills>>payments;
vector<int>frequency(40001,0);
for(int i=0;i<bills;i++){
frequency[readCents()]++;
}
for(int i=0;i<payments;i++){
frequency[readCents()]--;
}
bool first=true;
for(int cents=40000;cents>=0;cents--){
for(int copy=0;copy<frequency[cents];copy++){
if(!first){
cout<<' ';
}
first=false;
cout<<cents/100<<'.'<<setw(2)<<setfill('0')<<cents%100;
}
}
cout<<'\n';
}