ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > IMPC16 Group Contests > задача:


F2. 50936 - Saving the Soldiers

IMPC16 Group Contests

Старт: 16.янв.2016 в 10:00:00
Финиш: 16.янв.2016 в 14:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (3)

Задачи турнира

• 23. 50875 - Take m-out
• 24. 50876 - He is my cousin
• 25. 50877 - Friendly Queue
• 32. 50926 - School Mail Merge
• 33. 50927 - Health Expenses
• 34. 50928 - War Of Battleships
• 35. 50929 - Present from your uncles
• F1. 50841 - My grand-grand-grandfa...
• F2. 50936 - Saving the Soldiers
• F4. 50977 - Gaussian Elimination
• F5. 50978 - Albanian Coders
• F6. 50979 - Minimum access cost for...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
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.



Для отправки решений необходимо выполнить вход.

www.contester.ru