82AUnreviewed1100GPT-5.5 (high)

Double Cola

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

implementation math

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Don’t simulate the whole queue. Ask yourself: after everyone from the original 5 has drunk once, how many copies of each person are waiting?

The process happens in rounds. In round $0$ , each name appears $1$ time. In round $1$ , each name appears $2$ times. In round $2$ , each name appears $4$ times. You see the doubling nonsense now.

Round $k$ contains exactly $5 \cdot 2^k$ cans, arranged as Sheldon repeated $2^k$ times, then Leonard repeated $2^k$ times, and so on.

Subtract whole rounds from $n$ until the remaining position lies inside the current round. Keep a variable $len = 2^k$ , the number of consecutive times each name appears in that round.

Once $n$ is inside a round with block length $len$ , the answer is simply $\text{names}\left[\left\lfloor \frac{n-1}{len} \right\rfloor\right].$ Use 1-indexed $n$ , so the $-1$ is not optional. Off-by-one goblin defeated.

Key observation

The queue looks chaotic if you stare at individual people. That’s bait. Don’t simulate the queue — it grows forever and $n$ can be as large as $10^9$ .

Instead, group the process into rounds.

Initially, the order is:

\text{Sheldon},\ \text{Leonard},\ \text{Penny},\ \text{Rajesh},\ \text{Howard}

In the first round, each person drinks once:

1,1,1,1,1

After that, each person has been duplicated, so in the next round each name appears twice consecutively:

2,2,2,2,2

Then four times each:

4,4,4,4,4

And so on. In round $k$ , every name appears $2^k$ consecutive times, so the whole round contains:

5 \cdot 2^k

cans.

Reducing $n$

Let $len$ be the number of consecutive copies of each name in the current round.

Start with:

len = 1

The current round has:

5 \cdot len

positions. If $n$ is larger than that, the answer is not in this round, so subtract the whole round:

n \leftarrow n - 5 \cdot len

Then move to the next round:

len \leftarrow 2 \cdot len

Repeat until:

n \le 5 \cdot len

Now $n$ is the position inside the current round.

Finding the name

Inside a round with block size $len$ , the layout is:

\underbrace{S\ldots S}_{len}, \underbrace{L\ldots L}_{len}, \underbrace{P\ldots P}_{len}, \underbrace{R\ldots R}_{len}, \underbrace{H\ldots H}_{len}

So the zero-based index of the answer is:

\left\lfloor \frac{n-1}{len} \right\rfloor

The $n-1$ matters because cans are numbered from $1$ , but arrays are indexed from $0$ . Classic off-by-one trap. It wants your blood.

Example

For $n = 6$ :

Round with $len = 1$ has $5$ cans.
Since $6 > 5$ , subtract it:

n = 6 - 5 = 1

Now $len = 2$ .
Position $1$ in this round belongs to:

\left\lfloor \frac{1-1}{2} \right\rfloor = 0

So the answer is Sheldon.

Complexity

Each iteration doubles $len$ , so there are only about $\log_2 n$ iterations.

O(\log n)

time and

O(1)

extra memory.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    ll n;
    cin >> n;

    vector<string> names = {"Sheldon", "Leonard", "Penny", "Rajesh", "Howard"};

    ll len = 1; // copies of each name in the current round
    while (n > 5 * len) {
        n -= 5 * len;
        len *= 2;
    }

    cout << names[(n - 1) / len] << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    ll n;
    cin >> n;

    vector<string> names = {"Sheldon", "Leonard", "Penny", "Rajesh", "Howard"};

    ll len = 1; // copies of each name in the current round
    while (n > 5 * len) {
        n -= 5 * len;
        len *= 2;
    }

    cout << names[(n - 1) / len] << '\n';
    return 0;
}

View on Codeforces Back to the list

Double Cola

Progressive nudges

Full explanation

Key observation

Reducing $n$

Finding the name

Example

Complexity

Generated C++

Double Cola

Progressive nudges

Full explanation

Key observation

Reducing nnn

Finding the name

Example

Complexity

Generated C++

Reducing $n$