题一
“自身数字”问题
源文件：
self
输入文档：没有
输出：屏幕
50
分
问题描述
1949
年，印度数学家D.R.Kaprekar发现了一类被称作“自身数值”的数字：
对于任一个正整数n，定义函数d（n）为n加上它的各位数字的和。（d代表digitadition，是kaprekar造出来的术语）。
举例来说，d（75）=75+7+5=87。以任意一个正整数n为起点，可以构造一个无穷的递增的整数序列：n,d（n），d（d（n）），d（d（d（n））），……
例如：以33为起点，下一个数字是33+3+3=39，再下一个数字是39+3+9=51，再下一个数字是51+5+1=57，以此类推可以产生序列：
33
，39，51，57，69，84，96，111，114，120，123，129，141，……
n
被称作d（n）的“产生者”。
在上面的序列中，33是39的“产生者”，39是51的“产生者”，51是57的“产生者”，……。
有些数字会有不止一个“产生者”：举例来说，101有两个“产生者”，它们是91和100。
如果一个数字没有“产生者”，那么这个数字叫做“自身数字”。在小于100的数字中有13个“自身数字”：1，3，5，7，9，20，31，42，53，64，75，86，和97。
请写一个程序，按递增顺序输出所有大于0小于10000的所有的“自身数字”，每一行输出10个数字（最后一行可少于10个）。
示范输出
1 3 5 7 9 20 31 42 53 64
|
| <-- a lot more numbers
|
题二
寻找长方形
源文件
:rect.
输入文档
:rect.in
输出：屏幕
150
分
问题描述
观察图1a,2a,3a
中的圆点。图1b,2b和3b中画出了所有水平方向和垂直方向上均以所给出的圆点为顶点的长方形。图4中的点不能组成任何的长方形。
请写一个程序：对于给定的一组圆点，找出所有可能的长方形。下面将给出关于上面几个图的输入和输出的示例。
输入文档要包含1个以上的圆点集合，最后以0结尾表示输入文档结束。每一个圆点集合的第一行是正整数n，表示共有圆点的数目，其后的n行表示圆点的状态。每个圆点的表示格式是：先用一个大写字母来代表一个圆点，其后空格，然后是该圆点的横坐标，再空格，最后是该圆点的纵坐标。每一组圆点集合中，表示圆点的大写字母应按字母表的顺序使用。注意，因为每个点需要用一个大写字母表示，所以至多可以有26圆点。所有的坐标是小于50的非负整数。每组集合的各个圆点彼此是独立的。
每组圆点集合的输出要以“point set”作为开始，后面加上一个表示该组圆点编号的数字和一个冒号。如果不能组成长方形，则在冒号后面输出“no rectangles”。如果可以组成长方形，则另起一行，列出这些长方形。每个长方形前面先空一格。长方形以它顶点的字母来表示，从左上角开始，按顺时针顺序列出。即列出顶点的顺序是：左上角
à
右上角
à
右下角
à
左下角。每一行列出十个长方形，最后一行可以列出少于10个长方形。按字母表的顺序列出长方形。
示范输入
7
A 1 1
B 2 1
C 3 1
D 2 3
E 3 3
F 1 4
G 3 4
8
B 1 1
D 2 1
F 4 1
J 4 4
L 2 4
M 2 3
N 4 3
P 1 2
12
A 1 5
B 2 5
C 1 4
D 2 4
E 1 3
F 2 3
G 1 2
H 2 2
I 1 1
J 2 1
K 1 0
L 2 0
5
B 1 1
D 2 1
L 2 4
N 2 3
P 1 2
0
示范输出
Point
set 1:
DECB FGCA
Point
set 2:
LJFD LJNM MNFD
Point
set 3:
ABDC ABFE ABHG ABJI ABLK CDFE CDHG CDJI CDLK
EFHG
EFJI EFLK GHJI GHLK IJLK
Point
set 4: No rectangles
题三
交换比率问题
源文件
: exchange.
输入文档
: exchange.in
输出
:
屏幕
250
分
问题描述
用纸币来支付商品和服务的费用可以使生活方便，可是人们有时希望能够直接交换物品而不使用钱币来作媒介。为了确保一致的“价格”，商人们制订了一个关于商品的交换比率。我们用正整数m和n来表示商品A和B的交换比率，并说m个商品A等价于n个商品B。举例来说，2个火炉应该等价于3个冰箱(从数学的角度来说，1个火炉等价于1.5个冰箱,但是要拿出半个冰箱不是件容易的事,交换比率总是那些有实际意义的整数)。
请写一个程序,对于给出的交换比率表，计算出任意两件商品的交换比率。
输入文档中的第一行为一个整数，表示测试数据的组数。每组数据中均要包含至少一个命令，结尾用一个“$
”
号来表示输入文档的结束。每个命令独占一行，命令可以是一个断言或一个疑问。如果是断言，则以感叹号开头，并按如下格式： ! m itema = n itemb
itema
和itemb应是具体的商品名称，m和n都是不大于100的正整数。这个命令断言了m个itema等价于n个itemb。如果命令是一个疑问，则以问号开头，并按如下格式：
? itema = itemb
表示询问itema和itemb之间的交换比率，itema和itemb是在上文的断言中曾出现过的具体的商品名称（itema和itemb不一定要在同一断言中出现）。对于每个疑问，根据所有的有关的断言，输出itema和itemb之间的交换比率。交换比率必须是整数形式而且应该尽可能的小。如果不能找到相应的交换比率，用问号代替整数来表示。请严格按照下面例子输出。注意：
商品名字只能用不多于20个小写字母来表示。
商品的名字用单数表示（不要用复数形式）。
最多有60种不同的商品。
对于每一对不同的商品，最多只能有一个断言。
可能有永假的断言，举例来说, "2
pig = 1 cow", "2 cow = 1 horse", and "2 horse = 3 pig"
是永假，不成立。若在一组数据中发现有永假的断言，则不作任何处理，只需输出一个组号+“：”+“ERROR！”。 断言中的比率不一定要是最小的，但是输出的比率一定要是最小的形式。虽然断言中不能有大于100的数字，但疑问中可以出现比100大的数字。疑问的答案化成最小后输出。
示范输入
1
! 6 shirt = 15 sock
! 47 underwear = 9 pant
? sock = shirt
? shirt = pant
! 2 sock = 1 underwear
? pant = shirt
$
示范输出
5 sock = 2 shirt
? shirt = ? pant
45 pant = 188 shirt
题四
象棋中“车”的避开问题
源文件
:rook
输入文档
:rook.in
输出
:
屏幕
150
分
问题描述
在象棋中,
”
车
”
是一种能够在水平和垂直方向上移动任意空格数的棋子.在这个问题中,我们将讨论在设有阻止
”
车
”
前进的
”
墙
”
的小棋盘上放置
”
车
”
的问题:在任意两个
”
车
”
不能捉到对方的前提下,向棋盘上放入尽量多的
”
车
”
.
按照要求可知,如果任意两个
”
车
”
都不在同一横行或同一竖行,或者至少有一面
”
墙
”
将它们隔开,则棋盘上
”
车
”
的摆置是合法的.
下面的图反映了同一棋盘上放置
”
车
”
的5种情况.
第一幅图是一个空的棋盘；
第二和第三幅图是合法的放置
”
车
”
的情况；
第四和第五幅图是不合法的放置
”
车
”
的情况。
对于这个棋盘来说,合法地放置
”
车
”
的最大数量是5;
有多种不同的方法来放置最多的
”
车
”
,
第二幅图的方法是其中的一种.
请写一个程序:对于给定的一个棋盘,计算出能够在棋盘上合法地放置
”
车
”
的最大数.
输入文档要包含一个以上的棋盘的描述,最后一行以0来表示输入文档的结束。
.
每个棋盘的描述的第一行是一个正整数n,表示棋盘的大小;n不超过10；
接下来的n行,每一行描述棋盘上的一行,用
”
.
”
来表示一个空格,用大写字母
”
X
”
来表示一面
”
墙
”
.
输入文档中不出现空格.
对于每个测试案例,输出能够在棋盘上合法地放置
”
车
”
的最大数,同时输出最小能控制棋盘上“车”的数量，这两个数字独自占一行.
示范输入
4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0
示范输出
:
5 3
1 1
5 5
2 1
4 4
posted on 2009-03-12 22:39
250 阅读(320)
评论(0) 编辑 收藏 引用