The Tailor’s Doubling Button Bill
National Olympiad — Municipal round (2013 season)
Submission name: tailor.cpp
Problem summary
The first button costs k stotinki, and each next button costs twice as much. For n buttons, print the total as whole leva and remaining stotinki.
Input
k and n.
Output
Two nonnegative integers: leva and stotinki.
Constraints
1 ≤ k < 10; 1 < n < 61. One lev equals 100 stotinki.
Worked example
Input and output for the worked example discussed below.
Input
1 8
Output
2 55
Solution analysis
- Button prices form a geometric sequence k,2k,4k,… . Maintain the current button price and a running total; add each price once, then double it for the next button.
- Keep everything in integer stotinki. After summing, total/100 gives whole leva and total%100 gives the remaining stotinki. This avoids floating-point money rounding.
- For k=1,n=8, the total is 1+2+4+8+16+32+64+128=255 stotinki, hence 2 leva and 55 stotinki. At k=9,n=60 the total is 10376293541461622775, beyond signed 64-bit but within unsigned long long.
Why it works
At the beginning of each iteration, price is the correct geometric price of that button and total contains exactly all previous prices. Adding and doubling preserves the invariant. Integer quotient and remainder uniquely express the final total in base 100.
Watch out. Signed long long is insufficient at the upper bound. Avoid floating-point powers or currency arithmetic. The output is two integers, not a decimal currency string.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
unsigned long long price;
int buttons;
cin>>price>>buttons;
unsigned long long total=0;
for(int index=0;index<buttons;index++){
// All amounts stay exact in stotinki.
total+=price;
if(index+1<buttons){
price*=2;
}
}
cout<<total/100<<' '<<total%100<<'\n';
}