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 int[] shots, the i-th element of which is the number chosen by Bob on his i-th shot. You are also given a String answers, the i-th character of which is '0' (zero) if Alice tells him that he missed on the i-th shot, or '1' (one) if she tells him that he hit a battleship.
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.
|