#include #include using namespace std; using namespace atcoder; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; //using mint = modint1000000007; //using mint = modint998244353; uint32_t xor128() { static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123; uint32_t t; t = (x ^ (x << 11)); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } inline float frand() { return xor128() % UINT32_MAX / static_cast(UINT32_MAX); } struct P { int y, x; double p; }; bool operator<(const P& a, const P& b){ return a.p < b.p; } int H, W; int step; const int MAX_STEP = 1000; double fail_prob; const string angle = "UDLR"; int get_angle(char c){ if(c == 'U') return 0; if(c == 'D') return 1; if(c == 'L') return 2; if(c == 'R') return 3; assert(false); } int vy[4] = {-1,1,0,0}; int vx[4] = {0,0,-1,1}; double get_noise(){ double rate = step / (double)(MAX_STEP-100); if(rate > 1.0) rate = 1.0; double start_base = 1e-9; double end_base = 0.998; double base = start_base + (end_base - start_base) * rate; return base * frand(); } struct Wall { int pass; int stop; Wall():pass(0),stop(0){} double get_prob(){ if(pass > 0) return 1.0 - get_noise(); else return max(1e-100, 0.9 * pow(0.3, stop) - get_noise()); } void count_pass(){ pass++; } void count_stop(){ stop++; } }; Wall wall_right[25][25]; Wall wall_down[25][25]; int inv_k(int k){ assert(0<=k && k<=3); if(k == 0) return 1; if(k == 1) return 0; if(k == 2) return 3; if(k == 3) return 2; } // 移動可能確率 double get_prob(int y, int x, int k){ int ny = y + vy[k]; int nx = x + vx[k]; if(ny<0 || H<=ny || nx<0 || W<=nx) return 1e-100; if(k == 0) return wall_down[ny][nx].get_prob(); if(k == 1) return wall_down[y][x].get_prob(); if(k == 2) return wall_right[ny][nx].get_prob(); if(k == 3) return wall_right[y][x].get_prob(); assert(false); } void update_pass(int y, int x, int k){ int ny = y + vy[k]; int nx = x + vx[k]; if(ny<0 || H<=ny || nx<0 || W<=nx) return; if(k == 0) wall_down[ny][nx].count_pass(); if(k == 1) wall_down[y][x].count_pass(); if(k == 2) wall_right[ny][nx].count_pass(); if(k == 3) wall_right[y][x].count_pass(); } void update_stop(int y, int x, int k){ int ny = y + vy[k]; int nx = x + vx[k]; if(ny<0 || H<=ny || nx<0 || W<=nx) return; if(k == 0) wall_down[ny][nx].count_stop(); if(k == 1) wall_down[y][x].count_stop(); if(k == 2) wall_right[ny][nx].count_stop(); if(k == 3) wall_right[y][x].count_stop(); } double calc_fail_p(int c){ double ret = 0; rep(i,c){ ret += log(1.0 - fail_prob); } ret += log(fail_prob); return exp(ret); } void dump(){ rep(i,H){ rep(j,W){ cout << "(" << wall_down[i][j].get_prob() << "," << wall_right[i][j].get_prob() << ") "; } cout << endl; } } string get_answer(){ vector> dp(H, vector(W, -1e100)); vector> prev(H, vector(W, -1)); priority_queue

que; que.push((P){0,0,0.0}); dp[0][0] = 0.0; while(!que.empty()){ P p = que.top(); que.pop(); if(dp[p.y][p.x] > p.p) continue; rep(k,4){ int ny = p.y + vy[k]; int nx = p.x + vx[k]; if(ny<0 || H<=ny || nx<0 || W<=nx) continue; double logprob = log(get_prob(p.y,p.x,k)); if(dp[ny][nx] < dp[p.y][p.x] + logprob){ dp[ny][nx] = dp[p.y][p.x] + logprob; prev[ny][nx] = inv_k(k); que.push((P){ny,nx,dp[ny][nx]}); } } } int y = H-1, x = W-1; string ret; while(!(y == 0 && x == 0)){ int k = prev[y][x]; ret += angle[inv_k(k)]; y = y + vy[k]; x = x + vx[k]; } reverse(ALLOF(ret)); return ret; }; void update(const string& ans, int fail){ int y = 0, x = 0; rep(i,fail){ int k = get_angle(ans[i]); update_pass(y, x, k); y = y + vy[k]; x = x + vx[k]; } int k = get_angle(ans[fail]); update_stop(y, x, k); } int main(){ xor128(); //change random seed... double fp; cin >> H >> W >> fp; fail_prob = fp / 100.0; step = 0; while(true){ string ans = get_answer(); cout << ans << endl; int ret; cin >> ret; //cerr << step << "\t" << ret << "\t" << ans << endl; if(ret == -1) break; update(ans, ret); step++; } return 0; }