ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1382. Game with Cards

some tests
Posted by Roks 24 Jan 2009 20:23
4
2 4 3
2 4 4
2 1 1
2 3 4
// 2 1 2 2

4
3 2 1
2 1 1
4 4 4
2 3 1
// 1 1 2 2

2
2 2 2
1 1 1
// 1 1

3
1 2 1
2 3 2
3 1 3
// 1 1 1

Edited by author 24.01.2009 20:24
Re: some tests
Posted by SkorKNURE 24 Jan 2009 20:24
Hint:
Try to build bipartite graph with 2*N edges. Then iteratively find vertice with only one connected edge. This edge will be "true" anyhow, so its pair from the guy's statement is "false". Also "false" are all edges, connected to both vertices of current one, and then you can mark their pairs as "true" ans so on...
Re: some tests
Posted by svr 19 Jun 2009 10:37
What residue graph after this procedure.
Can it have vertices with deg>2?
Logically it must be union of separeted edges(matched vertices) and disjoint circles. But My Ac prog
says that in 9 test residue graph has vertice with deg>2.

Edited by author 20.06.2009 09:17
Re: some tests
Posted by Al.Cash 19 Jun 2009 13:36
I'm not sure how do you build that "residue graph", but the answer is most likely to be "no"))
I would not mind helping you, but don't want to post ideas in forum.

Edited by author 19.06.2009 13:37
some other tests
Posted by taobingxue 12 Sep 2009 19:57
5
5 4 5
5 1 5
4 1 5
4 4 3
4 1 5

5
2 5 4
4 5 1
3 4 3
3 5 5
1 5 5

I hope they can help~
o(∩_∩)o...
Re: some other tests
Posted by IGOR_Lviv NU 19 Nov 2009 17:28
Both of these tests are incorrect. My AC program fails on them.
Re: some other tests
Posted by hoan 12 Dec 2010 17:32
input:
6
1 2 4
2 3 5
3 1 6
1 5 4
5 6 5
6 4 6

output:
1 1 1 2 2 2