问题描述

奶牛贝茜又回到学校啦！她正在做数学作业，其中她需要将正整数舍入到10的幂。

将一个正整数舍入到最近的 $10^b$，其中 $b$ 是一个正整数，贝茜首先会找到从右往左数的第 $b$ 位数字，记为 $x$。

​ 如果 $x \geq 5$，贝茜会将 $10^b$ 加到当前值上。 ​ 然后，贝茜会将从右往左的第 $b$ 位数字以及其右侧的所有数字设置为 0。

例如，如果贝茜想把 456 舍入到最近的 $10^2$（百位），她会先找到从右往左的第 2 位数字，即 5。这意味着 $x = 5$。因为 $x \geq 5$，贝茜会将 100 加到 0 上。最后，贝茜会将从右往左的第 2 位及其右侧的所有数字设置为 0，得到 500。

然而，如果贝茜将 446 舍入到最近的 $10^2$，结果将是 400。

在查看贝茜的作业后，爱尔西认为自己发明了一种新的舍入方法：链式舍入。为了将数字链式舍入到最近的 $10^b$，爱尔西会首先舍入到最近的 $10^1$，然后是最近的 $10^2$，依此类推，直到最近的 $10^b$。

贝茜认为爱尔西的方法是错的，但她忙于数学作业，没时间验证她的怀疑。于是她让你统计有多少个整数 $x$（满足 $2 \leq x \leq N$，$1 \leq N \leq 10^9$），使得将 $x$ 舍入到最近的 $10^b$ 与链式舍入到最近的 $10^b$ 的结果不同，其中 $P$ 是满足 $10^P \geq x$ 的最小整数。

输入格式

你需要处理多个测试用例。

输入的第一行包含一个整数 $T$（$1 \leq T \leq 10^5$），表示测试用例的数量。接下来的 $T$ 行每行包含一个整数 $N$。每个测试用例的 $N$ 是唯一的。

输出格式

输出 $T$ 行，第 $i$ 行包含一个整数，表示在第 $i$ 个测试用例中，满足条件的整数 $x$ 的数量（$x$ 的范围是 2 到 $N$）。

样例输入

4
1
100
4567
3366

样例输出

0
5
183
60

解释

考虑样例中的第二个测试用例。数字 48 应该被统计，因为 48 链式舍入到最近的 $10^2$ 是 100（$48 \to 50 \to 100$），但 48 舍入到最近的 $10^2$ 是 0。

对于第三个测试用例，有两个整数被统计：48 和 480。48 链式舍入到 100，而不是 0，480 链式舍入到 1000，而不是 0。然而，67 不被统计，因为它链式舍入到 100，与直接舍入的结果相同。

评分标准

输入 2-4：$N \leq 10^3$ 输入 5-7：$N \leq 10^6$ 输入 8-13：无额外限制。

问题作者

Weiming Zhou

---

问题描述

农夫约翰 (Farmer John) 有一块立方体形状的奶酪块，位于三维坐标系中。奶酪块的范围从 $(0, 0, 0)$ 到 $(N, N, N)$，其中 $2 \leq N \leq 1000$。农夫约翰将执行 $Q$ 次操作，其中 $1 \leq Q \leq 2 \cdot 10^5$。

操作说明

每次操作中：

• 农夫约翰会移除奶酪中从坐标 $(x, y, z)$ 开始的 $1 \times 1 \times 1$ 小立方体，并扩展到 $(x+1, y+1, z+1)$，其中 $0 \leq x, y, z < N$。
• 保证操作前该位置有奶酪存在。

任务要求

在每次操作之后，输出一个整数，表示可以将一个 $1 \times 1 \times N$ 的砖块放置在剩余的奶酪块中的不同合法方案的数量。满足以下条件：

1. 砖块不能与被移除的空间重叠。
2. 砖块的每个顶点坐标必须是整数，且在范围 $[0, N ]$ 内。
3. 砖块可以在任意方向上旋转。

---

输入格式

• 第一行包含两个整数 $N$ 和 $Q$。
• 接下来的 $Q$ 行中，每行包含三个整数 $x, y, z$，表示要移除的小立方体的坐标。

---

输出格式

对于每次操作，输出一个整数，表示当前剩余的奶酪块中砖块的不同放置方案数量。

---

样例输入

2 5
0 0 1
0 1 1
1 0 1
1 1 0
1 1 0

样例输出

0
0
1
2
5

经过前三次更新后，横跨 $[0,1] \times [0,2] \times [0,1]$ 的 $1\times2\times1$ 横跨 $[0,1]\times[0,2]\times[0,1]$ 的砖块 没有与剩余的奶酪重叠，因此它对答案有贡献

---

题目描述

农场主约翰正试着向埃尔西描述他最喜欢的 USACO 比赛，但她不明白他为什么这么喜欢。他说："我最喜欢的是贝西说‘It's Mooin'Time’（是哞哞的时候了）并在比赛现场哞哞叫的时候。

埃尔西还是不明白，于是农夫约翰下载了竞赛的文本文件，并试图解释他的意思。比赛被定义为一串长度为 N（3≤N≤20000）的小写字母。“哞 "一般定义为子串$c_i c_j c_j$，其中某个字符$c_i$后面直接出现两个字符$c_j$，而$c_i \neq c_j$。根据农夫约翰的说法，贝西经常哞哞叫，所以如果某个哞哞叫在比赛中出现至少 $F$（$1\le F \leq N$）次，那可能就是贝西发出的。

不过，农夫约翰的下载文件可能已损坏，文本文件中最多可能有一个字符与原始文件不同。考虑到可能出现的错误，请打印贝西可能发出的所有 “哞哞 ”声，按字母顺序排列。

输入格式（输入来自终端/stdin）：

第一行包含 N 和 F，分别代表字符串的长度和贝西发出 “哞哞 ”声的频率阈值。

第二行包含长度为 N 的小写字母字符串，代表比赛

输出格式（打印输出到终端/stdout）：

打印出贝西可能发出的 “哞哞 ”声的数量，然后是按词典排序的 “哞哞 ”声列表。每条 “哞哞 ”声都应单独成行。

输入样例

10 2

zzmoozzmoo

样例输出：

1
moo

在这种情况下，任何字符变化都不会影响答案。贝西发出的唯一一声哞叫是 "moo"。

样例输入

17 2
momoobaaaaaqqqcqq

样例输出：

3
aqq
baa
cqq

输入样例

3 1
ooo

样例输出：

25
aoo
boo
coo
doo
eoo
foo
goo
hoo
ioo
joo
koo
loo
moo
noo
poo
qoo
roo
soo
too
uoo
voo
woo
xoo
yoo

动物园

数据：

数据点 4-8： N≤100

数据点 9-13： 无额外限制。

问题归功于 苏哈斯-纳加尔