백준 14454 Secret Cow Code (USACO January 2017 Silver 3번)

문제 링크: https://www.acmicpc.net/problem/14454

14454번: Secret Cow Code

주어진 index가 길이가 두배가 되기전 어떤 index에서 온것인지 역추적 하면 됨.

예시

COW 8

n -> 출력할 알파벳 index

------------------------------

0 -> 0

1 -> 1

2 -> 2

------------------------------ n이 3보다 작으면 해당 index 출력

3 -> 2

4 -> 0

5 -> 1

------------------------------ 나머지가 2, 0, 1, 따라서 % 3

6 -> 5 -> 1

7 -> 0

8 -> 1

9 -> 2

10 -> 3 -> 2

11 -> 4 -> 0

------------------------------ 나머지가 5, 0, 1, 2, 3, 4, 따라서 % 6

12 -> 11 -> 4 -> 0

13 -> 0

14 -> 1

15 -> 2

16 -> 3 -> 2

.

.

.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    string s;
    ll n;
    cin >> s >> n;
    n -= 1;
 
    ll sz = s.size();
    while(1) {
        if(n < sz) break;
        ll tmp = sz;
        while(tmp <= n) {
            tmp *= 2;
        }
        tmp /= 2;
        n = (n - 1) % tmp;
    }
 
    cout << s[n] << '\n';
    return 0;
}