Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Ibrahim Mesecan.
Saving the Soldiers
"Commander! The battle is continuing. When trying to conquer
the island, several planes have crashed in the air, sir. And,
the soldiers are falling down. Now, the navy fleet was sent
to save the soldiers. "
You know the coordinates of
and the capacity of all ships. You also follow
positions of the soldiers from their GPS signals. If a
soldier falls into the sea, he has to swim towards the
land. If a soldier falls down on any part of a ship
and if there is place in the ship, he can be saved
(each ship can hold the size of ship times 2 soldiers.
If the ship is full, then it cannot take any more
soldiers because the ship may sink, then). If the ship
is full, then the soldier has to swim towards land, again.
Question: On a 2D array, you
are given the ship and sea information. Then you are also
given the coordinates of the soldiers falling. Write a program
that finds the number of soldiers saved by the ships.
Input specification
You will be first given two numbers: the size of 2D array (n)
and the number of soldiers falling (m). Then, you will be
given n lines with n space separated integers where 1 represents
a part of a ship and 0 represents the sea. The following m lines
will contain 2 integers: x and y coordinates of each soldier
falling. Coordinates start from upper left corner (see the figure)
where 0 ≤ n ≤ 100 and
0 ≤ m ≤ 10,000 .
Output specification:
Show one number.
Sample Input
5 8
0 1 0 0 0
1 1 0 0 1
1 1 0 1 1
0 0 0 0 0
0 0 0 0 0
3 3
4 3
4 3
4 3
5 3
5 3
5 3
5 3
|
Sample Output
6
|
Explanation:
We are given 5x5 2D array in which there are
two ships with the sizes 5 and 3. The ship with the size
5 can hold at most 10 (capacity times 2) soldiers,
and the other ship can hold 6 soldiers.
Soldier 1 has fallen to the sea.
The other 7 soldiers have fallen on the ships.
But, only six of them were saved by the ships, because the
ship2 can hold at most 6 soldiers.
Для отправки решений необходимо выполнить вход.
|