cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2013 · EasyGeometric sums

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

  1. 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.
  2. 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.
  3. 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.

Complexity: O(n) time and O(1) space. The maximum bill is 9(2^60−1), which fits unsigned 64-bit arithmetic.

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';
}

Source: Arena Olimpiici ↗