CCC '13 S3 - Chances of Winning - DMOJ: Modern Online Judge

CCC '13 S3 - Chances of Winning

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2013 Stage 1, Junior #5, Senior #3

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 Specification

The first line of input will contain an integer $T$ $T$ which is your favourite team ( $1 \le T \le 4$ $1 \leq T \leq 4$ ). The second line will contain an integer $G$ $G$ , the number of games already played ( $0 \le G \le 5$ $0 \leq G \leq 5$ ).

The next $G$ $G$ lines will give the results of games that have already been played. Each of these lines will consist of four integers $A$ $A$ , $B$ $B$ , $S_A$ $S_{A}$ , $S_B$ $S_{B}$ separated by single spaces where $1 \le A < B \le 4$ $1 \leq A < B \leq 4$ , and $S_A, S_B \ge 0$ $S_{A}, S_{B} \geq 0$ . This corresponds to a game between team $A$ $A$ (which had score $S_A$ $S_{A}$ ) and team $B$ $B$ (which had score $S_B$ $S_{B}$ ) where team $A$ $A$ won if $S_A > S_B$ $S_{A} > S_{B}$ , team $B$ $B$ won if $S_A < S_B$ $S_{A} < S_{B}$ and the game ended in a tie if $S_A = S_B$ $S_{A} = S_{B}$ . The pairs $A$ $A$ and $B$ $B$ on the input lines are distinct, since no pair of teams plays twice.

Output Specification

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

Sample Input 1

Copy

Output for Sample Input 1

Copy

Explanation of Output for Sample Input 1

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

Copy

Output for Sample Input 2

Copy

Explanation of Output for Sample Input 2

After these games, we know the following:

Team	Points
1	1
2	2
3	6
4	1

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.

Comments

0
gj504772 commented on Feb. 11, 2024, 1:46 a.m. ← edited →
I think this is the combination match if anyone need it, 0 means team 1 and so on

Copy
match_ups = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

10

ColonelBy_team10 commented on Nov. 13, 2021, 7:54 p.m. ← edited →

Tips for Python Users: SUBMIT WITH PYTHON, NOT PYPY. You are searching through at most $3^5$ $3^{5}$ games i.e. $243$ $243$ games. You do not need the speed. YOU WILL NEED THE MEMORY

-12

kopichiki commented on Aug. 18, 2022, 9:42 p.m.

PyPy has more accepted solutions than Python.

PyPy Solutions: https://dmoj.ca/problem/ccc13s3/submissions/?language=PYPY&language=PYPY3

Python Solutions: https://dmoj.ca/problem/ccc13s3/submissions/?language=PY2&language=PY3

This comment is hidden due to too much negative feedback. Show it anyway.

1

Someone_you_can_trust commented on Feb. 16, 2021, 12:50 a.m.

Can anyone explain why does it say 9 instead of 6 in the sample output 2 ?

2

darek commented on April 22, 2022, 1:04 p.m. ← edited →

3 ** 2 = 9

-6

trant8381 commented on Dec. 24, 2021, 9:08 p.m.

They're using a different counting system, as in example 2's explanation. This threw me so bad....

This comment is hidden due to too much negative feedback. Show it anyway.

-73

Sonicforhire commented on July 12, 2019, 3:26 p.m.

how the hell does this work: "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." Let's break this down. You are the third team, therefore, you can play a maximum of three games before you have to replay another team. Thus, you need to play every team TWO TIMES in order to fullfill this requirement. However, this contradicts the last part of the sentence, which it "playing every other team exactly once"

This comment is hidden due to too much negative feedback. Show it anyway.

20

Dingledooper commented on July 12, 2019, 8:17 p.m.

Well the other three teams are also playing against each other, so not every game is played with you.

-55

Sonicforhire commented on July 13, 2019, 2:44 a.m. ← edited →

Its the same thing for them though. They play you, and then they play the two other teams. They still need to play 3 more games regardless

EDIT: Nvm It makes sense now

This comment is hidden due to too much negative feedback. Show it anyway.

5

bloxblox commented on Feb. 11, 2019, 3:20 a.m.

when I try to solve this using recursion and arrays I can't pass sample cases but when I change all my arrays to vectors I AC. Anyone know why this happens?

8

Neon commented on Feb. 11, 2020, 1:13 a.m.

vectors are mutable hence they adapt to your recursive calls