Problem: cheeseburger_corollary_ch2 (2023 practice)

*This problem shares some similarities with A1, with key differences in bold.*

Problem solving skills are applicable to many daily musings. For instance, you might ponder over shared birthdays, bird houses, mapmaking, or ordering an exact number of chicken nuggets. Naturally, another great question to ponder is: how many deckers of a cheeseburger you could build if you spent your entire salary on fast food!

Specifically, you're interested in building a \(K\)-decker cheeseburger, which alternates between buns, cheese, and patty starting and ending with a bun. **Buying a single cheeseburger costs \(A\) dollars and a double cheeseburger costs \(B\) dollars**. Each provides you with two buns, though a single provides one patty and one cheese, while a double provides two patties and two cheese.

{{PHOTO_ID:181863494933248|WIDTH:600}}

You'd like to know **the biggest \(K\) for which you can build a \(K\)-decker cheeseburger by spending at most \(C\) dollars**.


# Constraints

\(1 \leq T \leq 65\)
\(1 \leq A, B, C \leq 10^{16}\)


# Input Format

Input begins with an integer \(T\), the number of test cases. Each case contains one line with three space-separated integers, \(A\), \(B\) and \(C\).


# Output Format

For the \(i\)th test case, print "`Case #i:` " followed by the largest possible \(K\) for which you can build a \(K\)-decker cheeseburger, or \(0\) if you cannot build even a \(1\)-decker cheeseburger.


# Sample Explanation

In the first case, you can buy \(1\) single and \(1\) double cheeseburger. This gives you \(4\) buns, \(3\) slices of cheese, and \(3\) patties, exactly enough for a \(3\)-decker cheeseburger.

In the second case, you can only afford to build a \(1\)-decker cheeseburger. That's coincidentally identical to a single cheeseburger.

In the third case, you only have \(\$1\), while a single costs \(\$2\) and a double costs \(\$3\). No fast food for you today.

In the fourth case, our best possible strategy is to spend all our money on \(100\) doubles, which we can use to build a \(199\)-decker cheeseburger.

In the fifth case, our best possible strategy is to spend all our money on \(100\) singles, which we can use to build a \(100\)-decker cheeseburger.


Sample input:
6
2 3 5
2 3 2
2 3 1
5 1 100
1 3 100
1 1 1000000000000


Sample output:
Case #1: 3
Case #2: 1
Case #3: 0
Case #4: 199
Case #5: 100
Case #6: 1999999999999


Solution: Let's think about what ingredient is limiting us. If we've bought \(0\) singles, we're limited by buns. Otherwise we're limited by patties. So we should either:

- First reasonable option: buy only doubles (we'll be limited by buns unfortunately, but maybe singles are so outrageously expensive that it's worth it), or
- Second reasonable option: buy \(1\) single first so that we're only limited by patties, then buy as many patties as possible.

The second option is a bit trickier than it seems. Specifically, we might want to buy \(\lfloor C/A \rfloor\) singles (and no doubles) or \(1\) single (and as many doubles) **or \(2\) singles (and as many doubles)**.

We might want to buy \(2\) singles because if we start with a single, then prefer doubles, we might run out of money for doubles, but be able to afford one more single. Intuitively it might sound silly to buy \(2\) singles when \(1\) double would be cheaper, but keep in mind that for the first \(2\) (and only the first \(2\)) singles you buy, this may actually be useful because you get an extra bun. If you had bought only doubles, you'd be limited by buns, not patties.

In short, it is sufficient to consider \(S\) as one of \(\{0, 1, 2, \lfloor C/A \rfloor\}\), and then buying as many doubles as possible, and taking the best of these candidates.


Code: #include <algorithm>
#include <iostream>
using namespace std;

using int64 = long long;

int64 solve() {
  int64 A, B, C;
  cin >> A >> B >> C;

  // Watch out for this nasty bug: 2*x/y != 2*(x/y).
  // Remember to floor before multiplying!

  // Option 1: Buy only singles.
  int64 ans = C / A;

  // Option 2: Buy only doubles.
  ans = max(ans, 2*(C / B) - 1);

  // Option 3: 1 single + maximum doubles.
  if (C > A) {
    ans = max(ans, 1 + 2*((C - A)/B));
  }
  // Option 4: 2 singles + maximum doubles.
  if (C > 2*A) {
    ans = max(ans, 2 + 2*((C - 2*A)/B));
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}