PROBLEM LINK:
Author: Rutvij Menavlikar
Tester: Ishaan Shah, Sanyam Shah, Sambasai Andem and Tejas Chaudhari
Editorialist: Amul Agarwal
DIFFICULTY:
HARD
EXPLANATION:
You start from Coruscant (grid coordinates L9), so start from (12,9). Then you go to your clones, who are on the Kamino system (grid coordinates S15), that is you travel to (19,15) by querying the judge. When you reach Kamino, you query for your perfect copy. The story is based on Star Wars: Episode II - Attack of the Clones and according to the story, you are Jango Fett. Your perfect copy is Boba Fett. So you query “? boba” or “? bobafett”. Then you travel to Geonosis (grid coordinates R16), that is you travel to (18,16) by querying the judge. And finally output “! stay” to end interaction.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int c_x = 12, c_y = 9, k_x = 19, k_y = 15, g_x = 18, g_y = 16;
int n = 20;
pair<int, int> pos = {c_x, c_y};
vector<vector<bool>> v(n + 1, vector<bool>(n + 1, false));
bool srch = true;
void query(int dir, bool special)
{
if (special)
cout << "? bobafett" << endl;
else
{
switch (dir)
{
case 0:
cout << "? left" << endl;
break;
case 1:
cout << "? down" << endl;
break;
case 2:
cout << "? right" << endl;
break;
case 3:
cout << "? up" << endl;
break;
default:
break;
}
}
int l, r;
cin >> l >> r;
pos = {l, r};
}
void end()
{
cout << "! stay" << endl;
}
void travel(pair<int, int> rt, pair<int, int> par, pair<int, int> target)
{
if (rt == target)
{
srch = false;
return;
}
v[rt.first][rt.second] = true;
if (srch and rt.first > 1 and !v[rt.first - 1][rt.second])
{
pair<int, int> prev_pos = pos;
query(0, false);
if (pos != prev_pos)
travel(pos, prev_pos, target);
}
if (srch and rt.second > 1 and !v[rt.first][rt.second - 1])
{
pair<int, int> prev_pos = pos;
query(1, false);
if (pos != prev_pos)
travel(pos, prev_pos, target);
}
if (srch and rt.first < n and !v[rt.first + 1][rt.second])
{
pair<int, int> prev_pos = pos;
query(2, false);
if (pos != prev_pos)
travel(pos, prev_pos, target);
}
if (srch and rt.second < n and !v[rt.first][rt.second + 1])
{
pair<int, int> prev_pos = pos;
query(3, false);
if (pos != prev_pos)
travel(pos, prev_pos, target);
}
if (srch)
{
if (rt.first == par.first)
{
if (rt.second < par.second)
query(3, false);
else
query(1, false);
}
else if (rt.first < par.first)
query(2, false);
else
query(0, false);
}
}
int main()
{
int tc;
cin >> tc;
while (tc--)
{
srch = true;
pos = {c_x, c_y};
v.assign(n + 1, vector<bool>(n + 1, false));
travel(pos, {-1, -1}, {k_x, k_y});
query(0, true);
v.assign(n + 1, vector<bool>(n + 1, false));
srch = true;
travel(pos, {-1, -1}, {g_x, g_y});
end();
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> II;
typedef vector<int> VI;
#define F first
#define S second
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define endl "\n"
int X[] = {0, 1, 0, -1};
int Y[] = {1, 0, -1, 0};
bool reached = false;
int targetX = 19;
int targetY = 15;
int visited[25][25];
II query(int type)
{
if (type == 0)
cout << "? up\n";
else if (type == 1)
cout << "? right\n";
else if (type == 2)
cout << "? down\n";
else if (type == 3)
cout << "? left\n";
else
assert(0);
fflush(stdout);
int x, y;
cin >> x >> y;
return {x, y};
}
void dfs(II u)
{
int x = u.F, y = u.S;
visited[x][y] = 1;
if (x == targetX && y == targetY) {
if (targetX == 19) {
cout << "? boba\n";
fflush(stdout);
int x, y;
cin >> x >> y;
reached = true;
return;
}
else {
cout << "! stay\n";
fflush(stdout);
reached = true;
return;
}
}
FOR(i, 0, 4)
{
int newX = x + X[i];
int newY = y + Y[i];
if (visited[newX][newY] == 1)
continue;
if (newX < 1 || newY < 1)
continue;
if (newX > 20 || newY > 20)
continue;
II v = query(i);
if (v != u) {
assert(v == make_pair(newX, newY));
dfs(v);
if (reached)
return;
query((i + 2) % 4);
}
else
visited[newX][newY] = 1;
}
}
void solve()
{
reached = false;
targetX = 19;
targetY = 15;
memset(visited, 0, sizeof(visited));
dfs({12, 9});
assert(reached);
memset(visited, 0, sizeof(visited));
reached = false;
targetX = 18;
targetY = 16;
dfs({19, 15});
assert(reached);
}
signed main()
{
int totalTests = 1;
cin >> totalTests;
for (int testNo = 1; testNo <= totalTests; testNo++) {
solve();
}
return 0;
}