2003年四川省选拔测试
时间：4小时
题目 文件 输入 输出 分值
括号的匹配 Match.exe Match.in Match.out 50
表达式的数值 fractionexe fraction.in Fraction.out 50
邮递员的安排 Post.exe Post.in Post.out 50
题一：括号的匹配
题意描述：
在算术表达式中，除了加、减、乘、除等运算外，往往还有括号。包括有大括号{}，中括号[]，小括号()，尖括号<>等。
对于每一对括号，必须先左边括号，然后右边括号；如果有多个括号，则每种类型的左括号和右括号的个数必须相等；对于多重括号的情形，按运算规则，从外到内的括号嵌套顺序为：大括号->中括号->小括号->尖括号。例如，{[()]}，{()}为一个合法的表达式，而([{}])，{([])},[{<>}]都是非法的。
输入：
文件的第一行为一个整数n（1≤n≤100），接下来有n行仅由上述四类括号组成的括号表达式。第i+1行表示第i个表达式。每个括号表达式的长度不超过255。
输出：
在输出文件中有N行，其中第I行对应第I个表达式的合法性，合法输出YES，非法输出NO。
示例：
match.in match.out
5
{[(<>)]}
[()]
<>()[]{}
[{}]
{()} YES
YES
YES
NO
YES
题二：分数的位置
题意描述：
将所有的分母小于N的真分数（分子小于分母，数值小于1）从大到小排列出来后，例如当N=4时，所有的真分数有1/4，1/3，1/2，2/3，3/4。其中第三个真分数为1/2，其分子为1，分母为2。编一个程序，对给定的N，求出第M个真分数的值。
输入：
输入文件中第一行有一个数N，第二行为一个数字M（N <105，M<109）。
输出：
输出文件中有两行，第一行为分子K1，第二行为分母K2。其中K1 和K2没有除1以外的公约数。
示例：
Fraction.in fraction.out
4
3 1
2
题三：邮递员的安排
题意描述：
由于邮局的效率低下，某小区的志愿人员计划建立一个社区内部的报纸分发系统。在试运行阶段，由于志愿人员人数不够，任务安排不合理，造成分发效率不高。因此你被要求写一个程序，以尽可能合理的安排任务。
小区的街道都是沿着南北、或者东西方向延伸的，并且每一段街道长度都相等（不妨设其长度为1）。从飞机上看下来，整个小区就象一个棋盘格，而订户们总是在某两条街道的交叉处设有他们的邮箱。碰巧我们的分发中心也设在一个
十字路口。为了方便描述，我们在街道的基础上建立一个迪卡尔坐标系：以分发中心为坐标原点， 南北向为第一坐标，东西向为第二坐标。如下图中某订户相对于分发中心的坐标为（2，1）。
北
西 东
南
○为分发中心，●为订户邮箱
任务的安排基本上取决于订户们相对于分发中心的方向，订户们将被尽可能平均的分配给邮递员。任务安排的规则有以下几条：
每个邮递员负责以分发中心为圆心的一个扇形区域内的所有用户，但分发过程中，邮递员可以走出他所负责的扇形。
任意两个邮递员负责的用户数之差不超过1。
每天早上，每个邮递员从分发中心出发，将报纸逐个送到所负责的用户，最后返回分发中心。
邮递员只能沿着街道行走。
要求使所有邮递员的总路线长度最短。
输入：
第1行为两个整数n和m。分别表示邮递员个数和用户数。1〈 n〈 m ≤100。m 整除 n不超过10，以下m行依次给出每个用户相对于分发中心的坐标位置：Xi ,Yi ，其中，-100 ≤ Xi ,Yi ≤100，任何两个用户不会在相同的位置，任何用户也不会和分发中心重叠。
输出：
所有邮递员的路线总长度。如果不能安排，则文件仅输出-1。
示例：
Post.in Post.out
2 4
1 0
0 1
-1 0
0 -1 8
