软件工程学硕与专硕机试题，时长2.5小时

A. 约瑟夫问题

单点时限: 2.0 sec
内存限制: 512 MB

问题描述：

“约瑟夫问题，怎么又是约瑟夫问题。” 我嘟囔着，心里却开始盘算阴谋。
小学的开始，学数组的时候用 Pascal 写约瑟夫问题。
初中的时候，学模拟的时候用 Pascal 写约瑟夫问题。
高中的时候，学指针的时候用 C++ 写约瑟夫问题。
本科的时候，学算法的时候用 Python 写约瑟夫问题。
而现在，考场上，约瑟夫问题卷土重来，却好似没了以前的面目。
你抱怨着从来没有听说过这个问题，所以我只能再给你讲一遍什么是约瑟夫问题：
N 个人围成一圈，每个人按照顺时针的顺序，标号为 1 到 N 。现在从标号为 1 的人开始按照顺时针的顺序报数，数到 M 的人出圈；再由下一个人从 1 开始重新报数，数到 M 的人出圈（需要注意的是，出圈的人将不在参与之后的报数）……
你说你还是没有很清楚，所以我决定给你举一个例子：
5 个人围成一个圈，每次报数为 2 的人将出圈。

所以出圈的顺序为：2、4、1、5、3。

讲到这里，我的阴谋也基本成型了。现在，我会告诉你围成圈的一共有 N 个人，每次数到 M 的人将出圈，你需要 告诉我的是，第 K 个出圈的人的标号。

输入格式

数据第一行包含一个整数 T ，表示测试数据组数。

对于每一组测试数据，包含一行三个整数 N,M,K ，之间用空格隔开，意义参见题面

对于数据范围的约定：

• 对于 50%的数据，保证 \( 1 \leq K \leq N \leq 100, 1 \leq M \leq 100,1 \leq T \leq 50 \);

• 对于 80%的数据，保证 \( 1 \leq K \leq N \leq 10^5,1 \leq M \leq 10^5,1 \leq T \leq 50 \) ；

• 对于 100%的数据，保证 \( 1 \leq K \leq N≤10^{18},1 \leq M \leq 10^{18},1 \leq T \leq 50 且 \min\{M,K\}≤10^6 \) 。

输出格式

对于每组测试数据输出一行包含一个整数，表示答案。

测试样例 1

Input

5
5 2 1
5 2 2
5 2 3
5 2 4
5 2 5

Output

2
4
1
5
3

测试样例2

Input

5
10 3 5
10 5 2
10 1 8
10 8 10
5 6 1

Output

7
10
8
1
1

B. 合法变量

单点时限: 1.0 sec
内存限制: 256 MB

问题描述

马上就要成为研究生了。我决定考考你对基础知识的掌握程度。 我会给你一个不包含空格或者其他空白字符的字符串，请判断是否是 C 语言合法的变量名称。 我保证给你的字符串一定不是 C 语言的保留字。

如果一个字符串是 C 语言合法的变量名称，必须满足以下要求：

• 非保留字。
• 只包含字母、数字及下划线（“_”）。
• 不以数字开头。

输入格式

输入包含一行一个不包含空格或者其他空白字符的字符串，保证字符串的长度不超过 30 。

输出格式

一行，如果它是 C 语言的合法标识符，则输出 “yes” ，否则输出 “no” 。

样例1

Input

iloveyou

Output

yes

样例2

Input

555_failed

Output

no

C. 晚饭吃什么

单点时限: 1.0 sec
内存限制: 256 MB

问题描述

又到了吃晚饭的时间， dx 又来到了熟悉的二楼，面对着众多美食她的选择困难症又犯了。 这时 xxh 提出一个建议，食堂一共有 m 个窗口，将它们按照 1,2,3,⋯,m 来排序。由 xxh 来选择一个数字 n ， dx 按 照 1,2,3,⋯,m,1,2,⋯ 的顺序，直到第 n 个窗口就是 dx 今晚点餐的窗口。

例：食堂一共有 7 个窗口， xxh 给出数字 9，则 dx 将在 2 号窗口点餐。

dx 一口就答应了，但没想到 xxh 给的数字实在是太大了。 dx 根本数不过来，但又不甘心就这样放弃，请想想办 法帮助 dx 找到她今晚点餐的窗口编号。

输入格式

输入数据第一行包含一个整数 \( T ( 1 \leq T \leq 1000 ) \)，表示数据组数。
接下来 T 行，每行包含两个整数\( n,m ( 2 \leq n \leq 10^{1000}, 2 \leq m \leq 10^8 ) \)，表示所选的数字和窗口数量

对于 10%的数据保证\( 2 \leq n \leq 10^9 \)
对于 30%的数据保证 \( 2 \leq n \leq 10^{18} \)
对于 100%的数据保证 \( 2 \leq n \leq 10^{1000} \)

输出格式

输出每行包含一个整数，表示 dx 今晚点餐的窗口编号。

测试样例1

Input

2
148 90
183 50

Output

 58 33 

测试样例2

Input

5
7660882 2070
38198 9970
4287 74680
6108 3957955
76712 15

Output

1882
8288
4287
6108
2

D. 津津的数字压缩法

单点时限: 2.0 sec
内存限制: 512 MB

问题描述

最近津津需要处理一大堆长长的数字，可是她却买不起大容量的 SSD 来存放这些数据。 在一顿深入思考、冷静分析后，津津想出来了这样一个压缩数字的方法：

譬如说，数字 1111122 可以被描述为“ 5 个 1 和 2 个 2 ”，所以可以被压缩为 5122 ；
又譬如，122344111 可被描述为”1 个 1 、2 个 2 、1 个 3 、2 个 4 和 3 个 1“，所以可以被压缩为 1122132431 。

类似的道理， 1111111111 可以压缩为 101 ， 00000000000 可压缩为 110 ， 100200300 可压缩为 112012201320 。

当然在很多情况下这样子压缩反而让数字边长了…但是津津才不管这些呢！ 所以我们的任务是帮助津津按照她的压缩方法压缩她给出的数据，毕竟她开心就好。

输入格式

输入仅一行，包含一个很长很长的非负整数 s （可能会出现前导 0 ）。 数据保证 s 的位数在 1 到 1000 之间。

输出格式

一行，对应的压缩结果。

测试样例1

Input

122344111

Output

1122132431

测试样例2

Input

00000000000

Output

110

E. 财务危机

单点时限: 1.0 sec
内存限制: 256 MB

问题描述

小啵同学毕业之后决定创业。他招聘了 N 名员工，并且为每名员工都配备了一个办公室。
好景不长，仅仅过了一个月，公司就陷入了财务危机。无奈之下，小啵决定只留下 M 个办公室。这也就意味着，所 有的员工需要重新安排办公室。
小啵想知道有多少种不同的安排方法。
请注意，小啵不允许有办公室空出来（否则他就可以租更少的办公室）；办公室没有编号；两个方案被认为是相同 的，当且仅当在两个方案中，每个人的办公室同事都是相同的。
具体请参考样例解释。

输入格式

输入数据仅有一行，包含两个整数 N 和 M，表示员工数量和留下办公室的个数。

对于 50% 的数据，保证\( 1 \leq N \leq 10 \)
对于 80% 的数据，保证 \( 1 \leq N \leq 10^3 \)
对于 100% 的数据，保证 \( 1 \leq N \leq 10^6 \)
对于所有数据均保证 \( 0 \leq M \leq 10^3 且 M \leq N \)

输出格式

输出一个整数 P，代表所有的方案数。 答案可能很大，你只需要对答案模 \( 1000000007 (10^9+7) \)输出即可。

测试样例1

Input

3 2

Output

3

测试样例2

Input

4 3

Output

6

提示

在第一组样例中有 3 种方案：（1，23）（2，13）（3，12）

在第二组样例中有 6 种方案：（1，2，34）（1，3，24）（1，4，23）（2，3，14）（2，4，13）（3，4，12）

F. 超越方程

单点时限: 3.5 sec
内存限制: 256 MB

问题描述

求超越函数\( f(x)=k \cdot x^p−m^x \) ，其中\( k,m,p \in Z+,p \geq 2,m \geq 2 \) ,在闭区间中\( [a,b] \)的最大值。

当然，由于超越函数不具有良好的函数特性，比如：超越函数不一定是单调函数。 于是，为了简化问题，数据中保证 f(x) 在闭区间 [a,b] 中是一个单峰函数，也就是说函数 f(x) 在区间 [a,b] 上只有唯一 的最大值点 C ，而在最大值点 C 的左侧，函数单调增加；在点 C 的右侧，函数单调减少。
是不是感觉很简单呢？

输入格式

第一行一个整数 t ，表示测试组数。 接下来 t 行，每行五个整数 k,m,p,a,b 。

30% 数据满足 \( t=1 , 1 \leq k \leq 10 , 2 \leq m \leq 10 , 2 \leq p \leq 10 , 0 \leq a<b \leq 10 \)
50% 数据满足 \( 1 \leq t \leq 10 , 1 \leq k \leq 100 , 2 \leq m \leq 10 , 2 \leq p \leq 100 , 0 \leq a<b \leq 10^3 \)
70% 数据满足 \( 1 \leq t \leq 10^3 , 1 \leq k \leq 100 , 2 \leq m \leq 10 , 2 \leq p \leq 100 , 0 \leq a<b \leq 10^3 \)
100% 数据满足\( 1 \leq t \leq 10^4 , 1 \leq k \leq 10^6 , 2 \leq m \leq 10^3 , 2 \leq p \leq 10^6 , 0 \leq a<b \leq 10^7 \)

输出格式

共 t 行，每行一个小数 \( x_0 \) 满足\( a < x_0 < b \)， 且满足 f(x0) 是 f(x) 在闭区间 [a,b] 上的最大值。 你的答案和标准答案的绝对误差或相对误差在 \( 10^{-6} \) 之内就会被认为是正确的。

测试样例

Input

1
1 2 2 2 4

Output

3.21243252

温馨提示

1. long double 最大范围约在 \( 10^{4932} \)，long double 输出请用 prinf("%.8Lf\n",ans);或者强制类型转换成 double 都输出。（for c & c++）。
2. double 最大范围约在 \(10^{308} \)，double 输出请用 prinf("%.8lf\n",ans);（for c & c++）。
3. java 请使用 java.math.BigDecimal ，
4. 读入数据量大，请使用 scanf（for c & c++） 。
5. 请一定要认真阅读输入数据的数据约定！！！！！

G. 找数

单点时限: 1.0 sec
内存限制: 256 MB

问题描述

输入一个整数 n( \(2 \leq n \leq 10\) ) ，你需要找到一些 n 位数（允许有前置 0 ，见样例），这些 n 位数均 由 0 ~ n−1 这些数字组成。 并且每个数字恰好只出现一次。此外，这个 n 位数中前 \( n/2 \) 位数组成的数恰好是后 \( n/2 \) 位数组成的数的整 数倍。按从小到大的顺序输出所有满足条件的 n 位数。

输入格式

一个整数 n ( \(2 \leq n \leq 10\) 且 n 为偶数）。

输出格式

每行输出一个 n 位数。 表示满足条件的所有 n 位数，按升序排序。

测试样例

Input

2

Output

01