Missile ProblemProblem code: CRAFT01 |
You are a Fighter Pilot trainer. Recently you have had an innovative idea of testing the pilots. A series of obstacles will be placed in front of the pilots, and the target will be placed at the other side of the obstacles. The obstacles will have opening in between them. The pilot s test will be to find the perfect opening so that he can hit the target without hitting any of the obstacles.
The problem is that in some combinations of obstacles the target cannot be hit. Your job is to find out if for a given set of obstacles the target is hittable or not.
You are a Fighter Pilot trainer. Recently you have had an innovative idea of testing the pilots. A series of obstacles will be placed in front of the pilots, and the target will be placed at the other side of the
obstacles. The obstacles will have opening in between them. The pilot s test will be to find the perfect opening so that he can hit the target without hitting any of the obstacles.
The problem is that in some combinations of obstacles the target cannot be hit. Your job is to find out if for a given set of obstacles the target is hittable or not. The figure below shows the layout of an example maze.
Input
Your program is to read from standard input. The input consists of T test cases. The number of test cases T (1 T 30) is given in the first line of the input. Each test case starts with a line containing an integer W (2 W 100), the width of an archer line. The next line contains an integer N (2 N 20), the number of obstacles. The i-th line of the following N lines contains three integers Di, Li, Ri (1 Di W, 0 Li < Ri W), where 1 i N, Di represents the y-coordinate of the i-th obstacle, and Li and Ri represent the x-coordinates of the leftmost point and the rightmost point of the opening in the i-th obstacle, respectively. Note that Di Dj if i j.
Output
Your program is to write to standard output. Print exactly one line for each test case. Print YES , if there exists a position on the fire line from which a pilot can hit the target, otherwise, NO .
2 15 4 10 2 7 7 5 12 2 7 12 4 9 13 6 3 2 1 3 4 0 2 5 4 6 Output: YES NO
| Author: | aman871988 |
| Date Added: | 24-02-2010 |
| Time Limit: | 25 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, C, C99 strict, CAML, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, HASK, ICON, JAR, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
how can the first test case
how can the first test case result in yes for the given set of data???? obstacle @ 10 starts at 2 & ends at 7.. whereas obstacle @ 4 starts at 9 and ends at 13 ... so how come.. the result yes????
is there anyone??? what does
is there anyone??? what does this mean "Note that Di Dj if i j." ... in the input statement paragraph?? i still have no clue.. how the first case is giving yes!! :-o
where is the figure ?? plz
where is the figure ??
plz clear the meaning of question.
Is the archer line from A to
Is the archer line from A to B in fig. or the whole fire line from fig. ? Coordinates not given ??
i also cannot
i also cannot understand
please elaborate your first test case
how can the first test case result in yes for the given set of data???? obstacle @ 10 starts at 2 & ends at 7.. whereas obstacle @ 4 starts at 9 and ends at 13 ... so how come.. the result yes????
@Lucky: Whole line is the
@Lucky: Whole line is the fire line. A and B are the just the points on the fire line
what is the positoin of
what is the positoin of target???????????
its not clear from problem statement...
check out the 1st case
check out the 1st case admin....it should give no!!!
yes... i agree with ankit on
yes... i agree with ankit on that one...kindly verify the sampel output for 1st case
I haven't still got the
I haven't still got the correct answer.. but i feel.. the target doesn't need to be in perpendicular direction... we can hit across to... see the first case... you can hit the target by using a tilted line... I hope.. m clear in my point...
Problem statement and test
Problem statement and test cases are correct.
I'm agree with Nitin Kumar.
Yes nitin is right
Yes nitin is right
what does width,W of the
when will the solutions for
when will the solutions for this problem be available???