You may often see the phrase “buy one of \(X\) yen, buy three for \(Y\) yen” in a supermarket.
We can express “the way of achieving as low cost as possible” as an algorithm as follows:

1. If it is cheaper to “buy three for \(Y\) yen” than to “buy one for \(X\) yen” three times:

   • Buy three apples for \(Y\) yen as much times as possible. Buy the remainder for \(X\) yen each.

2. If it is cheaper or equivalent to “buy one for \(X\) yen” three times than to “buy three for \(Y\) yen”:

   • Buy all \(N\) apples for \(X\) yen each.

It can be mathematically proved that this algorithm is optimal, so it is sufficient to implement this.
The second case should be easy to implement, because the answer is just \(XN\) yen.
The first case can be implemented concisely using divisions. Let \(Q\) and \(R\) be the quotient and remainder when dividing \(N\) by \(3\), then it is optimal to “buy three for \(Y\) yen” \(Q\) times and “buy one for \(X\) yen” \(R\) times in the first case. \(Q\) can be calculated using operators that does division, specifically N / 3 and N % 3 (in C++). (Alternatively, you may simulate it using for or while statements.)

Therefore, the problem has been solved. The complexity is \(\mathrm{O}(1)\). (If you use simulation, it costs \(\mathrm{O}(N)\).)

• Sample code (C++)

#include <iostream>
using namespace std;
int main() {
  int X, Y, N;
  cin >> X >> Y >> N;
  if (X * 3 > Y) {
    cout << (N / 3) * Y + (N % 3) * X << endl;
  } else {
    cout << X * N << endl;
  }
}