#pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx2") #include #include #include #include #include #include #include #include #include #include #include #include #include struct xorshift64 { unsigned long long int x = 88172645463325252ULL; inline unsigned short nextUShort() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUShortMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x0000ffffffffffff) * mod) >> 48; } inline unsigned int nextUInt() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUIntMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x00000000ffffffff) * mod) >> 32; } inline unsigned long long int nextULL() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline double nextDouble() { x = x ^ (x << 7); x = x ^ (x >> 9); return (double)x * 5.42101086242752217e-20; } }; struct timer { double t = 0.0; double lastStop = 0.0; bool stopped = false; timer() { restart(); } inline void restart() { t = now(); stopped = false; } inline void start() { if (stopped) { t += now() - lastStop; stopped = false; } } inline void stop() { if (!stopped) { lastStop = now(); stopped = true; } } inline double time() { if (stopped) return lastStop - t; else return now() - t; } inline double now() { unsigned long long l, h; __asm__ ("rdtsc" : "=a"(l), "=d"(h)); #ifdef LOCAL return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X) #else //return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2) //return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3) return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL) #endif } }; using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef pair Pii; const ll mod = 1000000007; timer theTimer; xorshift64 theRandom; mt19937 theMersenne(1); // hyper parameters // structs struct { const vector x = { -1, 1, 0, 0}; const vector y = { 0, 0, -1, 1}; const vector c = {'U', 'D', 'L', 'R'}; } delta; // constants constexpr int h = 20; constexpr int w = 20; constexpr int turn_limit = 1001; constexpr int start_x = 0; constexpr int start_y = 0; constexpr int finish_x = h-1; constexpr int finish_y = w-1; vector edge_cost; // inputs double p; // outputs string ans; // internals vector > edge_passable_vertical(h-1, vector(w)); vector > edge_passable_horizontal(h, vector(w-1)); vector > edge_wall_hit_count_vertical(h-1, vector(w)); vector > edge_wall_hit_count_horizontal(h, vector(w-1)); bool within_board(int x, int y) { return 0 <= x && x < h && 0 <= y && y < w; } void receive_first_input() { int _h, _w, _p; cin >> _h >> _w >> _p; p = (double) _p * 0.01; } int answer(string ans) { cout << ans << endl; int res; cin >> res; return res; } void init() { edge_cost = vector(turn_limit); edge_cost[0] = 1.0; for (int i = 1; i < turn_limit; i++) { edge_cost[i] = edge_cost[i-1] * (1.0 / p); } } void solve() { for (int turn_count = 0; turn_count < turn_limit; turn_count++) { // find next path string next_path = ""; { vector > prev_dir(h, vector(w)); // direction to start vector > visited(h, vector(w)); priority_queue, vector >, greater > > que; que.emplace(0, start_x, start_y, '.'); while (!que.empty()) { auto [current_cost, px, py, dir] = que.top(); que.pop(); if (visited[px][py]) continue; visited[px][py] = true; prev_dir[px][py] = dir; if (px == finish_x && py == finish_y) break; for (int d = 0; d < 4; d++) { if (within_board(px + delta.x[d], py + delta.y[d]) && !visited[px + delta.x[d]][py + delta.y[d]]) { if (d & 2) { // horizontal movement assert(delta.x[d] == 0); assert(abs(delta.y[d]) == 1); int wall_y = min(py, py + delta.y[d]); if (edge_passable_horizontal[px + delta.x[d]][wall_y]) { que.emplace(current_cost, px + delta.x[d], py + delta.y[d], delta.c[d ^ 1]); // ^ 1: 180 deg flip } else { que.emplace(current_cost + edge_cost[edge_wall_hit_count_horizontal[px + delta.x[d]][wall_y]], px + delta.x[d], py + delta.y[d], delta.c[d ^ 1]); // ^ 1: 180 deg flip } } else { // vertical movement assert(abs(delta.x[d]) == 1); assert(delta.y[d] == 0); int wall_x = min(px, px + delta.x[d]); if (edge_passable_vertical[wall_x][py + delta.y[d]]) { que.emplace(current_cost, px + delta.x[d], py + delta.y[d], delta.c[d ^ 1]); // ^ 1: 180 deg flip } else { que.emplace(current_cost + edge_cost[edge_wall_hit_count_vertical[wall_x][py + delta.y[d]]], px + delta.x[d], py + delta.y[d], delta.c[d ^ 1]); // ^ 1: 180 deg flip } } } } } { int px = finish_x; int py = finish_y; while (!(px == start_x && py == start_y)) { assert(within_board(px, py)); assert(visited[px][py]); visited[px][py] = false; auto dir = prev_dir[px][py]; for (int d = 0; d < 4; d++) { if (delta.c[d] == dir) { next_path.push_back(delta.c[d ^ 1]); px += delta.x[d]; py += delta.y[d]; break; } } } reverse(next_path.begin(), next_path.end()); } } auto res = answer(next_path); if (res == -1) break; // valid path found else { int px = 0; int py = 0; for (int i = 0; i < res; i++) { for (int d = 0; d < 4; d++) { if (delta.c[d] == next_path[i]) { if (d & 2) { // horizontal movement assert(delta.x[d] == 0); assert(abs(delta.y[d]) == 1); int wall_y = min(py, py + delta.y[d]); edge_passable_horizontal[px + delta.x[d]][wall_y] = true; } else { // vertical movement assert(abs(delta.x[d]) == 1); assert(delta.y[d] == 0); int wall_x = min(px, px + delta.x[d]); edge_passable_vertical[wall_x][py + delta.y[d]] = true; } px += delta.x[d]; py += delta.y[d]; } } } for (int d = 0; d < 4; d++) { if (delta.c[d] == next_path[res]) { if (d & 2) { // horizontal movement assert(delta.x[d] == 0); assert(abs(delta.y[d]) == 1); int wall_y = min(py, py + delta.y[d]); edge_wall_hit_count_horizontal[px + delta.x[d]][wall_y]++; } else { // vertical movement assert(abs(delta.x[d]) == 1); assert(delta.y[d] == 0); int wall_x = min(px, px + delta.x[d]); edge_wall_hit_count_vertical[wall_x][py + delta.y[d]]++; } } } } } } int main(int argc, char *argv[]) { cin.tie(0); ios::sync_with_stdio(false); receive_first_input(); init(); solve(); return 0; }