#include "prison.h"
#include <vector>
#include <stdio.h>
// solutie x = 24
/*
strategie proasta:
baza B, K cifre
citesti cifra din A, scrii in stare
compari: diferit => return
egal => MAI TREBUIE O STARE DE REDIRECTIONARE
cum repari:
pentru deja stii valoarea lui B atunci scrii starea in functie de B
*/
namespace Solver {
const int BASE = 3;
const int DIGITS = 8;
std::vector<int> pb;
std::vector<int> getpb() {
std::vector<int> ret( 1, 1 );
while( (int)ret.size() <= DIGITS )
ret.push_back( ret.back() * BASE );
return ret;
}
int extract( int num, int idx ) {
if( idx >= DIGITS )
return -1;
return (num / pb[DIGITS - idx - 1]) % BASE;
}
int beats( int win, int lose ) {
if( win == 0 )
return -2;
return -1;
}
std::vector<std::vector<int>> devise_strategy( int N ) {
pb = getpb(); // cum fac asta cu constexpr?
// ret[y < x][0] = action
std::vector<std::vector<int>> ret(1 + BASE * DIGITS, std::vector<int>(N + 1, 0)); // x = 24
// starea initiala => citim 1
ret[0][0] = 1;
for( int val = 1 ; val <= N ; val++ )
ret[0][val] = 1 + extract( val, 0 );
for( int idx = 0 ; idx < DIGITS ; idx++ ){
bool t = (idx & 1);
for( int dig = 0 ; dig < BASE ; dig++ ){
int state = 1 + idx * BASE + dig;
ret[state][0] = t;
for( int valt = 1 ; valt <= N ; valt++ ){
int digt = extract( valt, idx );
if( digt < dig )
ret[state][valt] = beats( !t, t );
else if( digt > dig )
ret[state][valt] = beats( t, !t );
else
ret[state][valt] = 1 + BASE * (idx+1) + extract( valt, idx+1 ); // cifra idx+1 a lui t
}
}
}
// scoate starile pe care nu le atingem
for( auto &lin : ret )
for( auto &el : lin )
if( el >= (int)ret.size() )
el = -1;
return ret;
}
}
std::vector<std::vector<int>> devise_strategy( int N ) {
return Solver::devise_strategy( N );
}
