IOI 2018 day1 - Combo

문제 링크 : www.acmicpc.net/problem/20060

문제 여담 : 3년전에 뉴비 시절때 보자마자 무서워서 도망갔다. 쉬운 문제라는데 이런 함수 구현 형태를 접해본적도 없고, 너무 어렵게 느껴졌다. 슬펐었다.

문제 풀이

제일 먼저 생각할 수 있는 것은 첫 글자를 빠르게 찾아야 한다는 것이다. 총 글자의 수는 4가지 이기 때문에 AB,AX를 묶어서 2번 탐색하는 것으로 첫번째 글자를 찾을 수 있다. 일반성을 잃지 않고 A였다고 하자. 

이제 우리는 N번의 탐색을 통해 N-1개의 글자를 찾아야 하며, 한번 탐색때 부를 수 있는 단어의 길이는 4N이다. 길이와 횟수가 비슷하기 때문에 1번에 1개의 글자를 알아내는 것을 목표로 해야 한다.

한번의 질문의 대한 답으로 B,X,Y 중 다음글자가 무엇인지를 알아내야한다. 다시 생각하면 각각 B,X,Y 가 답일때 질문에 대한 결과가 달라야 한다.

현재까지 알아낸 단어를 s 라고 하자 이때 sXsYBsYXsYY를 질문하면 된다. 약 4번을 반복하는 것이기 때문에 정확히 4N 의 조건을 만족하며, 2가 커지면 Y, 1이 커지면 X 그대로면 B라는 결론을 낼 수 있다.
이 과정을 반복하고. 마지막 글자만 2번을 사용하여 정해주면 된다. 

코드

#include "combo.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
char ch[1010];
char st;
string s;
std::string guess_sequence(int N) {
    ll i,j,k,l,m,n=N;
    ll a=0;
    if(press("XY")) a+=2;
    if(press("BY")) a+=1;
    if(a==0){
        ch[1]='B';
        ch[2]='X';
        ch[3]='Y';
        st='A';
    }
    if(a==1){
        ch[1]='A';
        ch[2]='X';
        ch[3]='Y';
        st='B';
    }
    if(a==2){
        ch[1]='B';
        ch[2]='A';
        ch[3]='Y';
        st='X';
    }
    if(a==3){
        ch[1]='B';
        ch[2]='X';
        ch[3]='A';
        st='Y';
    }
    s+=st;
  if(n==1)
    return s;
    for(i=1;i<n-1;i++){
        string p;
        p=s+ch[2]+s+ch[1]+ch[1]+s+ch[1]+ch[2]+s+ch[1]+ch[3];
        ll x=press(p);
        if(x==i) s+=ch[3];
        if(x==i+1) s+=ch[2];
        if(x==i+2) s+=ch[1];
    }
    ll y=0;
 
    if(press(s+ch[1])==n){
        return s+ch[1];
    }
    if(press(s+ch[2])==n){
        return s+ch[2];
    }
    return s+ch[3];
}