#include #include #include #include #include #include #include #include using namespace std; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using modint = atcoder::static_modint<1000000007>; const int H = 20; const int W = 20; const int dx[4] = { 0, 1, 0, -1 }; const int dy[4] = { 1, 0, -1, 0 }; const string DIRCHAR = "DRUL"; template using nega_queue = priority_queue, greater>; double p; double log_p; double HEdge[H-1][W]; double VEdge[H][W-1]; void initEdge(){ rep(y,H-1) rep(x,W) HEdge[y][x] = 0.3; rep(y,H) rep(x,W-1) VEdge[y][x] = 0.3; } struct Pos { int y, x; Pos movedByDirection(int dir) const { Pos res; res.x = x + dx[dir]; res.y = y + dy[dir]; return res; } bool isInBoard() const { return 0 <= y && 0 <= x && y < H && x < W; } double& dirCostRef(int dir) const { if(!movedByDirection(dir).isInBoard()) exit(1); if(dir > 4) exit(1); switch(DIRCHAR[dir]){ case 'L' : return VEdge[y][x-1]; case 'R' : return VEdge[y][x]; case 'U' : return HEdge[y-1][x]; case 'D' : return HEdge[y][x]; } exit(1); } double dirCost(int dir) const { if(!movedByDirection(dir).isInBoard()) return 1.0e100; if(dir > 4) return 1.0e100; switch(DIRCHAR[dir]){ case 'L' : return VEdge[y][x-1]; case 'R' : return VEdge[y][x]; case 'U' : return HEdge[y-1][x]; case 'D' : return HEdge[y][x]; } return 1.0e100; } static Pos getGoal(){ return Pos{ H-1, W-1 }; } }; vector dijkstra(){ static double dist[H][W]; static int prevdir[H][W]; rep(y,H) rep(x,W) dist[y][x] = 1.0e100; rep(y,H) rep(x,W) prevdir[y][x] = -1; dist[0][0] = 0; struct DijkstraNode{ double d; Pos p; bool operator>(const DijkstraNode& r) const { return d > r.d; } }; nega_queue A; A.push({ 0.0, Pos{0, 0} }); while(A.size()){ auto [d,pos] = A.top(); A.pop(); if(dist[pos.y][pos.x] != d) continue; rep(dir,4){ Pos nx = pos.movedByDirection(dir); if(!nx.isInBoard()) continue; double nxd = pos.dirCost(dir) + d; if(dist[nx.y][nx.x] <= nxd) continue; dist[nx.y][nx.x] = nxd; prevdir[nx.y][nx.x] = dir; A.push({ nxd, nx }); } } Pos p = Pos::getGoal(); vector res; while(prevdir[p.y][p.x] != -1){ res.push_back(prevdir[p.y][p.x]); p = p.movedByDirection(prevdir[p.y][p.x] ^ 2); } reverse(res.begin(), res.end()); return res; } int ask(vector D){ string S; for(int d : D) S.push_back(DIRCHAR[d]); cout << S << '\n' << flush; int res; cin >> res; if(res == -1) exit(0); Pos p = { 0, 0 }; for(int i=0; i> h >> w >> pp; p = pp / 100.0; log_p = log(p); while(solve()); return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;