| 승리 확률 |
|---|
소규모 토너먼트 대회에서 내가 좋아하는 팀이 우승할 확률을 알고 싶다고 하자. 총 4개의 팀이 있고 한 팀이 다른 모든 팀과 한 번씩 경기를 하게 되면 총 6경기가 열리게 된다. 매 경기에서 가능한 경우의 수는 3가지로 한 팀이 이기는 경우, 다른 팀이 이기는 경우, 무승부인 경우가 그것이다. 그리고 승리한 팀은 3점, 진 팀은 0점, 무승부면 각 팀에 1점을 부여한다. 이때 좋아하는 팀의 점수가 다른 모든 팀의 점수보다 높아야 우승을 할 수 있다. 토너먼트 대회는 아직 끝나지 않았으며 이미 끝난 경기에 대한 결과가 주어질 때, 아직 남아 있는 경기를 통해 내가 좋아하는 팀이 우승할 수 있는 모든 경우의 수를 출력하는 프로그램을 작성하시오. |
| 입력 | |
|---|---|
입력 파일의 첫 번째 줄에 내가 좋아하는 팀이 정수 T(1<=T<=4)가 주어진다. 두 번째 줄에는 이미 끝난 경기의 수가 정수 G(0<=G<=5)가 주어진다. 그 다음의 G개 줄에 각 경기 결과가 주어진다. 각 줄에는 4개의 정수 A, B, SA, SB (1<=A=0)가 1개의 공백을 사이에 두고 주어진다. 이것은 A팀과 B팀의 경기 결과를 의미하는 것으로서 SA는 A팀의 점수, SB는 B팀의 점수를 나타낸다. 단, 동일한 두 팀이 두 번 이상 경기를 하지 않는다. | |
| 출력 | |||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
첫 번째 줄에 팀 T가 남아 있는 경기를 통해 우승할 수 있는 경우의 수를 정수로 출력한다. ※ 예시 1 : 주어진 세 경기에서 팀3은 두 번 졌고, 팀4는 한 번은 동점, 한 번은 이겼기 때문에 팀4는 현재 4점이다. 남아 있는 경기에서 팀3이 이긴다고 하더라도 팀4의 점수를 따라잡을 수 없으므로 팀3는 승리할 수 없다. ※ 예시 2 : 주어진 네 경기의 결과를 토대로 다음의 점수를 계산할 수 있다.
남아 있는 경기는 두 경기(팀3 대 팀2, 팀1 대 팀4)다. 이 두 경기를 통해서 팀1, 2, 4는 어떤 결과가 나오든 총 6점이 될 수 없다. 왜냐하면 팀1, 2, 4가 남아 있는 경기에서 이겨도 점수가 각각 4점, 5점, 4점 밖에 되지 않기 때문이다. 따라서 두 경기가 남아 있고, 가능한 경우의 수 9에 대해서 팀3은 모두 승리할 수 있다.
| |||||||||||||||||||||||||||||||||||||||||
| 예시 | |||
|---|---|---|---|
| 1 | 입력 | 3 3 1 3 7 5 3 4 0 8 2 4 2 2 | |
| 출력 | 0 | ||
| 2 | 입력 | 3 4 1 3 5 7 3 4 8 0 2 4 2 2 1 2 5 5 | |
| 출력 | 9 | ||