CC BY 4.0 （except where otherwise noted or for reposted articles）
A problem I solved during team practice. A really nice interactive problem I think. “How can you force the judge program to give you the output you want?” At the same time, the solution felt relatively simple once I went down that line of reasoning.
Problem
The problem is about the classic game of Battleships with the only difference that all ships are of size $5 \times 1$. The judge will “lie” about the result of your shots (under the constraints that it doesn’t cause a contradiction) and your goal is to sink all $k$ ships of the judge on a $n \times n$ grid within 2500 shots. $(5 \le n \le 100; 1 \le k \le 10)$
Solution
First of all, we want to somehow force the judge to a point where it can no longer “lie”. Obviously, the simplest way of doing this would be to shoot every cell in the grid. But this would be way over our 2500 shots limit in the worst case. We need to somehow reduce the number of shots while still covering all cells which may be part of a ship.
Let’s focus on the fact that the ships are all of a fixed size of $5 \times 1$. Thus, if we can place our shots such that any 5 horizontally or vertically consecutive cells contains at least 1 shot cell, all ships are bound to have been shot at least once. We can think of the following placement.
xooooxoooox
oxooooxoooo
ooxooooxooo
oooxooooxoo
ooooxooooxo
xooooxoooox
oxooooxoooo
ooxooooxooo
oooxooooxoo
ooooxooooxo
xooooxoooox
x represents a shot. o represents an empty cell.
Then, for all such cells which the judge responded with “hit”. Shoot 4 more cells to the top, bottom, left, and right of the grid. This way, we are bound to have sunk all ships.
Do be careful to return immediately once you’ve received $k$ “sink” responses.
Code (C++)
#include <bits/stdc++.h>
using namespace std;
// #define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
template <typename Q> using rpq = priority_queue<Q, vector<Q>, greater<Q> >;
const int INF = 0x3f3f3f3f;
const ll LLINF = 4'500'000'000'000'000'000;
const ll MOD = 1'000'000'007;
bool shot[105][105];
vector<pii>shots; int sunk = 0;
vector<pii>valid;
int main(){
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.setf(ios::fixed); cout.precision(PRECISION);
int n, k; cin >> n >> k;
int y = 5; for(int x=1; x<=n; x++){
if(y == 0) y = 5;
for(int ny = y; ny <= n; ny += 5){
shots.push_back({x, ny});
} y--;
}
for(auto i:shots){
cout << i.fr << ' ' << i.sc << endl;
shot[i.fr][i.sc] = 1;
string res; cin >> res;
if(res == "miss") {
continue;
}
if(res == "hit" || res == "sunk"){
if(res == "sunk") {
sunk++;
if(sunk == k) return 0;
}
valid.push_back(i);
}
}
for(auto i:valid){
// 왼
string res;
int x = i.fr - 1, y = i.sc;
while(x > 0 && x >= i.fr - 4){
if(!shot[x][y]){
shot[x][y] = 1;
cout << x << ' ' << y << endl;
cin >> res;
if(res == "sunk") sunk++;
if(sunk == k) return 0;
}
x--;
}
// 오른
x = i.fr + 1, y = i.sc;
while(x <= n && x <= i.fr + 4){
if(!shot[x][y]){
shot[x][y] = 1;
cout << x << ' ' << y << endl;
cin >> res;
if(res == "sunk") sunk++;
if(sunk == k) return 0;
}
x++;
}
// 위
x = i.fr , y = i.sc + 1;
while(y <= n && y <= i.sc + 4){
if(!shot[x][y]){
shot[x][y] = 1;
cout << x << ' ' << y << endl;
cin >> res;
if(res == "sunk") sunk++;
if(sunk == k) return 0;
}
y++;
}
// 아래
x = i.fr, y = i.sc - 1;
while(y > 0 && y >= i.sc - 4){
if(!shot[x][y]){
shot[x][y] = 1;
cout << x << ' ' << y << endl;
cin >> res;
if(res == "sunk") sunk++;
if(sunk == k) return 0;
}
y--;
}
}
}