namespace atcoder {} #ifdef LOCAL #define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl; #else #define NDEBUG #define dbg(x) true; #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #ifdef GTEST #include #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef PERF #include #endif using namespace std; using namespace atcoder; #define fast_io \ ios_base::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); #define ll long long int #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define reps(i, n) for (int i = 1; i <= (int)(n); i++) #define REP(i, n) for (int i = n - 1; i >= 0; i--) #define REPS(i, n) for (int i = n; i > 0; i--) #define MOD (long long int)(1e9 + 7) #define INF (int)(1e9) #define LINF (long long int)(1e18) #define chmax(a, b) a = (((a) < (b)) ? (b) : (a)) #define chmin(a, b) a = (((a) > (b)) ? (b) : (a)) #define all(v) v.begin(), v.end() typedef pair Pii; typedef pair Pll; constexpr double PI = acos(-1); #ifdef NDEBUG #define CHECK(v1, op, v2) #else #define CHECK(v1, op, v2) \ if (!((v1)op(v2))) { \ cerr << "ERROR:" << (v1) << " " << (v2) << endl; \ assert((v1)op(v2)); \ } #endif long double nCr(const int n, const int r) { long double ret = 1; rep(t, r) { ret *= (n - t); ret /= (r - t); } return ret; } template string to_string(const vector& vec) { string ret = ""; rep(i, vec.size()) { ret += vec[i].to_string(); if (i + 1 != vec.size()) { ret += ","; } } return ret; } template ostream& operator<<(ostream& os, const vector& vec) { os << to_string(vec); return os; } uint32_t xorshift() { static uint32_t x = 12345789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; w ^= t ^ (t >> 8) ^ (w >> 19); return w; } int rand(const uint32_t l, const uint32_t r) { return xorshift() % (r - l) + l; } uint32_t rand_other_than(const uint32_t l, const uint32_t r, const uint32_t other) { const uint32_t num = rand(l, r - 1); return num + (num >= other); } template const T& rand_vec(const vector& vec) { assert(vec.size() > 0); return vec[rand(0, vec.size())]; } template void shuffle(vector& vec) { rep(l, (int)vec.size() - 1) { const int idx = rand(l, vec.size()); swap(vec[idx], vec[l]); } } class Timer { chrono::system_clock::time_point _start, _end; ll _sum = 0, _count = 0; public: void start() { _start = chrono::system_clock::now(); } void stop() { _end = chrono::system_clock::now(); } void add() { const chrono::system_clock::time_point now = chrono::system_clock::now(); _sum += static_cast( chrono::duration_cast(now - _start).count()); _count++; } ll sum() const { return _sum / 1000; } int count() const { return _count; } string average() const { if (_count == 0) { return "NaN"; } return to_string(_sum / 1000 / _count); } void reset() { _start = chrono::system_clock::now(); _sum = 0; _count = 0; } inline int ms() const { const chrono::system_clock::time_point now = chrono::system_clock::now(); return static_cast( chrono::duration_cast(now - _start).count() / 1000); } inline int ns() const { const chrono::system_clock::time_point now = chrono::system_clock::now(); return static_cast( chrono::duration_cast(now - _start).count()); } }; #ifdef LOCAL struct Timers : unordered_map { friend ostream& operator<<(ostream& os, const Timers& timers) { for (const auto& pa : timers) { os << pa.first << " time: " << pa.second.sum() / 1000 << " count: " << pa.second.count() << endl; } return os; } }; #else struct Timers { struct Dummy { void start() const {} void add() const {} }; Dummy dummy; const Dummy& operator[](const std::string& str) { return dummy; } friend ostream& operator<<(ostream& os, const Timers& timers) { return os; } }; #endif Timers global_timers; /* start */ struct Output { friend ostream& operator<<(ostream& os, const Output& output) { return os; } }; /* start */ vector PARAMS = {}; /* start */ struct Enemy { int h, p, y, x; int original_h; }; using Action = int; constexpr Action kL = -1; constexpr Action kR = 1; constexpr Action kS = 0; vector enemys; vector> turn_x2idx; vector next_enemy_idxes; int X = 12; int LEVEL = 1; int SUM_POWERES = 0; int SCORE = 0; int TURN = 0; constexpr int W = 25; constexpr int H = 60; struct Solution { vector Xs; vector damages; int turn = 0; int power; int score = 0; int x; int first_dx = INF; Solution() : damages(enemys.size(), 0), power(SUM_POWERES), x(X) {} void Simulate() { for (const auto next_x : Xs) { if (turn >= H) break; while (true) { if (turn >= H) break; const int level = power / 100 + 1; // 移動 int dx = (x < next_x ? 1 : 0) + (x > next_x ? -1 : 0); // 接触するなら待つ int next_enemy_idx = turn_x2idx[turn][x + dx]; while (next_enemy_idx != -1 && enemys[next_enemy_idx].h - damages[next_enemy_idx] <= 0) { next_enemy_idx = next_enemy_idxes[next_enemy_idx]; } if (next_enemy_idx != -1 && enemys[next_enemy_idx].y - turn == 0 && enemys[next_enemy_idx].h - damages[next_enemy_idx] > 0) { dx = 0; next_enemy_idx = turn_x2idx[turn][x]; while (next_enemy_idx != -1 && enemys[next_enemy_idx].h - damages[next_enemy_idx] <= 0) { next_enemy_idx = next_enemy_idxes[next_enemy_idx]; } } if (first_dx == INF) { first_dx = dx; } x += dx; // 敵がいる if (next_enemy_idx != -1) { assert(enemys[next_enemy_idx].h - damages[next_enemy_idx] > 0); const auto& enemy = enemys[next_enemy_idx]; // 接触 if (enemy.y - turn == 0) { return; } // 攻撃 assert(enemy.h > damages[next_enemy_idx]); damages[next_enemy_idx] += level; if (enemy.h <= damages[next_enemy_idx]) { // 倒した power += enemy.p; score += enemy.original_h; next_enemy_idx = -1; // 目的地を倒したらbreak if (x == next_x) { break; } } } turn++; if (next_enemy_idx != -1 && enemys[next_enemy_idx].y - turn == 0) { // 倒せなくて衝突 return; } } } } }; class Solver { public: explicit Solver(istream& is) { #ifdef LOCAL // Pを捨てる rep(i, W) { int p; is >> p; } #endif } bool Input() { int N; cin >> N; if (N == -1) { return true; } // 一番上の行に新たな敵機が出現する。出現確率は後述のように列ごとに定められている。 rep(i, N) { int h, p, x; cin >> h >> p >> x; enemys.push_back(Enemy{h, p, 59, x, h}); } turn_x2idx.assign(H + 1, vector(W, -1)); next_enemy_idxes.assign(enemys.size() + 1, -1); int i = 0; for (const auto& enemy : enemys) { turn_x2idx[enemy.y][enemy.x] = i; i++; } rep(x, W) { int idx = -1; REP(y, H) { if (turn_x2idx[y][x] != -1) { next_enemy_idxes[turn_x2idx[y][x]] = idx; idx = turn_x2idx[y][x]; } turn_x2idx[y][x] = idx; } } return false; } void TurnEnd(Action action) { // 自機を左右いずれかに 1 マス移動、またはその場にとどまる。 if (action == kL) { cout << "L" << endl; X -= 1; } else if (action == kR) { cout << "R" << endl; X += 1; } else { cout << "S" << endl; } bool attacked = false; for (auto itr = enemys.begin(); itr != enemys.end();) { // 接触判定 if (itr->x == X && itr->y == 0) { // 接触してしまった std::quick_exit(0); return; } // 自機と同じ列に存在する敵機の中で自機に一番近い敵機を自動で攻撃する。 if (!attacked && itr->x == X) { itr->h -= LEVEL; attacked = true; // 敵が消える if (itr->h <= 0) { SUM_POWERES += itr->p; LEVEL = SUM_POWERES / 100 + 1; itr = enemys.erase(itr); continue; } } // フィールドに存在する全ての敵機が下に1 // マス移動する。 itr->y--; //フィールド外に移動した敵機は消滅する。 if (itr->y == -1) { itr = enemys.erase(itr); continue; } if (itr->x == X && itr->y == 0) { // 接触してしまった std::quick_exit(0); return; } itr++; } // ターン経過する TURN++; } Action Run() { int best_dx = -INF; int best_to = 0; float best_eval = -INF; rep(x, W) { Solution sol; sol.Xs.push_back(x); sol.Simulate(); const float eval = (float)(sol.power - SUM_POWERES) / (sol.turn * sol.turn + 1); if (best_eval < eval) { best_eval = eval; best_dx = sol.first_dx; best_to = x; } } assert(best_dx != -INF); return best_dx; } Output Solve(const int time_limit) { rep(t, 1000) { bool fin = Input(); if (fin) { std::quick_exit(0); } const auto action = Run(); TurnEnd(action); } std::quick_exit(0); return Output(); } private: }; int main(int argc, char* argv[]) { fast_io; if (argc >= 2) { int idx = 0; for (int i = 1; i < argc; ++i) { PARAMS[idx++] = std::stod(argv[i]); } } Timer timer; timer.start(); Solver solver(cin); auto output = solver.Solve(5850 - timer.ms()); cout << output << endl; return 0; }