BZPRO

#3623. CATS

内存限制：256 MiB 时间限制：2 Sec
提交 提交记录 讨论

题目描述

CATS(Counter and Two Stacks)是一门有一个counter和两个栈的语言。S1和S2是两个栈，初始时候每个栈中有无数个0，压栈和出栈的操作分别为“PUSH”和“POP”。“ADD”取出栈顶两个元素，并把和重新压栈。下程序中T1，T2分别表示S1，S2的栈顶元素。
COUNTER = X
WHILE COUNTER > 0
S2 PUSH T1                      //把S1栈顶元素压入S2
S1 POP                             //S1栈顶元素出栈
FLIP LAST BINARY BIT OF ALL NUMBERS IN S1 //把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
求该程序对于给定输入X,L,N的输出。

输入格式

第一行一个整数Q，接下来Q行每行有三个正整数分别为X,L和N，其中L不是N的倍数。

输出格式

输出共Q行，每行一个整数，为题目程序对于每组X,L和N的输出。

样例

样例输入


			
2

4 5 2

18 6 4

样例输出


			
8

9

样例输入输出解释：.

对于第一组X,L和N，以下为程序循环时栈S1和COUNTER的数值。为了表示方便，只显示栈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。

数据范围与提示



 

数据规模：OJ中只有一组数据，Q=223100，X,N,L<=2^60-1。

BZPRO Powered by Remmina.
Github Repository