Secret Cow Code

https://www.acmicpc.net/problem/14454

14454번: Secret Cow Code

 

제가 영어를 잘 못해서 해석이 어려웠지만, 예제를 한 번 보니 이해를 단번에 해버렸습니다.

 

N 값보다 문자열의 길이가 커질 때까지 이 행동을 반복할 필요가 있을까요?

일단 입력으로 들어오는 N 값이 10^18인 것을 보니 절대 그럴수는 없을거라는 느낌이 드네요.

 

이렇게 값이 크게 주어지면 보통 binary search / dynamic programming / pattern 찾기 정도를 생각해

볼 수 있습니다.

 

느낌상 pattern 찾기를 해보면 될 것 같아요. 뭔가 규칙이 있을 것 같습니다.

새로 추가되는 문자가 없고, 추가하는 문자열도 원래 문자열에 규칙적인 연산을 한 후에 붙이는 것이라

(한칸 쉬프트하고, 뒤집어서 뒤에 붙이는게 전부이니..)

N 값을 반복적인 계산으로 원래 초기 문자열 길이 안으로 가져오면 되겠습니다.

 

#include <math.h>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>
#include <string.h>
 
#define endl    '\n'
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
ll n;
string s;
 
int main() {
    FastIO;
 
    cin >> s;
    cin >> n;
 
    ll f = s.size();
    while (f < n) f <<= 1;
 
    while (n > s.size()) {
        while(n <= f) f >>= 1;
        n -= f;
        n -= 1;
        if (n == 0) n = f;
    }
 
    cout << s[n - 1];
 
    return 0;
}