럭키 세븐

시간 제한1초메모리 제한1024 MB

요약

K=1에서 시작해 매 턴 두 연산 중 하나를 골라, 마지막 K를 7의 배수로 만들 수 있는지 판정한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

당신은 양의 정수 $K$ 를 하나 가지고 있습니다. 처음에 $K=1$ 입니다.

당신에게는 $N$ 개의 턴이 주어지고, 각 턴에는 $2$ 개의 선택지 중 하나를 골라야합니다. 각각의 선택지는 “+ $v$ ” 혹은 “* $v$ ”와 같은 방식으로 주어집니다. $(1 \le v \le 9)$

“+ $v$ ”: $K$ 를 $K + v$ 로 바꿉니다.
“* $v$ ”: $K$ 를 $K \times v$ 로 바꿉니다.

선택지를 모두 고른 이후 결과로 나온 $K$ 가 $7$ 의 배수가 되도록 할 수 있나요?

입력

첫 줄에 테스트케이스의 수 $T$ 가 주어집니다. $(1 \le T \le 10\\,000)$

각 테스트케이스의 첫 줄에 턴의 수 $N$ 이 주어집니다. $(1 \le N \le 200\\,000)$

다음 $N$ 개의 줄의 $i$ 번째 줄은 “ $op\_1$ $v\_1$ $op\_2$ $v\_2$ ”와 같은 방식으로 모든 문자를 공백으로 구분하여 주어집니다. $op\_1$ 과 $op\_2$ 는 ‘+’ 혹은 ‘*’이며, $v\_1$ 과 $v\_2$ 는 $1$ 이상 $9$ 이하의 정수입니다. 이는 $i$ 번째 턴의 선택지가 “ $op\_1$ $v\_1$ ”과 “ $op\_2$ $v\_2$ ”라는 것을 의미합니다.

모든 테스트케이스에서 $N$ 의 합이 $200\\,000$ 을 넘지 않습니다.

출력

각 테스트케이스마다 한 줄에 하나씩, $K$ 를 $7$ 의 배수로 만들 수 있다면 “LUCKY”, 불가능하다면 “UNLUCKY”를 출력하세요.

예제1

예제 1

입력

3
1
+ 3 + 6
2
+ 3 + 6
+ 1 + 2
5
+ 3 * 1
+ 4 + 5
* 9 * 2
* 6 + 3
* 5 + 5

예상 출력

LUCKY
UNLUCKY
LUCKY