CHAMPS - Michel and the championship
Michel is participating in a championship where each participant have pi (0<=i<=N-1) points. He knows for some pairs of participants an inequality between the points of each one, in the form pA -pB >= C. Now he wants to know if his data is correct, i.e., if its possible to assign points for each participant and satisfy all the inequalities.
Input
The input consists of several test cases (at most 150). The first line of each test case consists of two integers N and M (1<=N<=500, 0<=M<=5000). Then follow M lines of three integers A, B and C, indicating that pA -pB >= C (0<=A,B<=N-1, |C|<=20000).
Output
Print a single line for each test case with 'y' if the data is valid or 'n' if its not.
Example
Input 2 2 0 1 2 1 0 2 4 4 0 1 1 1 2 1 2 3 -2 3 0 1 4 4 0 1 1 1 2 1 2 3 -3 3 0 1 Output n n y
hide comments
smso:
2018-08-05 08:12:39
got SIGSEGV, input may contain characters other than numbers, space and newline |
|
Dario Sindicic:
2015-04-03 09:47:29
0<=A,B<=N-1
|
|
Akimil:
2015-04-02 22:42:35
What is the number of test cases? Until when we read? |
|
Milan:
2015-04-02 01:21:21
I don't understand what is N supposed to do. Someone please explain me this part, thanks. Last edit: 2015-04-02 01:23:37 |
|
Petar Bosnjak:
2015-04-01 18:20:57
We should read input till EOF? |
|
Nikola:
2015-04-01 15:34:13
Can someone please explain this better with less conditions like: pA -pB >= C and 0<=A,B<=N-1, |C|<=20000? |
Added by: | Marcos Kawakami |
Date: | 2012-02-19 |
Time limit: | 1.542s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Author: Guilherme Souza (guirns) |