레이팅 미적용헛간에서 시간을 보내기 위해 소들은 간단한 주사위 게임을 즐긴다. 그중 하나는 두 주사위 X와 Y로 하는 게임이다. 두 주사위를 모두 굴려서, 더 높은 숫자가 나온 주사위가 이긴다. 둘 다 같은 숫자가 나오면 다시 굴린다(계속 비기는 한 여러 번 다시 굴릴 수 있다). 이 게임에서 X가 이길 가능성이 Y보다 높으면 주사위 X가 주사위 Y를 이긴다고 말한다.
다음의 4면 주사위들을 생각해 보자.
주사위 A의 면에는 숫자 4, 5, 6, 7이 적혀 있다.
주사위 B의 면에는 숫자 2, 4, 5, 10이 적혀 있다.
주사위 C의 면에는 숫자 1, 4, 8, 9가 적혀 있다.
이 주사위들은 꽤 흥미로운 성질을 만족한다. A는 B를 이기고, B는 C를 이기며, C는 또한 A를 이긴다. 특히, 세 주사위 중 어느 것도 나머지 둘을 모두 이기는 "최고"의 주사위가 아니다. 이처럼 어떤 두 주사위도 비기지 않고 어느 한 주사위도 최고가 아닌 경우, 세 주사위의 집합을 "비추이적(non-transitive)"이라고 부른다. 비추이적인 세 주사위의 집합에서 각 주사위는 다른 한 주사위를 이기고, 또 다른 주사위에게 진다.
두 4면 주사위 A와 B의 면에 적힌 숫자가 주어질 때, 세 번째 주사위 C의 면에 숫자를 배정하여 주사위 집합이 비추이적이 되도록 만들 수 있는지 판별하도록 소들을 도와주자. 모든 주사위의 면에 적힌 숫자는 1 이상 10 이하의 정수여야 한다.
출제자: Brian Dean
출제자: Brian Dean
각 입력은 여러 개의 독립적인 테스트 케이스로 이루어지며, 전체 입력 케이스를 해결하려면 모든 테스트 케이스를 올바르게 해결해야 한다. 입력의 첫째 줄에 해결해야 할 테스트 케이스의 수 \(T\)(\(1\le T\le 10\))가 주어진다.
다음 \(T\)개의 줄에 각 테스트 케이스가 8개의 숫자로 주어진다. 주사위 A의 네 면에 적힌 숫자와 주사위 B의 네 면에 적힌 숫자이다. 모든 숫자는 1 이상 10 이하이며, 반드시 정렬되어 있지는 않다. 같은 숫자가 여러 번, 심지어 같은 주사위에 여러 번 나타날 수도 있다.
\(T\)개의 줄을 출력한다. \(k\)번째 줄에는 \(k\)번째 테스트 케이스를 비추이적 주사위 집합으로 만들 수 있는 주사위 C를 설계할 수 있으면 'yes', 그렇지 않으면 'no'를 출력한다.
3
4 5 6 7 2 4 5 10
2 2 2 2 1 1 1 1
1 1 1 1 2 2 2 2yes
no
noThe first test case corresponds to the example given above. In the second test
case, there is no die C that can make the set of dice non-transitive. The
answer is no for the same reason for the third test case.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > January > Bronze