#include using namespace std; // // 開始状態 // GG...GG_BB...BB // の各マスのペア (G,G) や (G,B) や (G,_) を考えると、 // ゴール状態と転倒しているものが // nGirls*nBoys + nGirls + nBoys // 個ちょうどあることがわかる。 // // 各ステップでこの転倒数を1ずつ減らしていけば、 // nGirls*nBoys + nGirls + nBoys // ステップでゴールできる。1減らすステップは // h: _GB => BG_ // H: GB_ => _BG // s: _B => B_ // S: G_ => _G // この4パターンしかない。これをひたすら探索。 // // 他の基準としてスタートからゴールまでの // Girl達の移動距離は nGirls*(nBoys+1) で、 // Boy達も同様なので、総移動距離は // 2*nGirls*nBoys + nGirls + nBoys // である。よって、 // nGirls*nBoys回 h/H // nGirls+nBoys回 s/S // という回数配分でないと計算があわない。 // したがって探索時にh/Hを先に探すようにしたほうが効率的? // //=========================================================== // // 転倒数を2減らすパターン(_BB=>BB_, GG_=>_GG)もあるので // 上記の方法で解が見つかる保証はないのだけど、一応うまく // いってるっぽい。 // // 模範解答は上記の4moveの組み合わせのみを使うdeterministicな // ものだった。でもそれで確実に解ける理由がわからん。 // // p : position of the space // step: remaining steps // move: should record the move here bool search( char* p, int step, char* move ) { if( step==0 ) return true; if( p[1]=='G' && p[2]=='B' ) // _GB => BG_ { p[0] = 'B'; if( search( p+2, step-1, move+1 ) ) { *move='h'; return true; } p[2] = 'B'; } if( p[-2]=='G' && p[-1]=='B' ) // GB_ => _BG { p[0] = 'G'; if( search( p-2, step-1, move+1 ) ) { *move='H'; return true; } p[-2] = 'G'; } if( p[1]=='B' ) // _B => B_ { p[0] = 'B'; if( search( p+1, step-1, move+1 ) ) { *move='s'; return true; } p[1] = 'B'; } if( p[-1]=='G' ) // G_ => _G { p[0] = 'G'; if( search( p-1, step-1, move+1 ) ) { *move='S'; return true; } p[-1] = 'G'; } return false; } int main() { int N; cin>>N; while(N--) { // input int probNumber,nGirls,nBoys; cin>>probNumber>>nGirls>>nBoys; // __GG..GG_BB..BB__ char line[1024] = {0}; for(int i=2; i<2+nGirls; ++i) line[i]='G'; for(int i=3+nGirls;i<3+nGirls+nBoys;++i) line[i]='B'; int maxMove = nGirls*nBoys+nGirls+nBoys; // solve char moves[1024]; search( &line[2+nGirls], maxMove, &moves[0] ); // output cout << probNumber << ' ' << maxMove << endl; for(int i=0; i!=maxMove; ++i) (i>0 && i%50==0 ? cout<