Hide

Problem C
Musical Trees

/problems/musicaltrees/file/statement/en/img-0001.jpg
Source: Pixabay

It’s Christmas time and JW’s $1$-dimensional shop is selling Christmas trees. However, the demand for trees is much higher than the number of trees available. Hence, JW has come up with a special strategy to help decide who gets what tree: a game of Musical Trees!

Musical Trees is much like the game Musical Chairs. There’s a set of trees lined up in a straight ($1$-dimensional) line. At first, everyone starts by wandering around the store while the music is playing. When the music stops, everyone runs to the nearest tree (the tree the smallest distance away) and whoever reaches a tree first gets to the claim that tree. Since people are lazy, they will only ever try to run to the closest tree to them, and hence multiple people may try to get the same tree. Note this means some trees may be unclaimed if they are closest to no one. Also, like in Musical Chairs, no tree can be claimed by more than one person.

The music has just stopped in Musical Trees and as everyone is running to the closest tree, you want to figure out the number of people who won’t get any tree.

Input

The first line consists the number of people $n$ ($1\le n\le 100$) and the number of trees $m$ ($1 \le m \le 100$). The next line contains $n$ integers $p_1,p_2,\ldots ,p_ n$, the positions of all the people when the music stops ($1 \le p_ i \le 1\, 000$). The last line contains $m$ integers $t_1,t_2,\ldots ,t_ m$, the positions of all the trees ($1 \le t_ i \le 1\, 000$). No two people or two trees will have the same position. Some people may try to cheat though, and will already be at the same position as a tree when the music stops. Note that if a person has more than one closest tree to them, they will always go for the one with the smallest $t_ i$.

Output

Output the number of people who won’t get a tree.

Sample Input 1 Sample Output 1
2 3
1 4
2 4 5
0
Sample Input 2 Sample Output 2
3 2
1 5 10
4 6
1
Sample Input 3 Sample Output 3
2 3
3 1
2 5 4
1

Please log in to submit a solution to this problem

Log in