NOIP2010复赛模拟试题.doc

NOIP2010复赛模拟04
1、6174陷阱(trap.cpp)
【问题描述】
6174陷阱是众所周知的，下面我们来水一道吧。对于任意一个四位数n，当n的数字均不相同时，将它的数字重排后得到的最大的数减去重排得到的最小的数，重复若干个步骤后，一定会得到6174。给定n，求它几步后得到6174。
【输入格式】
第一行为正整数t(≤10000)，接下来t行，每行一个四位正整数n。
【输出格式】
对于每个数据，输出得到6174的步数，如果没有办法得到6174，输出-1。
【输入样例】
2
4521
6174
【输出样例】
2
0
2、整数链(chains.cpp)
【问题描述】
给一个正整数n，求一个整数序列Xi：X0,X1,…,Xm，使得X0=1,Xm=n，且Xi是Xi+1的因子。编程计算序列长度m的最大值，及能得到m长度的序列的种类数。
【输入格式】
第一行为正整数t(≤100)，接下来t行，每行一个正整数n(≤220)。
【输出格式】
对于每个数据，输出两个整数，分别表示m的最大值及种类数。
【输入样例】
3
2
4
100
【输出样例】
1 1
2 1
4 6
3．电路架设(pole.cpp)
【问题描述】
为了大开发，供电部门决定为开发区架设电线。架设这些电线要有N根电线杆。所有电线从供电站引出来，形成一条直线。完成这项任务后，供电部门才发现他们忽略了一个重要技术细节：即两个相邻的电线杆之间间隔要大于等于K米但又要小于等于P米。
所以他们决定重新调整电线杆，但是要知道调整1根电线杆首先要拔出，然后运输到目标地，然后将它竖立在目标地地上。因此它要很高代价。为此供电部门想尽可能少移动电线杆。
现在以供电站为坐标原点，每个电线杆对应一个正整数，这个数代表电线杆与供电站的距离。它们组成一个一维坐标系。
你的任务是给出电线杆所在的位置，求出按两个相邻的电线杆之间间隔要在大于等于K但又要小于等于P米的技术要求，最少移动多少根电线杆。
【输入格式】
第1行为三个正整数N,K,P，用空格隔开，N（1≤N≤2500）表示电线杆数，K（1≤K≤10），P（N≤P≤50）；第2行是N个正整数序列x1, x2, ... xn ，（0≤x1＜x2＜... ＜xn≤25000）。
【输出格式】
仅有一个正整数，为按两个相邻的电线杆之间间隔要在大于等于K但又要小于等于P米的技术要求，最少移动的电线杆数。
【输入样例1】
3 2 4
2 3 4
【输出样例1】
1
【输入样例2】
3 3 5
0 1 2
【输出样例2】
2
【输入样例3】
5 2 4
1 6 7 9 14
【输出样例3】
2