枚举

小学生计算机程序设计竞赛辅导资料

基础算法——枚举

1．数字反转(reverse)

【问题描述】

给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。

【输入】

输入文件名为 reverse.in。

输入共 1 行，一个整数N。

【输出】

输出文件名为 reverse.out。

输出共 1 行，一个整数，表示反转后的新数。

【输入输出样例 1】

reverse.in reverse.out

123 321

【输入输出样例 2】

reverse.in reverse.out

-380 -83

【数据范围】

-1,000,000,000 ≤ N≤ 1,000,000,000。

2. 吉祥数 (jxs)

【问题描述】 如果一个正整数是8的倍数，并且该数中包含数字8，但不包含数字4，那么我们称该数为吉祥数。

【输入格式】 输入文件为jxs.in

只有一行且只有一个正整数：n

【输出格式】 输出文件为 jxs.out

只有一行且只有一个正整数：闭区间[1,n]中吉祥数的个数。

【输入样例】

10

【输出样例】

1

小学生计算机程序设计竞赛辅导资料

1

【数据规模】

100%的数据：1 <= n <= 10 000 000 内存 <= 2560 KB 时间 <=1秒

3. 三角形问题 (sjx)

【问题描述】 输入绳子的长度n，将该绳子分成三段，每段长度为正整数，输出由该三段绳子组成的三角形个数。

【输入格式】 输入文件为sjx.in

只有一行且只有一个正整数：n

【输出格式】 输出文件为 sjx.out

只有一行且只有一个正整数：可以构成的三角形个数

【输入样例】

7

【输出样例】

2

【数据规模】

100%的数据：1 <= n <= 32 000 内存 <= 2560 KB 时间 <=1秒

4. 解方程（jfc）

【问题描述】三元三次方程：

x+y=z

请编程求出指定范围内的正整数解的个数。

【输入格式】 输入文件为 jfc.in

只有一行且只有一个正整数：n 表示 1 <= x , y , z <= n

【输出格式】 输出文件为 jfc.out

只有一行且只有一个正整数：不同的正整数解的个数

【输入样例】

5

【输出样例】

3

2

332

小学生计算机程序设计竞赛辅导资料

【数据规模】

100%的数据：1 <= n <= 3 000 内存 <= 2560 KB 时间 <=1秒

5.傻瓜电梯（dianti）

【问题描述】

所谓傻瓜电梯指的是在响应用户请求时缺乏相应的“智商” ，在上升或下降的过程中不能把中途的乘客捎带入电梯，而只会严格按照用户发出请求的先后顺序依次完成任务。比如，原来电梯在 1 楼，首先 6 楼有一位乘客发出请求，要求由 6 楼乘坐到 10 楼去，此时电梯马上会上去， 但在电梯上升到 3 楼时， 另外一位乘客请求由 5 楼乘坐到 8 楼去，傻瓜电梯却不会在上升途中把 5 楼的乘客捎带上去，而只会先把 6 楼的乘客送到 10 楼，然后再下来把 5 搂的乘客送到 8 楼。傻瓜电梯由 i 楼上升到 i+1 楼（或下降到 i-1 楼）的时间都是 3 秒，每到达一个楼层，不管进出乘客有多少，也不管乘客只有进、只有出或者进出电梯都有，所耽搁的时间都是 6秒。 现在味味要根据傻瓜电梯接受到的 n 个用户请求， 编程计算傻瓜电梯把所有乘客送到目标楼层时总共所需要的时间。

如果某批乘客到达目标楼层后，电梯没有马上要响应的请求，则电梯在前一批乘客的目的地等待， 这个等待时间也需计入总花费时间。 直到下一批乘客发出新请求， 电梯才会从当前位置出发，前往下一批乘客的出发楼层。

【输入】

输入文件 dianti.in 第一行包含两个整数 x（1<=x<=100）和 n（1<=n<=100） ，分别表示傻瓜电梯开始所在的楼层和总共接收到的请求数目。 下面有 n 行， 每行包含 3 个整数， 依次表示该请求发出的时间、 乘客目前所在的楼层和将要去的目标楼层。 其中请求发出的时间以秒为时刻单位，最大可能的值是 2000。如果某两个请求的发出时间相同，则按照输入文件中原始的先后顺序依次处理。

【输出】

输出文件 dianti.out 只包含一行一个整数，表示傻瓜电梯把所有乘客送到目标楼层后总共所需要的时间（从得到第一条请求时开始计算时间），单位是秒。

【输入样例 1】

3 4

10 10 2

18 1 9

2 1 12

8 6 10

【输出样例1】

3

小学生计算机程序设计竞赛辅导资料

162

【样例 1 解释】

第一批乘客发出请求到离开电梯所需时间：3*2+6+3*11+6=51 从前一批乘客离开电梯到第二批乘客离开电梯所需时间：3*6+6+3*4+6=42 第三批乘客从出发地出发到离开电梯所需时间：3*8+6=30（由于出发地与前一批乘客目的地相同，所以上下客时间不必再加 6）从前一批乘客离开电梯到第四批乘客离开电梯所需时间：3+6+3*8+6=39 总花费时间：51+42+30+39=162

【输入样例 2】

1 2

10 2 3

30 5 1

【输出样例2】

60

4