2015年安庆市迎江区青少年信息学奥林匹克竞赛试题.pdf

2015 年安庆市迎江区青少年信息学奥林匹克竞赛试题 2015年1 月31 日 （周六）上午8：30－－11：30 一、题目概况 题 目名称 数学黑洞 谁是冠军 置车问题 二叉查找树 源程序名 hole.pas/c/cpp champion.pas/c/cpp vehicle.pas/c/cpp tree.pas/c/cpp 输入文件名 hole.in Champion.in vehicle.in tree.in 输出文件名 hole.out champion.out vehicle.out tree.out 试题类 传统型 传统型 传统型 传统型 满 分 100 100 100 100 是否有部分 否 否 否 否 分 二、注意事项 1. 务必看清题目，严格按照所要求的格式输入、输出。 2. 在调试程序时请先使用题目 的示例数据，然后再自行设计多组测试数据进行调 试。 3. 每题一般有10个测试点，测试有严格的时间限制，请尽可能优化算法。 4. 命名规则： (1)每题都规定了该题的英文名称。 (2)程序文件和数据文件的主文件名都是该题的英文名字。 (3)程序文件扩展名采用语言环境的默认扩展名。 (4)数据文件都是文本文件，输入和输出文件的扩展名分别是.in 和.out。 5. 程序应从输入文件读取数据，并严格地按照规定的输出格式将结果输出到输出文件 。输入数据文件和输出数据文件都与程序在同一个目录 ，由于程序所在目录是 不确定的，因此不允许在文件名 含有盘符信息和任何形式的路径信息。 6. 选手在竞赛结束时应在指定分区的根目录下建立以参赛号命名的文件夹，并将所完 成各题的源程序文件放入到该文件夹 。测试以评测组编译的可执行文件为准，测 试系统使用标准的编译指令处理源文件，没有附加任何编译选项，请选手按照考试 机器上语言环境的默认配置编译调试自己的程序。由于测试的需要，Pascal 源程 序不得使用user math。 ．．．． 7. 小学组做前三题，第四题选做；中学组需做四题。 2015 年安庆市迎江 青少年信息学奥林匹克竞赛 第一题 数学黑洞 2014 年 10 月，省十三运在宜城开幕。本次运动会组织者计划从某学校挑选一批 服 者，小明想报名参加。他把这个想法告诉了数学老师。数学老师告诉小明，给你一 个正整数，你若能快速算出最少需要多少步找到数学的黑洞，你就可以参加。老师向小 明解释了数学黑洞问题：对于所有的数字不完全相同的n 位数 （不够 n 位数的前面补 零也算是n位数），我们用这个n位数的n 个数字可组成的最大数减去可组成的最小数， 则得到一个新的n 位数 （不够n 位数的前面补零当成是n 位数）；对新的n 位数还按照 上面的规则继续算下去，最后会发现，我们陷入一个死循环，或者说是跌入了一个数的 黑洞里。比如从三位数 123 开始，计算如下 321-123=198；981-189=792； 972-279=693；963-369=594；954-459=495,共 5 步掉入黑洞里。实际上，从其 他的任何三位数开始，最终也都会停止在 495，我们把 495 叫做三位数的黑洞。亲爱 的小朋友们，你也来和小明一起试试看吧。 输入格式 一行，含用空格隔开的两个整数n和m,分别表示位数和n位的正整数。 输出格式 一行，表示找到黑洞的最少步骤。 输入样例 1 3 123 输出样例 1 5 输入样例 2 4 123 输出样例 1 3 数据范围 2 n =4