#include // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair; const ll INF=4e18; void print0(){}; template void print0(H h,T... t){cout<void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);} void perr0(){}; template void perr0(H h,T... t){cerr<void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);} void ioinit() { cout<; using tii = tuple; struct point { int i; int j; }; bool operator==(const point &lhs, const point &rhs) { return (lhs.i == rhs.i && lhs.j == rhs.j); } bool operator!=(const point &lhs, const point &rhs) { return !(lhs == rhs); } bool operator<(const point &lhs, const point &rhs) { if (lhs.i != rhs.i) { return lhs.i < rhs.i; } return lhs.j < rhs.j; } std::ostream &operator<<(std::ostream &os, point &pt) { string s; s.push_back('('); s = s + to_string(pt.i); s = s + ", "; s = s + to_string(pt.j); s.push_back(')'); return os << s; } mt19937 engine(0); clock_t start_time; double now() { return 1000.0 * (clock() - start_time) / CLOCKS_PER_SEC; } void marathon_init() { start_time = clock(); random_device seed_gen; engine.seed(seed_gen()); } int randint(int mn, int mx) { int rng = mx - mn + 1; return mn + (engine() % rng); } double uniform(double x, double y) { const int RND = 1e8; double mean = (x + y) / 2.0; double dif = y - mean; double p = double(engine() % RND) / RND; return mean + dif * (1.0 - 2.0 * p); } bool anneal_accept(double new_score, double old_score, double cur_time, double begin_time, double end_time, double begin_temp, double end_temp) { const int ANNEAL_RND = 1e8; const double ANNEAL_EPS = 1e-6; double temp = cur_time * (end_temp - begin_temp) / (end_time - begin_time) + (end_time * begin_temp - end_temp * begin_time) / (end_time - begin_time); return (exp((new_score - old_score) / temp) > double(engine() % ANNEAL_RND) / ANNEAL_RND + ANNEAL_EPS); } const int N = 20; double P; const int R = 0; const int D = 1; const int L = 2; const int U = 3; vector mvs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int c2d(char c) { if (c == 'R') return R; if (c == 'D') return D; if (c == 'L') return L; if (c == 'U') return U; return -1; } char d2c(int d) { if (d == R) return 'R'; if (d == D) return 'D'; if (d == L) return 'L'; if (d == U) return 'U'; return '?'; } vector l_table[N][N]; int l_btable[N][N]; bool l_check_table() { queue que; que.push({0, 0}); vector> done(N, vector(N)); while (que.size()) { point p = que.front(); que.pop(); if (done[p.i][p.j]) continue; done[p.i][p.j] = true; for (auto mv : l_table[p.i][p.j]) { int ni = p.i + mv.i; int nj = p.j + mv.j; que.push({ni, nj}); } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (!done[i][j]) return false; } } return true; } void l_maketable(int M) { if (!LOCAL) return; while (true) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { l_table[i][j].clear(); l_btable[i][j] = 0; } } set wallset; int nwall = 0; while (nwall < M) { if (randint(0, 1) == 0) { // 右 int i = randint(0, N - 1); int j = randint(0, N - 2); tii w = {0, i, j}; if (wallset.count(w)) continue; wallset.insert(w); } else { // 下 int i = randint(0, N - 2); int j = randint(0, N - 1); tii w = {1, i, j}; if (wallset.count(w)) continue; wallset.insert(w); } nwall++; } // RDLU の順 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i + 1 < N && !wallset.count({1, i, j})) { l_table[i][j].push_back({1, 0}); //下 l_btable[i][j] += (1 << D); } if (i - 1 >= 0 && !wallset.count({1, i - 1, j})) { l_table[i][j].push_back({-1, 0}); //上 l_btable[i][j] += (1 << U); } if (j + 1 < N && !wallset.count({0, i, j})) { l_table[i][j].push_back({0, 1}); //右 l_btable[i][j] += (1 << R); } if (j - 1 >= 0 && !wallset.count({0, i, j - 1})) { l_table[i][j].push_back({0, -1}); //左 l_btable[i][j] += (1 << L); } } } if (!l_check_table()) continue; perr("M=", M); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { perr0("・"); if (j + 1 < N && wallset.count({0, i, j})) { perr0("│"); } else { perr0(" "); } } perr0("\n"); for (int j = 0; j < N; j++) { if (i + 1 < N && wallset.count({1, i, j})) { perr0("─"); } else { perr0(" "); } perr0(" "); } perr0("\n"); } break; } } int request(string ops) { cout << ops << endl; if (!LOCAL) { int res; cin >> res; return res; } { bool hitwall = false; point cur = {0, 0}; point goal = {N - 1, N - 1}; for (auto op : ops) { int d = 0; if (op == 'R') { d = R; } else if (op == 'D') { d = D; } else if (op == 'L') { d = L; } else if (op == 'U') { d = U; } else { perr(ops, "!?!?"); assert(false); } if (!(l_btable[cur.i][cur.j] & (1 << d))) { hitwall = true; break; } auto mv = mvs[d]; cur = {cur.i + mv.i, cur.j + mv.j}; } if (!hitwall && cur == goal) { return -1; } } { int opnum = 0; point cur = {0, 0}; for (auto op : ops) { int d = c2d(op); if (!(l_btable[cur.i][cur.j] & (1 << d))) { return opnum; } if (uniform(0.0, 1.0) < P) { return opnum; } auto mv = mvs[d]; cur = {cur.i + mv.i, cur.j + mv.j}; opnum++; } return opnum; } } string rand_combination(string s0, int start_ind) { string s = s0; int r = 0; int d = 0; for (int j = 0; j < start_ind; j++) { if (s[j] == 'R') r++; if (s[j] == 'D') d++; } for (int i = start_ind; i < int(s.size()); i++) { if (r < N - 1 && d < N - 1) { if (randint(0, 1)) { s[i] = 'R'; r++; } else { s[i] = 'D'; d++; } } else if (r < N - 1) { s[i] = 'R'; r++; } else { s[i] = 'D'; d++; } } return s; } string makeop(int opid, vector> &history, unordered_set &hist_ops) { // とりあえず R と D だけ。それで到達できないケースは諦める。 int N2 = 2 * N - 2; int maxlen = 0; // 全探索モード do { int BRUTE_FORCE_START; if (P < 0.071) { BRUTE_FORCE_START = 32; } else if (P < 0.101) { BRUTE_FORCE_START = 30; } else { BRUTE_FORCE_START = 28; } point maxpt = {0, 0}; for (int i = 0; i < N-2; i++) { for (int j = 0; j < N-2; j++) { if (history[i][j].size() == 0) continue; int len = i + j; if (maxlen < len) { maxlen = len; maxpt = {i, j}; } } } if (maxlen < BRUTE_FORCE_START) { break; } int baseind = maxlen + 1; int brute_force_num = N2 - baseind; int r0 = 0; int d0 = 0; { string s = history[maxpt.i][maxpt.j]; for (int j = 0; j < baseind; j++) { if (s[j] == 'R') r0++; if (s[j] == 'D') d0++; } } for (int i = 0; i < (1 << brute_force_num); i++) { string s = history[maxpt.i][maxpt.j]; int r = r0; int d = d0; for (int j = 0; j < brute_force_num; j++) { char c; if ((i >> j) & 1) { c = 'R'; r++; } else { c = 'D'; d++; } s[j + baseind] = c; } if (r > N - 1 || d > N - 1) continue; if (hist_ops.count(s)) continue; return s; } } while (0); // 完全な無作為 if (opid < 20) { string s; s.resize(N2); return rand_combination(s, 0); } // 適当にサンプリング+改変 { vector> sample_candidate; for (int si = 0; si < N; si++) { for (int sj = 0; sj < N; sj++) { if (history[si][sj].size() == 0) continue; int ok = 0; ok += (si + 1 < N && history[si + 1][sj].size() == 0); ok += (sj + 1 < N && history[si][sj + 1].size() == 0); if (ok) { double score = (si + sj) * (si + sj) * (si + sj) - abs(si - sj); sample_candidate.push_back({score, {si, sj}}); } } } sort(sample_candidate.begin(), sample_candidate.end(), [](pair a, pair b) { return a.first > b.first; }); point sample = sample_candidate[0].second; double total = 0; for (auto c : sample_candidate) { total += c.first; } double rat = uniform(0.0, total); double cum = 0; for (auto c : sample_candidate) { cum += c.first; if (rat < cum) { sample = c.second; break; } } // 後ろの方を適当に改変 string sample_str = history[sample.i][sample.j]; int sz = sample_str.size(); int changestart = (sample.i + sample.j) + (-1); if (changestart < 0) changestart = 0; return rand_combination(sample_str, changestart); } return "RDRD"; } void solve() { int opslimit = 1001; if (LOCAL) opslimit = 1000; unordered_set hist_ops; vector> history(N, vector(N, "")); for (int opid = 1; opid <= opslimit; opid++) { string s = makeop(opid, history, hist_ops); int res = request(s); if (res < 0) { perr(opid, "success!"); perr0("score=", 1001 - opid, "\n"); return; } { point cur = {0, 0}; for (int i = 0; i < res; i++) { char c = s[i]; auto mv = mvs[c2d(c)]; point nxt = {cur.i + mv.i, cur.j + mv.j}; if (history[nxt.i][nxt.j].size() == 0) { history[nxt.i][nxt.j] = s; } cur = nxt; } } if (LOCAL) { perr(res); } } perr(opslimit, "failure!"); perr0("score=0\n"); } int main() { marathon_init(); ioinit(); int _h, _w; cin >> _h >> _w >> P; P *= 0.01; int M = 200; if (LOCAL) { cin >> M; } perr("P=", P); l_maketable(M); solve(); return 0; }