double TL = 0.01; int STANDARD = 1; int DBG = 0; #include using namespace std; #define F0(i,n) for (int i=0; i pii; typedef long long ll; const double EPS = 1e-9; const int MOD = 998244353; #define PR(x) cerr << #x << "=" << x << endl template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << ", " << p.second << ")"; return os; } template ostream& operator<<(ostream& os, const tuple& p) { os << "(" << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ")"; return os; } istream& operator>>(istream& is, pii& p) { is>>p.first>>p.second; return is; } template ostream& operator<<(ostream& os, const vector& v) { os << "["; F0(i,SZ(v)) { if (i>0) os << ","; os << v[i]; } os << "]"; return os; } template ostream& operator<<(ostream& os, const set& v) { os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ","; cerr << i; } os << "}" << endl; return os; } template ostream& operator<<(ostream& os, const map& v) { os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ", "; cerr << i.first << ":" << i.second; } os << "}" << endl; return os; } //#pragma GCC optimize("O3") #ifndef __APPLE__ inline ll GetTSC() { ll lo, hi; asm volatile ("rdtsc": "=a"(lo), "=d"(hi)); return lo + (hi << 32); } inline double GetSeconds() { return GetTSC() / 3.0e9; } #else #include double GetSeconds() { timeval tv; gettimeofday(&tv, 0); return tv.tv_sec + tv.tv_usec * 1e-6; } #endif const int MAX_RAND = 1 << 30; struct Rand { ll x, y, z, w, o; Rand() {} Rand(ll seed) { reseed(seed); o = 0; } inline void reseed(ll seed) { x = 0x498b3bc5 ^ seed; y = 0; z = 0; w = 0; F0(i, 20) mix(); } inline void mix() { ll t = x ^ (x << 11); x = y; y = z; z = w; w = w ^ (w >> 19) ^ t ^ (t >> 8); } inline ll rand() { mix(); return x & (MAX_RAND - 1); } inline int nextInt(int n) { return rand() % n; } inline int nextInt(int L, int R) { return rand()%(R - L + 1) + L; } inline int nextBool() { if (o < 4) o = rand(); o >>= 2; return o & 1; } double nextDouble() { return rand() * 1.0 / MAX_RAND; } }; Rand my(2023); double saveTime; double t_o[20]; ll c_o[20]; void Init() { saveTime = GetSeconds(); F0(i, 20) t_o[i] = 0.0; F0(i, 20) c_o[i] = 0; } double Elapsed() { return GetSeconds() - saveTime; } void Report() { double tmp = Elapsed(); cerr << "-------------------------------------" << endl; cerr << "Elapsed time: " << tmp << " sec" << endl; double total = 0.0; F0(i, 20) { if (t_o[i] > 0) cerr << "t_o[" << i << "] = " << t_o[i] << endl; total += t_o[i]; } cerr << endl; //if (total > 0) cerr << "Total spent: " << total << endl; F0(i, 20) if (c_o[i] > 0) cerr << "c_o[" << i << "] = " << c_o[i] << endl; cerr << "-------------------------------------" << endl; } struct AutoTimer { int x; double t; AutoTimer(int x) : x(x) { t = Elapsed(); } ~AutoTimer() { t_o[x] += Elapsed() - t; } }; #define AT(i) AutoTimer a##i(i) //#define AT(i) int X, turn; int n, m, S, str, score, newX; string ans; const int N = 32; const int M = 64; int P[N]; const int W = 25; const int H = 60; const int DX[]={-1,0,1,0}; const int DY[]={0,1,0,-1}; const string CS="nesw"; const string HS="URDL"; int hp[M][N], pw[M][N], ihp[M][N], f[N]; double bv; int bmoves; int bdir; void Greedy() { bv = -1.0; for (int i = 1; i < H; i++) if (hp[i][X] > 0) { if ((i) * str >= hp[i][X]) { double av = 1.0 * pw[i][X] / ((hp[i][X] + str - 1) / str - 1); if (av > bv) { bv = av; newX = X; ans = "S"; } } break; } for (int dir = -1; dir <= 1; dir += 2) { int cX = X; F1(steps, 25) { if (hp[steps - 1][cX]) break; cX = (cX + dir + W) % W; if (hp[steps - 1][cX]) break; for (int i = steps; i < H; i++) if (hp[i][cX] > 0) { // TODO if ((i - steps + 1) * str >= hp[i][cX]) { double av = 1.0 * pw[i][cX] / (((hp[i][cX] + str - 1) / str) + steps - 2); if (av > bv) { bv = av; newX = (X + dir + W) % W; ans = dir == -1 ? "L" : "R"; } } break; } } } } struct State { vector hits; int X; int S; int fd; ll Hash() { ll ret = S; ret = ret * 239 + X; for (int t : hits) ret = ret * 239 + t; return ret; } }; const int BB = 1 << 16; State bb[BB], ns; const int BUFF = 1 << 23; int buff[BUFF], buff_pos; int bn; typedef double EvalType; const int MAXB = 1000; set> pq[MAXB+1]; unordered_map Hashes; int id[M][N], nx[M][N]; vector active; void Prepare() { active.clear(); F0(i, H) F0(j, W) if (hp[i][j]) { id[i][j] = SZ(active); active.push_back(pii(i, j)); } F0(i, H) F0(j, W) { int x = i + 1; while (x < H && !hp[x][j]) x++; nx[i][j] = x; } } inline int HP(int x, int y, vector& hits) { return (x < H && hp[x][y]) ? hits[id[x][y]] : 0; } int Target(int x, int y, vector& hits) { while (x < H && HP(x, y, hits) <= 0) x = nx[x][y]; return x < H ? id[x][y] : -1; } int BC, BW, maxT; void BeamStep() { F0(level, maxT) { F0(e, BW) { if (pq[level].empty()) break; int lindex = pq[level].begin()->second; pq[level].erase(pq[level].begin()); State s = bb[lindex]; // TODO: stay for (int dir = -1; dir <= 1; dir += 1) { int cX = s.X; int str = s.S / 100 + 1; //PR(dir); F1(steps, 10) { if (HP(level + steps - 1, cX, s.hits) > 0) break; cX = (cX + dir + W) % W; if (HP(level + steps - 1, cX, s.hits) > 0) break; int id = Target(level + steps, cX, s.hits); if (id == -1) continue; int i = active[id].first; //assert(active[id].second == cX); ll cur_hp = HP(i, cX, s.hits); //assert(cur_hp > 0); if ((i - (level + steps) + 1) * str < cur_hp) continue; int shots = (cur_hp + str - 1) / str; int moves = level + steps - 1 + shots; int newS = s.S + pw[active[id].first][active[id].second]; int fd = level == 0 ? dir : s.fd; double av = 1.0 * newS; if (av > bv) { bmoves = moves; bv = av; bdir = fd; } ll eval = -newS; if (moves < maxT && ((SZ(pq[moves]) < BC || (--pq[moves].end())->first > eval))) { ns = s; ns.X = cX; int attack_turn = level; for (int x = (s.X + dir + W) % W; x != cX; x = (x + dir + W) % W) { int nx = Target(attack_turn, x, s.hits); if (nx != -1) { ns.hits[nx] -= str; //assert(ns.hits[nx] > 0); } attack_turn++; } ns.hits[id] = 0; ns.S = newS; ns.fd = fd; ll h = ns.Hash(); if (!Hashes.count(h) || Hashes[h] <= ns.S) { Hashes[h] = ns.S; pq[moves].insert(make_pair(eval, bn)); if (SZ(pq[moves]) > BC) { pq[moves].erase(--pq[moves].end()); } bb[bn++] = ns; } } //cerr << steps << " " << cX << " " << id << " " << shots << endl; if (shots == 1 || dir == 0) break; } } } } } void BeamSearch() { Hashes.clear(); bv = -1.0; bdir = 0; maxT = 45; BC = 24; bn = 0; F0(i, maxT + 1) pq[i].clear(); Prepare(); State s0; s0.X = X; s0.hits.assign(SZ(active), 0); F0(i, SZ(active)) s0.hits[i] = hp[active[i].first][active[i].second]; s0.S = S; pq[0].insert(make_pair(0, 0)); bb[bn++] = s0; /* int BEAM_STEPS = 0; while (Elapsed() < TL) { BW = 1; BEAM_STEPS += BW; BeamStep(); } PR(BEAM_STEPS); */ BW = BC; BeamStep(); //cerr << turn << " " << bdir << " " << bv << " " << bmoves << endl; //PR(bn); //if (bn > BB / 4) throw; //PR(buff_pos); //if (buff_pos > BUFF / 4) throw; if (DBG) { F0(i, MAXB) { if (SZ(pq[i])) cerr << i << " " << SZ(pq[i]) << endl; } } } void Solve() { X = 12; str = 1; score = 0; S = 0; for (turn = 1; turn <= 1000; turn++) { cin >> n; if (n == -1) break; F0(h, H) F0(w, W) { hp[h][w] = hp[h + 1][w]; ihp[h][w] = ihp[h + 1][w]; pw[h][w] = pw[h + 1][w]; } F0(i, n) { int h, p, x; cin >> h >> p >> x; hp[H-1][x] = h; ihp[H-1][x] = h; pw[H-1][x] = p; f[x]++; } if (DBG && turn <= 187) { for (int i = 30; i >= 0; i--) { F0(j, W) if (hp[i][j]) { int d = (hp[i][j] + str - 1) / str; d = min(d, 9); cerr << d; } else cerr << "."; cerr << endl; } F0(j, W) if (j == X) cerr << "X"; else cerr << " "; cerr << endl << endl; } if (hp[0][X] > 0) { cerr << "Dead at " << turn << endl; break; } //Greedy(); BeamSearch(); if (bdir == -1) ans = "L"; else if (bdir == 0) ans = "S"; else ans = "R"; X = (X + bdir + W) % W; if (DBG) cerr << bv << " " << ans << endl; for (int i = 1; i < H; i++) if (hp[i][X] > 0) { pii t = pii(i, X); hp[t.first][t.second] -= str; if (hp[t.first][t.second] <= 0) { S += pw[t.first][t.second]; score += ihp[t.first][t.second]; str = 1 + S / 100; hp[t.first][t.second] = 0; ihp[t.first][t.second] = 0; pw[t.first][t.second] = 0; } break; } cout << ans << endl; } PR(score); if (0) F0(i, W) { cerr << P[i] << " " << f[i] << endl; } } void ReadInput() { F0(i, W) cin >> P[i]; } int main(int argc, char* argv[]) { int seed1 = 0, seed2 = 0; if(argc>1) { seed1 = seed2 = atoi(argv[1]); if (argc > 2) { DBG = atoi(argv[2]); } STANDARD=0; } if(STANDARD) { Solve(); return 0; } for (int seed=seed1; seed<=seed2; seed++) { if(seed>=0 && seed<5000) { char inp[128]; sprintf(inp, "in/%04d.txt", seed); char outp[128]; sprintf(outp, "out/%04d.txt", seed); ignore = freopen(inp, "r", stdin); ignore = freopen(outp, "w", stdout); ReadInput(); //cerr << "Seed #" << seed << " "; Solve(); //cout << "Score would be " << bscore << endl; } else { // Generate throw; } } return 0; }