#include using namespace std; using pii=pair; using tii=tuple; using qii=tuple; using ll=long long; using ull=unsigned long long; using ld=long double; constexpr int INF=1e9; constexpr ll INF_ll=1e18; #define rep(i,n) for (int i=0;i<(int)(n);i++) #define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++) #define all(v) v.begin(),v.end() #define len(v) ((int)v.size()) template inline bool chmin(T &a,T b){ if(a>b){ a=b; return true; } return false; } template inline bool chmax(T &a,T b){ if(a(now-start).count(); return ms; } int get_ms_all_program(){ auto now=chrono::system_clock::now(); int ms=chrono::duration_cast(now-program_start).count(); return ms; } } mt19937 mt; uint32_t rand_int(uint32_t r){ //[0,r) assert(r!=0); return ((uint64_t)mt()*r)>>32; } int rand_int(int l,int r){ //[l,r) assert(l T get_random_element(const vector &v){ assert(!v.empty()); return v[rand_int(len(v))]; } template void add(vector &a,vector b){ for(auto i:b) a.push_back(i); } constexpr int W=25,H=60,T=1000; namespace Solver{ struct Enemy{ int first_hp,hp,power,end_turn; Enemy(int h,int p,int turn):first_hp(h),hp(h),power(p),end_turn(turn+H){} }; using Score=int; struct Candidate{ int action; Score score; int parent; Candidate(int action_,Score score_,int parent_):action(action_),score(score_),parent(parent_){} auto operator<=>(const Candidate &other) const{ return this->score<=>other.score; } }; struct State{ vector> q; int pos=12,score=0,level=1,power_sum=0; int point=0; vector actions; int turn=0; State():q(W){} auto operator<=>(const State &other) const{ return this->point*this->level<=>other.point*other.level; } void add_enemy(int x,int h,int p){ Enemy enemy(h,p,turn); q[x].push(enemy); } Candidate try_advance(int d,int parent) const{ int new_pos=pos+d; if(new_pos==-1) new_pos=W-1; if(new_pos==W) new_pos=0; int new_point=point,new_level=level; if(!q[new_pos].empty()){ Enemy enemy=q[new_pos].front(); if(enemy.end_turn==turn+1){ return Candidate(d,-INF,parent); } enemy.hp-=min(enemy.hp,level); if(enemy.hp<=0){ new_point+=enemy.first_hp; new_level=1+(power_sum+enemy.power)/100; }else{ if(enemy.end_turn==turn+2){ return Candidate(d,-INF,parent); } } }else{ new_point-=10; if(d==0) new_point-=10; if(!actions.empty()&&actions.back()+d==0) new_point-=10; } rep(w,W){ if(!q[w].empty()){ Enemy enemy=q[w].front(); if(enemy.end_turn!=turn+1){ if(w!=new_pos) new_point-=enemy.first_hp-enemy.hp; } } } Score new_score=new_point*new_level; return Candidate(d,new_score,parent); } void advance(int d){ pos+=d; if(pos==-1) pos=W-1; if(pos==W) pos=0; actions.push_back(d); if(!q[pos].empty()){ Enemy &enemy=q[pos].front(); if(enemy.end_turn==turn+1){ //cerr << turn << " " << enemy.first_hp << " " << enemy.hp << " " << enemy.power << " miss" << endl; score=-INF; point=-INF; } enemy.hp-=min(enemy.hp,level); if(enemy.hp<=0){ score+=enemy.first_hp; point+=enemy.first_hp; power_sum+=enemy.power; level=1+power_sum/100; q[pos].pop(); }else{ } }else{ point-=10; int sz=len(actions); if(actions.back()==0) point-=10; if(2<=sz&&actions[sz-2]+actions[sz-1]==0) point-=10; } turn++; rep(w,W){ if(!q[w].empty()){ Enemy &enemy=q[w].front(); if(enemy.end_turn==turn){ q[w].pop(); }else{ /*int dist=(pos-w+W)%W; if(!(dist==0||dist==1||dist==W-1)) point-=enemy.first_hp-enemy.hp;*/ if(pos!=w) point-=enemy.first_hp-enemy.hp; } } } if(!q[pos].empty()){ Enemy &enemy=q[pos].front(); if(enemy.end_turn==turn+1){ //cerr << turn << " " << enemy.first_hp << " " << enemy.hp << " " << enemy.power << " miss" << endl; score=-INF; point=-INF; } } } }; constexpr int Depth=30,Width=10; vector beam_search(State first_state){ vector dp; dp.push_back(first_state); rep(depth,Depth){ //vector candidates; vector,greater>> pq(W); rep(width,Width){ if(len(dp)<=width) break; const State &state=dp[width]; replr(d,-1,2){ Candidate candidate=state.try_advance(d,width); if(candidate.score==-INF) continue; int pos=state.pos+d; if(pos==-1) pos=W-1; if(pos==W) pos=0; if(!pq[pos].empty()&&candidate candidates; rep(pos,W){ while(!pq[pos].empty()){ Candidate candidate=pq[pos].top(); pq[pos].pop(); candidates.push_back(candidate); //if(len(candidates)==Width) break; } } sort(all(candidates)); reverse(all(candidates)); vector new_dp; for(auto &candidate:candidates){ State state=dp[candidate.parent]; state.advance(candidate.action); new_dp.push_back(state); } swap(dp,new_dp); } if(dp.empty()) return {0}; //cerr << "beam " << dp[0].point << " " << dp[0].level << " " << dp[0].actions[0] << endl; return dp[0].actions; } void solve(){ State state; rep(_,T){ int n; cin >> n; if(n==-1) break; rep(i,n){ int h,p,x; cin >> h >> p >> x; //cerr << h << " " << p << " " << x << endl; state.add_enemy(x,h,p); } state.actions.clear(); int action=beam_search(state)[0]; state.advance(action); char c='X'; if(action==-1) c='L'; else if(action==0) c='S'; else if(action==1) c='R'; else assert(0); cout << c << '\n'; cout.flush(); //cerr << state.turn << " ? " << c << endl; /*if(!state.q[state.pos].empty()){ Enemy enemy=state.q[state.pos].front(); cerr << " !!! " << enemy.end_turn << " " << enemy.hp << endl; } cerr << state.turn << " : "; rep(w,W){ if(!state.q[w].empty()){ cerr << state.q[w].front().end_turn-state.turn << " "; }else{ cerr << "-1 "; } } cerr << endl; assert(state.turn<=200);*/ //cerr << len(state.q[state.pos]) << " " << n << " " << state.turn << endl; //cerr << state.turn << " " << state.score << " " << Timer::get_ms() << endl; } cerr << state.score << ' ' << Timer::get_ms_all_program() << '\n'; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); Timer::program_start_snap(); #ifdef LOCAL rep(i,W){ int _; cin >> _; } #endif Solver::solve(); exit(0); }