BOJ 26017 Guessing Game

문제 링크:

문제 내용

월요일부터 일요일까지 일주일 동안 열리는 경기 이벤트가 있습니다. 이 이벤트의 참가자들은 팀 레드와 팀 블루로 나뉘어서 경기에 참가하며, $i$번째 날에는 $d_i$개의 경기가 열립니다. 각 경기의 엔트리는 그 경기가 열리기 일주일 전에 공개됩니다.

당신은 $n$명의 친구들과 내기를 하려고 합니다. 하루에 한 경기씩을 골라 총 7개의 경기에 대해 팀 레드가 이길지, 팀 블루가 이길지를 예측하는 방식입니다. 예측이 맞은 경기의 수가 가장 많은 사람이 우승합니다.

하지만, 당신은 예측을 제때 내지 않았다는 사실을 뒤늦게 깨달았습니다. 엔트리가 공개된 경기는 예측을 써낼 수 없으므로, 마지막 이틀에 대한 예측만 써서 내려고 합니다. 이때 당신이 우승할 확률이 조금이라도 있을까요?

입력

첫 번째 줄에는 친구들의 수 $n$이 주어집니다. ($1 \le n \le 50\;000$)

두 번째 줄에는 각 날짜에 열리는 경기의 수 $d_1, d_2, \cdots, d_7$이 주어집니다. ($\sum d_i \le 100\;000$)

다음 $n$줄에 걸쳐서, 각각의 친구가 예측한 7경기의 승자가 주어집니다. 각각의 날짜에 대해, 그 날의 $x$번째 경기를 팀 레드가 이길 것이라고 예측했다면 $x$가, 팀 블루가 이길 것이라고 예측했다면 $-x$가 주어집니다.

마지막으로, 당신이 예측한 두 경기의 승자가 같은 형식으로 주어집니다. 첫 번째 수는 6번째 날에 대한 예측이고, 두 번째 수는 7번째 날에 대한 예측입니다.

출력

당신이 우승할 가능성이 있으면 possible, 없으면 impossible을 출력합니다.

문제 풀이