스내퍼 1초 256MB
문제
스내퍼는 매우 작고 똑똑한 기계 부품이다.
스내퍼는 입력 1개와 출력 1개, 그리고 전구 하나와 스위치 하나로 이루어져 있다.
입력은 다른 스내퍼의 출력과 연결되거나 전선과 연결될 수 있고, 출력은 다른 스내퍼의 입력과 연결될 수 있다.
스내퍼의 전구가 켜져있고 입력선에서 신호가 들어오면, 출력선으로 그 신호를 그대로 보낸다.
반대로, 전구가 꺼져있거나 입력선에서 신호가 들어오지 않으면 출력선으로 신호를 보내지 않는다.
또한, 스내퍼의 스위치를 눌렀을 때 전구의 상태가 바뀔 수 있는데, 만약 입력선에서 신호가 들어오고 있었다면 전구의 상태를 토글한다. (켜져있으면 꺼지고, 꺼져있었으면 켜진다)
신호가 들어오지 않았다면 전구의 상태는 바뀌지 않는다.
n개의 스내퍼가 전구가 꺼진 상태로 일렬로 연결되어 있다.
첫 번째 스내퍼의 입력선에는 항상 신호가 들어오고 있다.
여러분은 모든 스내퍼의 스위치를 동시에 누르는 것만 할 수 있다.
이 때, k번 스위치를 눌렀을 때 가장 오른쪽 스내퍼의 출력선에는 신호가 나가고 있을까?
예를 들어, n=2인 경우에 대해 살펴보자. 스위치를 누르기 전에는 두 스내퍼의 전구가 모두 꺼져있는 상태이다.
스위치를 한 번 누르면, 첫 번째 스내퍼에만 신호가 들어오고 있기 때문에 첫 번째 스내퍼의 전구만 켜지게 된다.
스위치를 한 번 더 누르면, 두 스내퍼 모두 신호가 들어오고 있기 때문에 두 스내퍼 모두 상태가 바뀌며, 첫 번째 스내퍼의 전구는 꺼지고 두 번째 스내퍼의 전구는 켜지게 된다.
입력
첫 번째 줄에 테스트케이스의 개수 T가 주어진다. (1≦T≦10,000)
두 번째 줄부터 T개의 줄에 전구의 개수 n과 스위치를 누른 횟수 k가 공백을 사이에 두고 주어진다.
출력
각 테스트케이스에 대하여 스위치 조작이 끝난후 모든 전구가 켜져 있다면 ON 그렇지 않다면 OFF를 행으로 구분하여 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 30점 | 1≦n≦10, 0≦k≦100 |
| #2 | 70점 | 1≦n≦30, 0≦k≦108 |
예제
4
1 0
1 1
4 0
4 47
OFF
ON
OFF
ON
로그인해야 코드를 작성할 수 있어요.