HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Volumes > Data Structures > problem:


51044 - Number of Trees

Guest
• Review clarifications (6)

Volume problems

• 50979 - Minimum access cost for BST
• 51000 - Book Index
• 51076 - Key person
• 51062 - Fish Pond II
• 51067 - Jumping frog
• 51080 - Deepest Point
• 51079 - Key person - 2
• 51021 - Number of Nodes
• 51044 - Number of Trees
• 51010 - Max Sequential Sum
• 51086 - Top popular student
• 51072 - Castle on chessboard
• 51015 - Student Scholarships
• 51082 - Sum is equal to K - 1
• 51020 - Number of nodes removed
• 51023 - Preparing Keyword Index
• 51075 - Shortest Path for Bishop

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.

Number of Trees

Question: You have X-by-Y rectangular field and you want to plant trees. There are k parts in the field where you cannot plant anything. And, every tree requires at least w-square-meter. Write a program, that defines the maximum number of trees that you can plant.

Input specification: You will be given four integers in the beginning,

  • the width of the field (X)
  • the length of the field (Y)
  • the width required for every tree (w)
  • the number of objects in the field (k)
where 1 ≤ (X,Y) ≤ 10, 2 ≤ w ≤ 7 and 0 ≤ k ≤ 100. Then, each of the following k lines will have two integers (x, y) coordinates of k objects.

Output specification: Show one integer (the number of trees that can be planted).

Sample Input I
6 5 2 3
1 1
3 2
4 5
Sample Input II
6 5 3 3
1 1
3 2
4 5
Sample Output I
5
Sample Output II
2



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

www.contester.ru