CodeRo's blog

By CodeRo, history, 7 weeks ago, In English

Question Details A group of monkeys are living in Sunderbans forests. There are N trees in Sunderbans (numbered from 0 to N-1) on which these monkeys live. Every year floods hit the forest of Sunderbans. The monkeys have a tradition of meeting on a tree after the flood.

Last night Sunderbans has been hit hard by a sudden flood. The flood was very strong and it has submerged everything except the mighty trees on which the monkeys live.

All the monkeys now have to meet on some tree. Due to the flood the trees have become weak so jumping from them is dangerous. Whenever a monkey jumps fro m a tree A to a tree B, the tree A gets submerged a little while the tree B remains unaffected. The monkeys don't know how to swim. So, they move from one tree to another tree by jumping. Every tree has been assigned a 2D — coordinate value. A monkey can only jump between two trees if the euclidean distance between them is less than or equal to C. C is called the jumping capacity of the monkeys.

The trees have threshold values. The threshold value of the ith tree is given by ti. It means that no more than ti monkeys can jump off from the ith tree. You are given the coordinates of the trees, their threshold values, the number of monkeys on the trees, and the jumping capacity of the monkeys. You have to tell the number of trees on which all monkeys can meet after the flood. The meeting can happen on a tree if all the monkeys can come to this tree.

Input Format The first line of input contains 2 integers N and C, denoting the number of trees and the jumping capacity of the monkeys.

Following N lines contains xi yi mi ti — the x-coordinate of the ith tree, the y-coordinate of the ith tree, the number of monkeys on the ith tree and the maximum number of monkeys that can jump off from the ith tree.

The last line of the input is kept blank.

Output Format One line with space separated integers denoting the numbers of the trees on which the meeting can happen. These numbers should be in ascending order and should be from 0 to N-1. If there is no tree on which the meeting can happen then print -1.

Constraints 1 <= N <= 200

0 <= C <= 100, 000

-100, 00 <= xi, yi <= 100, 00

0 <= mi <= 15

1 <= ti <= 200

Sample Test Case 1 3 100.0

1 10 5 5

5 10 5 1

8 10 5 4

Sample Output 1

-1

Sample Test Case 2 3 100.0

1 10 5 20

5 10 5 20

8 10 5 20

Sample Output 2

0 1 2

 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

you can see there exits three cases .

1.there exits more than one tree where mi > ti. (ans=-1) 2.when there is at most one such tree. 3.No such tree exits.

for case 2 look if its possible for all monkeys to meet at that tree.

for case 3 :

you need to make a graph where all nodes are connected to each other so basically n*(n-1)/2 edges and just try to make MST and if maximum weight in MST is greater than C than only ans is -1.

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Hi, please prefer posting the link to the question. There's no way for us to know if it's from an ongoing contest.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am Sorry! I will keep that in mind. I request you to kindly help if you can. Thanks!