NavalBattle
TCO07 Sponsor 1 · 2007-03-07 · by Mike Mirzayanov
Problem Statement
Alice and Bob are playing a game called "Naval Battle". The playing field is a row of fieldLength 1x1 squares. At the beginning of the game, Alice placed one or more battleships on the field. Each battleship occupies exactly shipLength consecutive squares. There must be one or more vacant squares between every pair of adjacent battleships. Bob doesn't know how many battleships Alice has placed, and he doesn't know their positions.
Now, Bob starts shooting. For each shot, he says the number of a single square. The squares are numbered from left to right starting with 0. After each shot, Alice tells him if he hit a square that contains a battleship or if he missed.
Bob suspects that Alice is playing dishonestly and providing wrong answers. You are given a
Return the 0-based index of the earliest answer after which Bob can be sure that Alice is playing dishonestly. Return -1 if there is no such move.
Constraints
- fieldLength will be between 1 and 50, inclusive.
- shipLength will be between 1 and fieldLength, inclusive.
- shots will contain between 1 and 50 elements, inclusive.
- Each element of shots will be between 0 and fieldLength-1, inclusive.
- answers will contain exactly n characters, where n is the number of elements in shots.
- answers will contain only the digits '0' and '1'.
1
1
{0}
"1"
Returns: -1
3
2
{0, 2, 1}
"110"
Returns: 1
5
2
{0, 4, 1, 3, 2}
"11110"
Returns: -1
10
1
{4, 7, 8, 2}
"0110"
Returns: 2
Alice canât place two battleships without one or more vacant squares between them.
10
10
{4, 2}
"01"
Returns: 0
Submissions are judged against all 151 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NavalBattle with a public method int firstDishonestMove(int fieldLength, int shipLength, vector<int> shots, string answers) · 151 test cases · 2 s / 256 MB per case