USACO 2022 January Bronze Problem 2

출처:  http://usaco.org/index.php?page=viewproblem2&cpid=1180

---

문제 설명

4면체 주사위 3개(A, B, C) 가 있고, 주사위의 각 면의 숫자는 1부터 10 사이의 숫자이다. 두 주사위를 던져서 높은 숫자가 많이 나오는 주사위가 이겼다고 할때, A > B > C > A 혹은 A < B < C < A 가 되는 조합이 있는지 판별하는 문제이다. 입력으로는 주사위 A, B의 숫자들이 주어진다.

입력

3
4 5 6 7 2 4 5 10
2 2 2 2 1 1 1 1
1 1 1 1 2 2 2 2

출력

yes
no
no

 

---

문제 풀이

주사위 C의 숫자들이 1 ~ 10 이고, 4개의 숫자를 선택할때 가능한 모든 조합 O(N^4)를 해도 10^4 이고, 주사위 2개를 비교해서 편정하는 경우도 4^2 이므로, 전체 계산량은 대략 10^5 정도로 가능하다. 중첩된 Loop 로 모든 경우를 비교하는 알고리즘으로 가능하다. 

프로그램 내용

...
for(i)
	for(j)
    	for(k)
        	for(l)
            	dice_c = {i, j, k, l}
                if( dice_c >dice_b && dice_b >dice_a && dice_a > dice_c)
                	flag = true; break;
				if( dice_b >dice_c && dice_a >dice_b && dice_c > dice_a)
                	flag = true; break;
if(flag)
	cout << "yes"
else
	cout << "no"