Grenade in the Lake!!
Time limit2sMemory limit512 MB
Given people on a line with throw ranges, decide whether the grenade can travel from the first person to the last.
- Level
Easy3 of 10
- Topics
- Greedy, Intervals, Implementation
- Solved
- No attempts yet
Problem
people including Ukje stand in a row on a number line. Ukje stands at , and the positions are given from left to right in nondecreasing order. A person with range can throw the grenade to anyone whose distance is at most , and anyone can catch a grenade thrown at them. When several people share one position, any one of them can catch it and throw it onward.
The grenade starts with Ukje. The game ends quietly when the th person from the left, the rightmost one, receives it. Everyone cooperates, so the game succeeds when at least one relay path reaches that last person. When the grenade falls to the ground, the game fails.
Input
The first line holds with .
The second line holds positions from left to right. The first one is Ukje at . Each position is an integer with .
When , the third line holds ranges in the same order. The first range belongs to Ukje, and the rightmost person is excluded. Each range is an integer with . When , the third line is absent.
Output
When the last person can receive the grenade, print 권병장님, 중대장님이 찾으십니다. Otherwise print 엄마 나 전역 늦어질 것 같아. Print exactly one line including the trailing newline.