Technocup 2017 - Elimination Round 2 D. Sea Battle
Problem:
There are N grid on a row, there are A ships, each ship's length is B. Let an int array Array[N] represents the grids. Array[i] == 0 or Array[i] == 1. Ships can only be placed on 0's. Guess some positions that there are at least one grid you guess is occupied by one ship.
Solution:
Method 1:
At first, this problem is complicated by myself at first:
- split the array into some intervals which can be placed ship.
- sort the intervals by their length.
- loop from the shortest interval to longest interval, until you are sure that you are sure that you hit at least a ship.
This is solution one. This is a bit stupid, and its implementation is a little complicated. :-(
Method 2:
We can think solve this problem in the opposite way. First, we place A - 1 ships in the intervals we encountered. Then we know that we must make it impossible to place any ship in remaining intervals.
It's easier than the first solution. And implementation is much simpler. ;-)
Perl Source Code:
All of these two Perl solutions can be accepted.
