2021 软件学院 AK 杯程序设计竞赛 (现场赛)

Problem H. 白茶与千层之塔

在聚会中,白茶听闻有一座千层之塔,塔内有 RTX 9090 Ti,强人工智能 AI 等一系列宝藏,率先到达塔底即可领取。于是白茶前去挑战。

《白茶与千层之塔》和《果冻与千层之塔》仅存在少量差别,你可以使用《果冻与千层之塔》的代码通过《白茶与千层之塔》。

在大断层,有一座无限高的塔,它的最低层是第 1 层。

每一个层都设置有只允许下行的遗物电梯。具体而言,第 k 层设置有一座直达第 k-1 层的电梯(若 k>1)和一座直达第 k-2 层的电梯(若 k>2)。特别地,如果 k \bmod 3 = 1,还额外设置有一座直达第 k-3 层的电梯(若 k>3),此处 \bmod 是取余运算。

假设你一开始位于第 a 层,想要前往第 1 层,你只允许乘坐前面所述的下行电梯,求前往的方案数。

输入

输入包含多组测试用例。

第一行包含一个整数 t \ (1 \leq t \leq 10),表示你需要处理 t 组测试用例。

接下来 t 行每行一组测试用例,各包含两个用空格间隔的整数 a,b \ (2 \leq a \leq 20, b=1)a 为开始所位于的楼层;b 为目标楼层,在本题中为固定值。

输出

对于每组测试用例,在单独的一行输出一个整数,表示答案。

在给定数据范围下,答案不会大于 20000

样例

标准输入 复制文本
2
4 1
20 1
标准输出 复制文本
4
18750

提示

对于测试用例 1,四种方案如下:

  • 4 \to 3 \to 2 \to 1
  • 4 \to 3 \to 1
  • 4 \to 2 \to 1
  • 4 \to 1

登录以提交代码。
单点时限 2 秒
内存限制 512 MB
提交 92
通过 55

A B C D E F G H I J

赛后 17:10 将于三楼机房进行题解讲解。
G 题输入描述有更新,请刷新页面查看。