7177 : 토너먼트 대진
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N개의 팀이 참가하는 토너먼트 대진이 주어집니다. 1번 팀이 대진표의 모든 가능한 재배치(순열) 중에서 토너먼트 우승을 달성할 수 있는 대진표 배치가 존재하는지 여부를 구하십시오.
[제약 조건]
• 팀의 수 N = 2^k (1 ≤ k ≤ 4)
• 승률 행렬의 각 원소는 0.0 이상 1.0 이하의 실수입니다.
[제약 조건]
• 팀의 수 N = 2^k (1 ≤ k ≤ 4)
• 승률 행렬의 각 원소는 0.0 이상 1.0 이하의 실수입니다.
입력 설명
첫째 줄에 팀의 수 N이 주어집니다. (N = 2^k, 1 ≤ k ≤ 4)
둘째 줄부터 N개의 줄에 걸쳐 각 팀이 다른 팀을 이길 확률을 나타내는 N×N 행렬이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 각 팀이 다른 팀을 이길 확률을 나타내는 N×N 행렬이 주어집니다.
출력 설명
우승할 수 있는 대진표 구성이 존재하면 YES, 불가능하면 NO를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
2
0.5 0.3
0.7 0.5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
YES도움
2개 팀 경기에서 1번 팀이 2번 팀을 이길 확률이 0.3 > 0 이므로 우승 가능합니다.