Proficient.
Put your skills to the test.

Problem summary

A seller gives 1 kg for 1 lev and 2 kg for 2 leva. Paying 3n leva gives 3 times the amount for n leva, plus 1 kg. Paying 3n+1 or 3n+2 adds another 1 or 2 kg respectively. Find the amount received for x leva.

Constraints

1 ≤ x < 100000000.

Worked example

An independently prepared example for this explanation.

10

14

Solution analysis

1. Let apples(x) denote the amount for payment x. The two base cases are apples(1)=1 and apples(2)=2.
2. For x≥3, divide x into quotient q=x/3 and remainder r=x%3. The offer gives apples(x)=3·apples(q)+1+r. The extra 1 belongs to every multiple-of-three offer; r then accounts for the remaining leva.
3. For x=10, q=3 and r=1. First apples(3)=3·apples(1)+1=4, then apples(10)=3·4+1+1=14. Each recursive call reduces its argument by about a factor of three.

Why it works

The base cases are explicitly stated in the offer. For any larger payment, Euclidean division uniquely gives x=3q+r with q≥1 and r in {0,1,2}. Applying the corresponding offer rule gives exactly 3·apples(q)+1+r. Induction on x proves the recurrence and implementation correct.

Watch out. Do not interpret the rule as 3·(apples(q)+1): the bonus is one kilogram after the tripling. The recurrence only applies when q≥1, so keep the base cases. All results fit in int under the printed bound; long long is used for comfortable intermediate arithmetic.

An independently written complete program with standard headers.

#include<iostream>
using namespace std;
long long apples(long long payment){
    if(payment<3){
        return payment;
    }
    // First apply the multiple-of-three offer, then add the remainder.
    return 3*apples(payment/3)+1+payment%3;
}
int main(){
    long long payment;
    cin>>payment;
    cout<<apples(payment)<<'\n';
}