#P3623. CATS
CATS
[新加坡 NOI 2014] CATS
题目描述
熊猫先生想用 CATS(Counter and Two Stacks)语言写一个程序。给出 时,他原本想求严格大于 的第 个 的倍数。他用到了负数,并且有些指令被执行了两次。你需要求出下面这段程序实际打印的值。
CATS 可以操作一个计数器 和两个栈 。两栈初始化时各含无穷多个 。普通的 和 分别压入一个数和弹出栈顶。 弹出栈顶的两个数,并压入它们的和。尝试压入负数时,该数不会入栈,整座栈中的每个数(包括无限延伸的部分)都会翻转其二进制最低位。翻转最低位等价于与 异或,例如 和 在翻转后互换。
以下伪代码用 T1 和 T2 分别表示 S1 和 S2 当时的栈顶。每次询问都从两个初始栈开始。
COUNTER = X
WHILE COUNTER > 0
S2 PUSH T1
S1 POP
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
输入格式
第一行一个正整数 ,表示询问数。随后 行各有三个正整数 ,保证 不是 的倍数。
输出格式
输出 行,每行一个整数。第 行是熊猫先生的程序对第 个询问打印的唯一一个整数。
2
4 5 2
18 6 4
8
9
样例解释
表中为第一组询问每次进入循环前的状态,只列出 S1 最上面的四个元素,最左边是栈顶。
| COUNTER | S1 |
|---|---|
| 4 | 0 0 0 0 |
| 4 4 1 1 | |
| 8 8 5 0 | |
| 3 | 9 4 1 1 |
| 2 | 5 0 0 0 |
| 9 9 1 1 | |
| 1 | 8 0 0 0 |
最后一次执行循环时,COUNTER 降到 ,因此打印 。
数据范围
当前 OJ 归档有一份包含 个询问的测试输入,。
原赛六档数据如下。表内数值为上界,第一档的 固定为 。
| 档次 | 分值 | ||||
|---|---|---|---|---|---|
| 1 | 4 | ||||
| 2 | |||||
| 3 | |||||
| 4 | |||||
| 5 | |||||
| 6 | 5 | ||||