BOJ 31490 Throwing dice

문제 링크:

문제 내용

$n$면 주사위 한 개를 던지면 1 이상 $n$ 이하의 정수를 각각 $\frac{1}{n}$의 확률로 얻습니다.

Alice는 면의 개수가 각각 $A_1, A_2, \cdots, A_M$인 주사위 총 $M$개를, Bob은 $B_1, B_2, \cdots, B_N$인 주사위 총 $N$개를 갖고 있습니다. 한 사람이 얻는 점수는 그 사람이 가진 주사위를 모두 던졌을 때 얻는 값들의 총합입니다. 점수가 높은 사람이 승리하며, 점수가 같으면 비깁니다.

각자가 가진 주사위의 목록이 주어질 때, Alice가 이길 확률이 Bob이 이길 확률보다 높은지, 낮은지, 또는 같은지를 구하세요.

입력

첫 번째 줄에는 $M$과 $N$이 주어집니다. ($1 \le M, N \le 100\;000$)

두 번째 줄에는 $A_1, A_2, \cdots, A_M$이 주어집니다. ($4 \le A_i \le 10^9$)

세 번째 줄에는 $B_1, B_2, \cdots, B_N$이 주어집니다. ($4 \le B_i \le 10^9$)

출력

Alice가 이길 확률이 더 높다면 ALICE, Bob이 이길 확률이 더 높다면 BOB, 서로 같다면 TIED를 출력합니다.

문제 풀이