#pragma GCC optimize("Ofast") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using P = pair; template using V = vector; template using VV = V>; template bool chmin(T& t, const U& u) { if (t > u) { t = u; return 1; } else return 0; } template bool chmax(T& t, const U& u) { if (t < u) { t = u; return 1; } else return 0; } #define REP(i,n) for(int i=0;i=int(b);i--) #define MP make_pair #define SZ(x) int(x.size()) #define ALL(x) x.begin(),x.end() #define INF 10001000 #define endl "\n" chrono::system_clock::time_point t_start; const double TIME_LIMIT1 = 500, TIME_LIMIT = 2930; double last_update = 0, t_diff; double start_temp, end_temp; mt19937 rng; using uni_int = uniform_int_distribution<>; using uni_real = uniform_real_distribution<>; using u64 = uint64_t; using u32 = uint32_t; V y_vec = { 0, 1,0, -1 }; V x_vec = { -1, 0,1, 0 }; class XorInt { public: uint32_t x = 2463534242; XorInt() {}; XorInt(uint32_t seed) { x = 2463534242 + seed; }; uint32_t next() { x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x; } uint32_t operator()(uint32_t l, uint32_t r) { return (this->next() % (r - l)) + l; } uint32_t operator()(uint32_t d) { return this->next() % d; } }; XorInt xs; class Xor64 { public: uint64_t x = 88172645463325252ULL; Xor64() {}; Xor64(uint64_t seed) { x = 88172645463325252ULL + seed; } uint64_t next() { x ^= x << 13; x ^= x >> 7; x ^= x << 17; return x; } uint64_t operator()(uint64_t l, uint64_t r) { return (this->next() % (r - l)) + l; } uint64_t operator()(uint64_t d) { return this->next() % d; } }; Xor64 xx; void get_time() { auto t_now = chrono::system_clock::now(); t_diff = chrono::duration_cast(t_now - t_start).count(); } int H, W, p; int Pos(int x, int y) { return x * W + y; } char Dir(int pos, int npos) { if (pos / H == npos / H) { if (pos < npos)return'R'; else return 'L'; } else { if (pos < npos)return'D'; else return 'U'; } } int move(int pos, char dir) { if (dir == 'U')return pos - W; if (dir == 'R')return pos + 1; if (dir == 'D')return pos + W; if (dir == 'L')return pos - 1; } string Direction = "URDL"; VV pass; class Cell { public: int state = 0; V around4; Cell() {}; }; V grid; string findPath() { int start = 0; int goal = H * W - 1; V d(H * W, INF); V path(H * W, ""); d[0] = 0; priority_queue, greater

> pq; pq.push(MP(0, 0)); while (!pq.empty()) { int dis = pq.top().first; int pos = pq.top().second; pq.pop(); if (dis > d[pos])continue; if (pos == goal)return path[goal]; for (auto npos : grid[pos].around4) { int cost = max(0, pass[pos][npos]); if(pass[pos][npos]==0)cost += xs(1,(100-p)/2); if (chmin(d[npos], d[pos] + cost)) { path[npos] = path[pos] + Dir(pos,npos); pq.push(MP(d[npos], npos)); } } } } void update(string ans, int res) { int pos = 0; REP(i, res) { int npos = move(pos, ans[i]); pass[pos][npos] = -1; pass[npos][pos] = -1; pos = npos; } int npos = move(pos, ans[res]); if (pass[pos][npos] == -1)return; pass[pos][npos] += 100 - p; pass[npos][pos] = pass[pos][npos]; } signed main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(15); t_start = chrono::system_clock::now(); get_time(); cin >> H >> W >> p; grid = V(H * W); pass = VV(H * W, V(H * W)); REP(x, H) { REP(y, W) { V a; REP(k, 4) { int nx = x + x_vec[k]; int ny = y + y_vec[k]; if (nx < 0 || nx >= H || ny < 0 || ny >= W)continue; a.push_back(Pos(nx, ny)); } shuffle(ALL(a),rng); grid[Pos(x, y)].around4 = a; } } while (true) { string ans = findPath(); cerr << ans << endl; cout << ans << endl; cout.flush(); int res; cin >> res; if (res == -1)break; update(ans, res); } cerr << "time: " << int(t_diff) << " ms" << endl; //cerr << "score: " << score << endl; //cerr << "last: " << last_update << endl; //cerr << "cnt: " << cnt << endl; //cerr << "update:" << update_cnt << endl; return 0; }