| Submit | All submissions | Best solutions | Back to list |
SGAME - SHAPE GAME |
You probably might have played the game of constructing a figure without lifting up the pencil. But it seems too easy for us.
Let's add some twist to it!
What about start constructing a figure from a point and returning to the same point resulting in the figure without lifting up the pencil.
Note: Figure is bounded and one can't retrace an arc or line.
INPUT SPECIFICATION
Input consists of several test data. There are 't' test cases. For each case you are given the point index 'n' from which to start and end. Then follows two space separated index that define a line from index 'i' to index 'j'. These integers follow up until "-1 -1" is encountered.
OUTPUT SPECIFICATION
Output "YES", if it's possible to construct figure satisfying the specification and "NO" if it's not possible (without quotes).
CONSTRAINTS
t<=100
1<=n<=300
1<=i,j<=300
i!=j
EXAMPLE
Sample Input: 1 1 1 2 1 4 2 3 2 5 2 6 3 6 4 7 5 6 6 7 -1 -1 Sample Output: YES
| Added by: | Swapnil R.Mehta |
| Date: | 2012-12-12 |
| Time limit: | 0.100s |
| Source limit: | 3000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | C C++ 4.3.2 CPP PAS-GPC PAS-FPC PYTHON PYTHON3 |
| Resource: | Own Problem |
hide comments
|
2017-11-19 15:11:21
Very nice problem. Fun to revisit a puzzle that had bothered me since childhood and learn exactly when and why it can be solved or not. |
|
|
2013-08-13 13:15:29 Rocker3011
can't believe so many people says this problem belongs to tutorial. It does not, a simple backtracking would pass on a tutorial question but this required some graph theory and some optimization too. Awesome question :) |
|
|
2013-08-13 13:15:29 mehmetin
It would be better if it is stated that one edge will not be traversed twice. Last edit: 2012-12-26 13:22:13 |
|
|
2013-08-13 13:15:29 Ankit Paharia
If u say testcase is incorrect, then i should ask, is overwriting in a line allowed ??? PS:NO! Last edit: 2012-12-21 03:23:12 |
|
|
2013-08-13 13:15:29 Ankit Paharia
problem description seems quite doubtful... what should be the output for this ... 1 1 2 2 1 -1 -1 PS:The Test Case you provided is incorrect. It should be:- 1 1 2 -1 -1 ->NO! Last edit: 2012-12-20 03:23:23 |
|
|
2013-08-13 13:15:29 Divanshu
Does the figure need to be a closed one? It isn't specifically mentioned, though? PS:There is a possibility of any case belonging to graph. Last edit: 2012-12-20 03:19:26 |
|
|
2013-08-13 13:15:29 Anuraag
Is the input always a connected graph?? PS:All necessary details given in the problem description. Last edit: 2012-12-16 09:01:21 |
|
|
2013-08-13 13:15:29 RAJDEEP GUPTA
I have one query: 1. Is it necessary to use all the lines? PS:Yes you must complete the whole figure. Last edit: 2012-12-16 07:30:53 |
RSS