We all know the game of battleship, where each player places his ships, and then each player tries to guess the coordinates of the ships. Well, the game of one-dimensional battleship involves the first player setting k of the numbers A[1], A[2], \ldots, A[4 k] equal to 1 and the rest equal to 0. The second player’s goal is to guess some index i for which A[i]=1, and after each guess the first player reveals if it is correct or not.
\begin{array}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
\hline
\end{array}
You are the second player in a game of one-dimensional battleship.
Find, with proof, a deterministic algorithm for playing one-dimensional battleship that requires at most 3 k+1 guesses.