Submission #159407

#	Time	Username	Problem	Language	Result	Execution time	Memory
159407		Mounir	Combo (IOI18_combo)	C++14	100 / 100	69 ms	624 KiB

combo

#include <bits/stdc++.h>
#include "combo.h"
using namespace std;
 
string chaineCur;
 
string chaineRecherche;
/*
int press(string s)
{
	int tailleMax = 0;
	for (int deb = 0; deb < (int)s.length(); ++deb)
	{
		int add = 0;
		while ( deb + add < (int)s.length() && add < (int)chaineRecherche.length() && s[add + deb] == chaineRecherche[add])++add;
		tailleMax = max(tailleMax, add);
	}
	//cout << tailleMax << endl;
	return tailleMax;
}*/
 
string resoudre(int tailleChaine)
{
	//Trouver la lettre numéro 1
	if (press("AB") >= 1)
	{
		if (press("A") == 1) chaineCur = "A";
		else chaineCur = "B";
	}
	else
	{
		if (press("X") == 1) chaineCur = "X";
		else chaineCur = "Y";
	}
	
	if (tailleChaine==1)return chaineCur;
	
	char dicoBase[4] = {'A', 'B', 'X', 'Y'};
	vector<char> dico;
	
	for (char i : dicoBase){
		if (i != chaineCur[0])
			dico.push_back(i);}
	
	//cout << dico[0] << " " << dico[1] << " " << dico[2] << endl;
	
	for (int idLettre = 1; idLettre < tailleChaine - 1; ++idLettre)
	{
		string toPress = chaineCur + dico[0]; //Si press(toPress) renvoie 1
		toPress += (chaineCur + dico[1] + dico[0]) + (chaineCur + dico[1] + dico[1]) + (chaineCur + dico[1] + dico[2]); 
		
		int resCur = press(toPress);
		
		if (resCur ==  idLettre + 1)
			chaineCur += dico[0];
		else if (resCur == idLettre + 2)
			chaineCur += dico[1];
		else
			chaineCur += dico[2];
		
	}
	
	//On trouve la dernière lettre
	string toPress = chaineCur + "A" + chaineCur + "B";
	if (press(toPress) == tailleChaine)
	{
		if (press(chaineCur + "A") == tailleChaine)chaineCur += "A";
		else chaineCur += "B";
	}
	else
	{
		if (press(chaineCur + "X") == tailleChaine)chaineCur += "X";
		else chaineCur += "Y";
	}
	//cout << chaineCur << endl;
	return chaineCur;
}
 
string guess_sequence(int N)
{
	return resoudre(N);
}
/*
int main()
{
	chaineRecherche = "XXYYABYABXAY";
	if(guess_sequence(chaineRecherche.length()) == chaineRecherche)cout<<"OUI";
	else
	cout<<"NON";
	return 0;
}*/

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95