IOI 2018 Combo

서브태스크 1: 가능한 모든 경우를 해본 뒤 3이 나오는 경우를 출력하면 된다. 쿼리의 수는 최대 36개이다.

서브태스크 2: 

5점: 모든 문자에 대해서 이전 문자열+A,B,X,Y를 해 보면 된다.

25점: 첫 문자 외의 문자는 후보가 3개이고, 마지막 후보까지 정답이 안 나왔으면 마지막 후보가 자동으로 정답이다. 이를 통하면 2N+1로 줄일 수 있다.

92점:문자열들을 이어붙이면 쿼리를 더 효율적으로 할 수 있다. 이전 문자열을 S라 할 때, 첫 문자가 A라 할 경우 SBBSBXSBYSX라 하면 다음 글자가 B일 때 정답이 S의 길이+2, X일 때 S의 길이+1,Y일 때 S의 길이가 된다. 첫 글자와 마지막 글자를 제외한 글자를 이렇게 처리하면 N+3으로 92점을 맞는다.

95점(만점):첫 글자는 이분 탐색을 통해 2번의 쿼리로 할 수 있다. AB와 AX의 쿼리를 날리면 첫 글자는 유일하게 결정되어, 2+(N-2)+2=N+2로 95점을 맞을 수 있다.

#include "combo.h"
#include <vector>
using namespace std;
char arr[4] = { 'A','B','X','Y' };
std::string guess_sequence(int N) 
{
	int fl = 0;
	string First = "AB";
	if (press(First))
	{
		fl = press("B");
	}
	else
	{
		fl = 2 + press("Y");
	}
	if (N == 1)
	{
		string res;
		res.push_back(arr[fl]);
		return res;
	}
	string cur;
	cur.push_back(arr[fl]);
	int i;
	for (i = 1; i < N - 1; i++)
	{
		vector<char>s;
		int j;
		for (j = 0; j < 4; j++)
		{
			if (j != fl)
				s.push_back(arr[j]);
		}
		string q;
		for (j = 0; j < 3; j++)
		{
			q.append(cur);
			q.push_back(s[0]);
			q.push_back(s[j]);
		}
		q.append(cur);
		q.push_back(s[1]);
		int re = press(q);
		if (re == i)
		{
			cur.push_back(s[2]);
		}
		else if (re == i + 1)
			cur.push_back(s[1]);
		else
			cur.push_back(s[0]);
	}
	vector<char>s;
	int j;
	for (j = 0; j < 4; j++)
	{
		if (j != fl)
			s.push_back(arr[j]);
	}
	string q = cur;
	q.push_back(s[0]);
	if (press(q) == N)
		return q;
	q.pop_back();
	q.push_back(s[1]);
	if (press(q) == N)
		return q;
	q.pop_back();
	q.push_back(s[2]);
	return q;
}