2013 Canadian Computing Competition, Stage 1

Problem J5/S3: Chances of winning

You want to determine the chances that your favourite team will be the champion of a small tournament.

There are exactly four teams. At the end of the tournament, a total of six games will have been played with each team playing every other team exactly once. For each game, either one team wins (and the other loses), or the game ends in a tie. If the game does not end in a tie, the winning team is awarded three points and the losing team is awarded zero points. If the game ends in a tie, each team is awarded one point.

Your favourite team will only be the champion if it ends the tournament with strictly more total points than every other team (i.e., a tie for first place is not good enough for your favourite team).

The tournament is not over yet but you know the scores of every game that has already been played. You want to consider all possible ways points could be awarded in the remaining games that have not yet been played and determine in how many of these cases your favourite team will be the tournament champion.

Input

The first line of input will contain an integer T which is your favourite team (1 ≤ T ≤ 4). The second line will contain an integer G, the number of games already played (0 ≤ G ≤ 5). The next G lines will give the results of games that have already been played. Each of these lines will consist of four integers A, B, S_A, S_B separated by single spaces where 1 ≤ A < B ≤ 4, and S_A, S_B ≥ 0. This corresponds to a game between team A (which had score S_A) and team B (which had score S_B) where team A won if S_A > S_B, team B won if S_A < S_B and the game ended in a tie if S_A = S_B. The pairs A and B on the input lines are distinct, since no pair of teams plays twice.

Output

The output will consist of a single integer which is the number of times that team T is the champion over all possible awarding of points in the remaining games in the tournament.

Sample Input 1

3
3
1 3 7 5
3 4 0 8
2 4 2 2

Sample Output 1

0

Explanation

Team 3 has lost two of its three games, and team 4 has tied one and won one, which gives 4 points to team 4. Even if team 3 wins its final game, it cannot have more points than team 4, and thus, will not be champion.

Sample Input 2

3
4
1 3 5 7
3 4 8 0
2 4 2 2
1 2 5 5

Sample Output 2

9

Explanation

After these games, we know the following:

There are two remaining games (team 3 plays team 2; team 1 plays team 4). Teams 1, 2 or 4 cannot achieve 6 points, since even if they win their final games, their final point totals will be 4, 5 and 4 respectively. Thus, out of the 9 possible outcomes (2 matches with 3 different possible results per match), team 3 will be the champion in all 9 outcomes.

All Submissions
Best Solutions

Point Value: 12
Time Limit: 2.00s
Memory Limit: 16M
Added: May 19, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I get both sample test cases right but all the test cases from the judge wrong.

You're just getting the wrong answer. Solving only the sample cases is not good enough to ensure that your program is correct. Make your own test cases.

Also, [url=http://wcipeg.com/comments/view#comment3719]please read this announcement[/url] about question asking. This is your only warning before I delete questions on sight.

There are a lot of things in the announcement. What am I not respecting?

I was referring to:
[quote]On asking questions: post on a problem page if and only if your question is of relevance to everybody (for instance, a clarification question). If your question pertains only to you (such as if your program doesn't work, or if there's something you don't understand about your programming language), please don't clutter up the comments page with it.[/quote]
However, that's probably a bit outdated since we don't really get question spam anymore, and the forum and irc channel aren't running. Ignore that part of my other comment, I guess.

I understand the question, but how does "... out of the 9 possible outcomes (2 matches with 3 different possible results per match)... " make sense?

If there are 3 possible outcomes per match and there are two matches, doesn't that make 2*3=6 outcomes?

2 matches with 3 possible outcomes each:
match 1 --> 3 possibilities
match 2 --> 3 possibilities for each of the 3 results in match 1
3*3 = 9

Ahh.. That makes sense now. I seem to have forgotten a massive part of the question... :/