oj.uz

문제 보기 - CATS (NOI14_cats)

CATS Batch 컴파일 명령

시간 제한 메모리 제한 제출 횟수 통과한 사람 수 비율
1500 ms 256 MiB 176 18 10.23%

난해한 프로그래밍 언어는 프로그래밍의 한계를 시험하기 위해, 또는 단지 사람들을 웃기기 위해 만들어진 프로그래밍 언어입니다. 어느 날, 승현이는 Counter and Two Stacks (CATS)라고 불리는 난해한 프로그래밍 언어를 가지고 놀고 있었습니다. 이 언어는 여러 가지 기본적인 연산들을 통하여 카운터 (COUNTER)와 두 개의 스택(S1과 S2)를 다룰 수 있도록 설계되었습니다.

초기에, 두 스택 모두 무한한 수의 0들로 초기화되어 있습니다. 데이터들은 PUSH 또는 POP 연산을 통하여 스택에 더해지거나 빼내질 수 있습니다. 추가적인 연산인 ADD는 스택의 맨 위에 있는 두 개의 원소를 빼내고, 이들을 더한 뒤 그 값을 해당하는 스택에 다시 넣습니다. 승현이는 이 언어를 사용한지 얼마 안 됐기 때문에 단순한 문제를 해결하기로 했습니다: "세 개의 정수 $X, L, N$이 주어질 때, $L$보다 큰 $N$의 배수들 중 $X$번째로 작은 것의 값을 구하시오." 승현이는 편의상 코드를 짤 때 프로그램이 음수를 사용하도록 했으며, $L$이 $N$의 배수인 경우는 고려하지 않았습니다.

승현이는 이 언어를 처음 다루어 보았기 때문에 정확한 답을 출력하지 않습니다. 더욱이, 그는 이 언어에서 사용하는 스택들이 음수를 다룰 수 없다는 사실을 몰랐습니다. CATS에서, 코드가 PUSH 연산을 사용하여 스택에 음수를 넣으려고 시도하면, 이 숫자는 스택에 들어가지 않습니다. 대신 CATS는 이상하게 동작하여 그 스택 안에 있는 모든 숫자들의 마지막 비트가 뒤집힐 것입니다. (스택의 크기가 무한함에 유의하세요) 예로 들어, $4 = 100_{2}$는 $5 = 101_{2}$로 변할 것입니다. 숫자 $X$의 마지막 비트를 뒤집는 것은 C/C++에서 (X ^ 1)을 행하는 것과 같습니다.

게다가 승현이는 실수로 몇 개의 연산들을 두 번 행하도록 했습니다. 결과적으로 승현이가 짠 코드는 아래와 같이 쓸 수 있습니다. 여기서 T1과 T2는 각각 스택 S1과 S2의 맨 위에 위치한 원소를 가리킵니다.

COUNTER = X
WHILE COUNTER > 0
    S2 PUSH T1  //Push the top element of S1 onto S2
    S1 POP      //Pop the top element of S1
    FLIP LAST BINARY BIT OF ALL NUMBERS IN S1
    IF T2 > L
        COUNTER = COUNTER - 1
        IF COUNTER == 0 PRINT T2
    ELSE
        S2 PUSH N
        S2 PUSH N
        S2 ADD
        S2 ADD
        S1 PUSH T2
        S1 PUSH T2
        S2 POP
        S2 POP

승현이의 코드는 동작하는 데 너무 오래 걸려서 버그를 잡는 게 너무 힘들다고 합니다. 승현이가 출력값을 빠르게 알 수 있도록 도와주세요!

입력 형식

첫 번째 줄에는 쿼리의 수 $Q$가 주어집니다. 다음 $Q$개 줄에는 3개의 자연수 $X, L, N$이 공백을 사이로 두고 주어집니다. 위에서 명시했듯이 $L$은 $N$의 배수가 아닙니다.

출력 형식

각 쿼리마다 승현이의 코드가 출력한 값을 한 줄에 하나씩 출력합니다. 승현이의 코드가 각 쿼리마다 정확히 1개의 정수를 출력한다는 것은 보장됩니다.

서브태스크

  1. (4점) $Q = 1$, $X \le 1,000,000$, $L \le 20$, $N \le 20$.
  2. (4점) $Q \le 50$, $X \le 1,000,000$, $L \le 50$, $N \le 20$.
  3. (4점) $Q \le 500$, $X \le 1,000,000$, $L \le 80$, $N \le 20$.
  4. (4점) $Q \le 1,000$, $X \le 1,000,000$, $L \le 1,000,000$, $N \le 1,000,000$.
  5. (4점) $Q \le 10,000$, $X \le 2^{30} - 1$, $L \le 2^{30} - 1$, $N \le 2^{30} - 1$.
  6. (5점) $Q \le 100,000$, $X \le 2^{60} - 1$, $L \le 2^{60} - 1$, $N \le 2^{60} - 1$.
입력 출력
2
4 5 2
18 6 4		 8
9

첫 번째 쿼리가 주어질 때, 승현이의 코드에서 WHILE 루프가 반복될 때마다 COUNTER의 값과 S1 내부의 값들을 추적한 결과입니다. 편의상 S1의 맨 위 4개 원소만 보여집니다. 각 줄의 가장 왼쪽에 위치한 숫자가 S1의 맨 위에 있는 원소를 의미합니다.

COUNTER: 4
S1: 0000...

COUNTER: 4
S1: 4411...

COUNTER: 4
S1: 8850...

COUNTER: 3
S1: 9411...

COUNTER: 2
S1: 5000...

COUNTER: 2
S1: 9911...

COUNTER: 1
S1: 8000...

다음 반복에서 COUNTER는 0이 되어 8이 출력됩니다.

출처