山东信息奥赛培训(7.17).doc

NOIP模拟试题

题目名称
城市街区
因子的排列
序列排序
可执行文件名
city
factors
sort
输入文件
city.in
factors.in
sort.in
输出文件
city.out
factors.out
sort.out
每个测试点时限
1s
1s
1s
内存限制
128M
128M
128M
测试点数目
10
10
10
每个测试点分值
10
10
10
结果比较方式
忽略多余的空格和文件尾的空行
题目类型
传统
传统
传统

注意：最终测试时，所有编译命令均不打开任何优化开关。
一、城市街区
(city.pas/c/cpp)

问题描述：
小A有一个游戏，这个游戏中的某个城市的地图是一个大型方格网，左下角为(-109,-109)，右上角为(109,109)。在方格网内部（包括边界）每个整点都是一个路口，每条直线x=x0或y=y0（x0, y0为整数）在方格网内部（包括边界）的部分都是该城市的一条街道。此外，该城市还存在一条斜向的街道，其直线方程为Ax+By+C=0（A, B均不等于0），这条斜向的街道与方格网的交叉点也是路口。现在有N个人，所有人都只能沿着城市的街道行走，其中第i个人要从该城市的路口(ai,bi)走到路口(ci,di)。小A希望计算每个人需要走的最短路径的长度。由于N太大了，小A不想自己算，因此他向你求助。

输入：
第一行，四个整数N, A, B, C。
接下来的N行，每行四个整数ai, bi, ci, di。

输出：
N行，每行一个实数（保留3位小数），其中第i行的整数表示第i个人需要走的最短路径的长度。

输入输出样例：
city.in
city.out
3 2 2 -1
-6 2 2 4
-6 2 -3 -2
-6 2 -8 10

10.000
7.000
8.828

数据范围：
对于30%的数据，|A|, |B|, |C|, |ai|, |bi|, |ci|, |di|<=10；
对于全部的数据，|A|, |B|, |C|, |ai|, |bi|, |ci|, |di|<=109，1<=N<=2000。
二、因子的排列
(factors.pas/c/cpp)

问题描述：
一天，小B学习了分解质因数的相关内容。他发现，一个数的质因子可以有许多不同的排列方式，例如20=2*2*5=2*5*2=5*2*2，那么小B认为20的质因子有3种不同的排列方式。小B的同学现在有一个问题：如果一个整数的质因子的不同的排列方式的种类数为k，那么这个整数n（n>1）最小是多少？小B的同学一共有T个不同的k值，希望小B帮助这个同学解决问题。但是小B发现T太大了，并且给出的k值也相当大，因此小B向你求助。

输入：
第一行，一个整数T。
接下来的T行，每行一个整数k。

输出：
T行，每行一个整数，其中第i行的整数表示第i个k值对应的n的值。

输入输出样例：
factors.in
factors.out
4
1
2
3
105

2
6
12
720

数据范围：
对于30%的数据，1<n<=100000；
对于全部的数据，1<n<263，1<k<263，1<=T<=1000。
三、序列排序
(sort.pas/c/cpp)

问题描述：
小C有一个N个数的整数序列，这个序列的中的数两两不同。小C每次可以交换序列中的任意两个数，代价为这两个数之和。小C希望将整个序列升序排序，问小C需要的最小代价是多少？

输入：
第一行，一个整数N。
第二行，N个整数，表示小C的序列。

输出：
一行，一个整数，表示小C需要的最小代价。

输入输出样例：
sort.in
sort.out
6
8 4 5 3 2 7

34

数据范围：
对于30%的数据，1<=N<=10；
对于全部的数据，1<=N<=100000，输入数据中的其他整数均为正整数且不超过109。