82-A, *1100

Problem - 82A - Codeforces

문제

• queue에 {"Sheldon", "Leonard", "Penny", "Rajesh", "Howard"} 가 차례로 들어가 있다
• queue에서 원소를 뺐을 때 나오는 사람이 콜라를 마시고 그 사람 이름 2개를 다시 queue에 넣는다 --- !
• ! 를 $n(1 \leq n \leq 10^{9})$ 수행했을 때 마지막 콜라를 마시는 사람??
• $O(log\ n)$ 정도의 알고리즘은 통과할 수 있다

 

$O(log\ n)$

q	0	1	2	3	4
value	Sheldon	Leonard	Penny	Rajesh	Howard

배열 $q$가 위와 같다고 하자

 

Sheldon

Sheldon

Leonard

Leonard

Penny

Penny

Rajesh

Rajesh

Howard

Howard

queue 에 위와같이 원소가 들어있으면 $i(1 \leq i \leq 10)$번째 원소는 $q$에서 index가
$$\left [ \frac{i-1}{2} \right ]$$

일반화 하면, 똑같은 이름이 $r$번 들어가 있는 큐에 대해 $i(1 \leq i \leq 5r)$번째 원소는 $q$에서 index가
$$\left [ \frac{i-1}{r} \right ]$$

이를 이용하여 답을 구한다

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
string q[] = {"Sheldon", "Leonard", "Penny", "Rajesh", "Howard"};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n;
    cin >> n;
    int acc = 1;
 
    while(n - 5*acc > 0){
        n -= 5*acc;
        acc *= 2;
    }
 
    cout << q[(n-1)/acc] << endl;
 
    return 0;
}cs