USACO原题

USACO Training

The USA Computing Olympiad (USACO) is the premier pre-college computing organization in the USA.

Chapter1

Section 1.1

Your Ride Is Here你的飞碟在这儿！ 问题描述

科学家们在研究彗星后惊讶地发现，在每一个彗星后面都有一个不明飞行物UFO。 这些不明飞行物时常来带走来自地球上的一些支持者。不幸地，他们的空间在每次旅行只能带上一群支持者。 他们要做的是用一种聪明的方案让某个支持彗星UFO的团体都被彗星带走。他们为每个彗星起了一个名字，通过这些名字来决定一个团体是不是特定的彗星带走。 那个相配方案的细节是这样的:

所有团体的名字和彗星的名字都以下列各项方式转换成一个数字: 这个最后的数字代表名字中所有字母的信息，\是 1 和 \是 26。

举例来说，团体 \会是 21*19*1*3*15=17955 。 如果团体的数字 mod 47 等于慧星的数字 mod 47,那么你要告诉这个团体：准备好行李，走吧 ! 现在，你要写一个程序来通过团体的名字和彗星的名字来决定一个组是否应该与在那一颗彗星后面的不明飞行物搭配。

写一个程序读入彗星的名字和团体的名字，如果搭配打印\否者打印\ 团体的名字和彗星的名字将会是没有空格或标点的一串大写字母（不超过6个字母）。 样例 样例1: 输入:

COMETQ HVNGAT 输出: GO 样例2: 输入:

ABSTAR USACO 输出: STAY 格式

文件名： ride(.pas/.c/.cpp)

输入格式： (输入文件名 ride.in） 第 1 行:

彗星的名字（一个长度为1到6的字符串）

第 1 页 共 53 页

第 2 行:

团体的名字（一个长度为1到6的字符串） 输出格式: (输出文件名 ride.out) 只有一行----\或\

Greedy Gift Givers贪婪的送礼者 描述

对于一群要互送礼物的朋友，你要确定每个人收到的礼物比送出的多多少,反之亦然对于那些用贪婪的眼光来看礼物的人(by John)。 在这一个问题中，每个人都准备了一些钱来送礼物，而这些钱将会被平均分给那些将收到他的礼物的人。 然而，在任何一群朋友中，有些人将送出较多的礼物(可能是因为有较多的朋友)，有些人有准备了较多的钱。

给出一群朋友， 没有人的名字会长于 14 字符，给出每个人将花在送礼上的钱，和将收到他的礼物的人的列表，请确定每个人收到的比送出的钱多的数目。 格式

PROGRAM NAME: gift1 INPUT FORMAT: (file gift1.in)

第 1 行: 人数NP,2<= NP<=10

第 2到 NP+1 行:这NP个在组里人的名字 一个名字一行 第NP＋2到最后：

这里的NP段内容是这样组织的： 第一行是将会送出礼物人的名字。

第二行包含二个数字: 第一个是原有的钱的数目（在0到2000的范围里），第二个 NGi 是将收到这个送礼者礼物的人的个数 如果 NGi 是非零的, 在下面 NGi 行列出礼物的接受者的名字，一个名字一行。 OUTPUT FORMAT: (file gift1.out) 输出 NP 行

每行是一个的名字加上空格再加上收到的比送出的钱多的数目。

对于每一个人，他名字的打印顺序应和他在输入的2到NP＋1行中输入的顺序相同。所有的送礼的钱都是整数。

每个人把相同数目的钱给每位要送礼的朋友，而且尽可能多给，不能给出的钱被送礼者自己保留。

IMPORTANT NOTE:

测试系统是 Linux 符合标准的 Unix 的协定。 用'\\n'作为行的结束。 这和 Windows 系统用'\\n' 和 '\\r'作为行的结束是不同的。 你的程序可不要被这困住了! SAMPLE INPUT 5 dave laura owen vick amr

第 2 页 共 53 页

dave 200 3 laura owen vick owen 500 1 dave amr 150 2 vick owen laura 0 2 amr vick vick 0 0

SAMPLE OUTPUT dave 302 laura 66 owen -359 vick 141 amr -150

Friday the Thirteenth 黑色星期五 描述

13号又是星期五是一个不寻常的日子吗?13号在星期五比在其他日少吗?为了回答这个问题,写一个程序来计算在n年里13日落在星期一,星期二......星期日的次数.这个测试从1900年1月1日到1900+n-1年12月31日.n是一个非负数且不大于400. 这里有一些你要知道的:

1900年1月1日是星期一.4,6,11和9月有30天.其他月份除了2月都有31天.闰年2月有29天,平年2月有28天.年份可以被 4整除的为闰年(1992=4*498 所以 1992年是闰年,但是1990年不是闰年)以上规则不适合于世纪年.可以被400整除的世纪年为闰年,否则为平年.所以,1700,1800,1900 和2100年是平年,而2000年是闰年.请不要预先算好数据! 格式

PROGRAM NAME: friday INPUT FORMAT: (file friday.in) 一个整数n.

OUTPUT FORMAT: (file friday.out)

七个在一行且相分开的整数,它们代表13日是星期六,星期日,星期一...星期五的次数. SAMPLE INPUT

第 3 页 共 53 页

20

SAMPLE OUTPUT 36 33 34 33 35 35 34

Broken Necklace破碎的项链 描述

你有一条由N个红色的，白色的，或蓝色的珠子组成的项链(3<=N<=350)，珠子是随意安排的。 这里是 n=29 的二个例子:

1 2 1 2 r b b r b r r b

r b b b r r b r r r w r b r w w b b r r b b b b b b r b r r b r b r r r b r r r r r r b r b r r r w

图片 A 图片 B

r 代表 红色的珠子 b 代表 蓝色的珠子 w 代表 白色的珠子

第一和第二个珠子在图片中已经被作记号。 图片 A 中的项链可以用下面的字符串表示： brbrrrbbbrrrrrbrrbbrbbbbrrrrb .

假如你要在某点打破项链,展开成一条直线，然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事。(颜色可能与在这之前收集的不同) 确定应该在哪里打破项链来收集到最大数目的珠子。 Example 举例来说，在图片 A 中的项链，若在珠子 9 和珠子 10 或珠子 24 和珠子 25 之间打断项链，则可以收集到8个珠子。 在一些项链中，包括白色的珠子如图片 B 所示。 当收集珠子的时候，一个被遇到的白色珠子可以被当做红色也可以被当做蓝色。 表现项链的字符串将会包括三符号 r ， b 和 w 。 写一个程序来确定从一条被供应的项链最大可以被收集珠子数目。 格式

PROGRAM NAME: beads INPUT FORMAT: (file beads.in)

第 4 页 共 53 页

第 1 行: N, 珠子的数目

第 2 行: 一串度为N的字符串, 每个字符是 r ， b 或 w。 OUTPUT FORMAT: (file beads.out)

单独的一行包含从被供应的项链可以被收集的珠子数目的最大值。 SAMPLE INPUT 29

wwwbbrwrbrbrrbrbrwrwwrbwrwrrb SAMPLE OUTPUT 11

输出解释

考虑两段项链（能组成一圈的）。11个珠子已经标注了。

wwwbbrwrbrbrrbrbrwrwwrbwrwrr bwwwbbrwrbrbrrbrbrwrwwrbwrwrrb ***** ******

Section 1.2

Milking Cows 挤牛奶 描述

三个农民每天清晨5点起床，然后去牛棚给3头牛挤奶。第一个农民在300时刻(从5点开始计时，秒为单位)给他的牛挤奶，一直到1000时刻。第二 个农民在700时刻开始，在 1200时刻结束。第三个农民在1500时刻开始2100时刻结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300时刻到1200时 刻)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300时刻(从1200时刻到1500时刻)。

你的任务是编一个程序，读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表，计算以下两点(均以秒为单位):

? 最长至少有一人在挤奶的时间段。 ? 最长的无人挤奶的时间段。 格式

PROGRAM NAME: milk2 INPUT FORMAT: (file milk2.in)

第一行:一个整数N。 第二行: 2..N+1:

每行两个小于1000000的非负整数，表示一个农民的开始时刻与结束时刻。 OUTPUT FORMAT: (file milk2.out)

仅一行，两个整数，用空格分开，即题目所要求的两个答案。 SAMPLE INPUT 3

300 1000 700 1200 1500 2100

第 5 页 共 53 页

SAMPLE OUTPUT 900 300

Transformations 方块转换 描述

一块N x N（1<=N<=10）正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式：

? 1：转90度：图案按顺时针转90度。 ? 2：转180度：图案按顺时针转180度。 ? 3：转270度：图案按顺时针转270度。

? 4：反射：图案在水平方向翻转（以中央铅垂线为中心形成原图案的镜像）。 ? 5：组合：图案在水平方向翻转，然后再按照1到3之间的一种再次转换。 ? 6：不改变：原图案不改变。

? 7：无效转换：无法用以上方法得到新图案。

? 如果有多种可用的转换方法，请选择序号最小的那个。 格式

PROGRAM NAME: transform INPUT FORMAT: (file transform.in)

第一行： 单独的一个整数N。

第二行到第N+1行： N行每行N个字符（不是“@”就是“-”）；这是转换前的正方形。 第N+2行到第2*N+1行： N行每行N个字符（不是“@”就是“-”）；这是转换后的正方形。 OUTPUT FORMAT: (file transform.out)

单独的一行包括1到7之间的一个数字（在上文已描述）表明需要将转换前的正方形变为转换后的正方形的转换方法。

SAMPLE INPUT 3 @-@ --- @@- @-@ @-- --@

SAMPLE OUTPUT 1

Name That Number 命名那个数字 描述

在威斯康辛州牛大农场经营者之中，都习惯于请会计部门用连续数字给母牛打上烙印。 但是,母牛用手机时并没感到这个系统的便利,它们更喜欢用它们喜欢的名字来呼叫它们的同伴，而不是用像这个的语句\。 请写一个程序来帮助可怜的牧牛工将一只母牛的烙印编号翻译成一个可能的名字。 因为母牛们现在都有手机了，使用那标准

第 6 页 共 53 页

的按键的排布来把收到从数目翻译到文字:( 除了 \和 \ 2: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9: W,X,Y 4: G,H,I 7: P,R,S

可接受的名字都被放在这样一个叫作\dict.txt\的文件中，它包含一连串的少于 5,000个可被接受的牛的名字。 (所有的名字都是大写的) 请读入母牛的编号并返回那些能从编号翻译出来并且在字典中的名字。 举例来说,编号 4734 能产生的下列各项名字: GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI

碰巧，81个中只有一个\是有效的(在字典中)。

写一个程序来对给出的编号打印出所有的有效名字，如果没有则输出NONE。编号可能有12位数字。 格式

PROGRAM NAME: namenum INPUT FORMAT: (file namenum.in)

单独的一行包含一个编号(长度可能从1到12)。 OUTPUT FORMAT: (file namenum.out)

以字典顺序输出一个有效名字的不负列表，一行一个名字。 SAMPLE INPUT 4734

SAMPLE OUTPUT GREG

Palindromic Squares 回文平方数 描述

回文数是指从左向右念和从右向左念都一样的数。如12321就是一个典型的回文数。 给定一个进制B(2<=B<=20,由十进制表示)，输出所有的大于等于1小于等于300（十进制下）且它的平方用B进制表示时是回文数的数。用?A?,?B?……表示10，11等等。 格式

PROGRAM NAME: palsquare INPUT FORMAT: (file palsquare.in)

共一行，一个单独的整数B(B用十进制表示)。 OUTPUT FORMAT: (file palsquare.out)

每行两个数字，第二个数是第一个数的平方，且第二个数是回文数。(注意:这两个数都应该在B进制下)

第 7 页 共 53 页

SAMPLE INPUT 10

SAMPLE OUTPUT 1 1 2 4 3 9 11 121 22 484 26 676 101 10201 111 12321 121 14641 202 40804 212 44944 264 69696

Dual Palindromes 双重回文数 描述

如果一个数从左往右读和从右往左读都是一样，那么这个数就叫做“回文数”。例如，12321就是一个回文数，而77778就不是。当然，回文数的首和尾都应是非零的，因此0220就不是回文数。

事实上，有一些数（如21），在十进制时不是回文数，但在其它进制（如二进制时为10101）时就是回文数。

编一个程序，从文件读入两个十进制数N (1 <= N <= 15)S (0 < S < maxlongint)然后找出前N个满足大于S且在两种或两种以上进制（二进制至十进制）上是回文数的十进制数，输出到文件上。

本问题的解决方案不需要使用大于32位的整型变量。 格式

PROGRAM NAME: dualpal INPUT FORMAT: (file dualpal.in)

只有一行，用空格隔开的两个数N和S。 OUTPUT FORMAT: (file dualpal.out)

N行, 每行一个满足上述要求的数，并按从小到大的顺序输出。 SAMPLE INPUT 3 25

SAMPLE OUTPUT 26 27 28

Section 1.3

第 8 页 共 53 页

Mixing Milk 混合牛奶 描述

牛奶包装是一个如此低利润的生意,以至于尽可能低地控制初级产品(牛奶)的价格变得十分重要。请帮助Merry的牛奶制造公司(Merry Milk Makers')以尽可能最廉价的方式取得他们所需的牛奶。Merry的牛奶制造公司从一些农民那购买牛奶，每个农民卖给牛奶制造公司的价格不一定相同。 而且,如一只母牛一天只能生产一定量的牛奶,农民每一天只有一定量的牛奶可以卖。每天,Merry的牛奶制造公司从每个农民那购买一定量的牛奶,少于或等 于农民所能提供的最大值。给出Merry牛奶制造公司的每日的牛奶需求,连同每个农民的可提供的牛奶量和每加仑的价格,请计算Merry的牛奶制造公司所 要付出钱的最小值。 注意:每天农民生产的牛奶的总数对Merry的牛奶制造公司来说是足够的。 格式

PROGRAM NAME: milk INPUT FORMAT: (file milk.in)

第 1 行:二个整数, N 和 M。

第一个数值,N,(0<= N<=2,000,000)是Marry的牛奶制造公司的一天需要牛奶的数量。 第二个数值,M,(0<= M<=5,000)是提供牛奶的农民个数。 第 2 到 M+1 行:每行二个整数,Pi 和 Ai。 Pi(0<= Pi<=1,000) 是农民 i 的牛奶的价格。

Ai(0 <= Ai <= 2,000,000)是农民 i 一天能卖给Marry的牛奶制造公司的牛奶数量。 OUTPUT FORMAT: (file milk.out)

单独的一行包含单独的一个整数，表示Marry的牛奶制造公司拿到所需的牛奶所要的最小费用

SAMPLE INPUT 100 5 5 20 9 40 3 10 8 80 6 30

SAMPLE OUTPUT 630

Barn Repair 修理牛棚 描述

在一个月黑风高,下着暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚没有住满。 剩下的牛一个紧挨着另一个被排成一行来过夜。 有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,农民约翰必须尽快在牛棚之前竖立起新的木板。 他的新木材供应商将会供应他任何他想要的长度,但是供应商只能提供有限数目的木板。 农民约翰想将他购买的木板总长度减到最少。

给出:可能买到的木板最大的数目M(1<= M<=50);牛棚的总数S(1<= S<=200); 牛棚里牛的总数C(1 <= C <=S);和牛所在的牛棚的编号stall_number(1 <= stall_number <= S),计算拦住所有有牛的牛棚所需木板的最小总长度。 输出所需木板的最小总长度作为答案。

第 9 页 共 53 页

格式

PROGRAM NAME: barn1 INPUT FORMAT: (file barn1.in)

第 1 行: M ， S 和 C(用空格分开)

第 2 到 C+1行: 每行包含一个整数，表示牛所占的牛棚的编号。 OUTPUT FORMAT: (file barn1.out)

单独的一行包含一个整数表示所需木板的最小总长度。

SAMPLE INPUT 4 50 18 3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43

SAMPLE OUTPUT 25

[ 一种最优的安排是用板拦住牛棚3-8,14-21,25-31,40-43.]

Calf Flac 描述

据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出世上最棒的回文。你的工作就是去寻找这些牛制造的奇观(最棒的回文)。 在寻找回文时不用理睬那些标点符号、空格(但应该保留下来以便做为答案输出),只用考虑字母'A'-'Z'和'a'-'z'。要你寻找的最长的回文的文章是一个不超过20,000个字符的字符串。 我们将保证最长的回文不会超过2,000个字符(在除去标点符号、空格之前)。 题目名称：calfflac 输入格式

输入文件不会超过20,000字符。这个文件可能一行或多行，但是每行都不超过80个字符(不

第 10 页 共 53 页

包括最后的换行符)。 样例输入(file calfflac.in)

Confucius say:Madam,I'm Adam. 输出格式

输出的第一行应该包括找到的最长的回文的长度。

下一行或几行应该包括这个回文的原文（没有除去标点符号、空格），把这个回文输出到一行或多行（如果回文中包括换行符）。

如果有多个回文长度都等于最大值，输出最前面出现的那一个。 样例输出(file calfflac.out） 11

Madam,I'm Adam

Prime Cryptarithm 牛式 描述

下面是一个乘法竖式，如果用我们给定的那n个数字来取代*，可以使式子成立的话，我们就叫这个式子牛式。 * * * x * * ------- * * * * * * ------- * * * *

数字只能取代*，当然第一位不能为0。

注意一下在美国的学校中教的“部分乘积”，第一部分乘积是第二个数的个位和第一个数的积，第二部分乘积是第二个数的十位和第一个数的乘积. 写一个程序找出所有的牛式。 格式

PROGRAM NAME: crypt1 INPUT FORMAT: (file crypt1.in)

Line 1:数字的个数n。

Line 2:N个用空格分开的数字（每个数字都∈{1,2,3,4,5,6,7,8,9}）。 OUTPUT FORMAT: (file crypt1.out)

共一行，一个数字。表示牛式的总数。 下面是样例的那个牛式。 2 2 2 x 2 2 ------ 4 4 4 4 4 4 --------- 4 8 8 4

第 11 页 共 53 页

SAMPLE INPUT 5

2 3 4 6 8

SAMPLE OUTPUT 1

Section 1.4

Packing Rectangles 铺放矩形块 (IOI 95) 描述

给定4个矩形块，找出一个最小的封闭矩形将这4个矩形块放入，但不得相互重叠。所谓最小矩形指该矩形面积最小。

图1 所有4个矩形块的边都与封闭矩形的边相平行，图1示出了铺放4个矩形块的6种方案。这6种方案只是可能的基本铺放方案。因为其它方案能由基本方案通过旋转和镜像反射得到。 可能存在满足条件且有着同样面积的各种不同的封闭矩形，你应该输出所有这些封闭矩形的边长。 格式

PROGRAM NAME: packrec INPUT FORMAT: (file packrec.in) 共有4行。每一行用两个正整数来表示一个给定的矩形块的两个边长。矩形块的每条边的边长范围最小是1，最大是50。 OUTPUT FORMAT: (file packrec.out)

总行数为解的总数加1。第一行是一个整数，代表封闭矩形的最小面积（子任务A）。接下来的每一行都表示一个解，由数P和数Q来表示，并且P≤Q（子任务B）。这些行必须根据P的大小按升序排列，P小的行在前，大的在后。且所有行都应是不同的。 SAMPLE INPUT 1 2 2 3 3 4 4 5

SAMPLE OUTPUT 40 4 10 5 8

第 12 页 共 53 页

The Clocks 时钟 (IOI'94 - Day 2) 描述

考虑将如此安排在一个 3 x3 行列中的九个时钟:

|-------| |-------| |-------| | | | | | | | |---O | |---O | | O | | | | | | | |-------| |-------| |-------| A B C

|-------| |-------| |-------| | | | | | | | O | | O | | O | | | | | | | | | | |-------| |-------| |-------| D E F

|-------| |-------| |-------| | | | | | | | O | | O---| | O | | | | | | | | | |-------| |-------| |-------| G H I

目标要找一个最小的移动顺序次将所有的指针指向12点。下面原表格列出了9种不同的旋转指针的方法，每一种方法都叫一次移动。选择1到9号移动方法，将会使在表格中对应的时钟的指针顺时针旋转90度。 移动方法 受影响的时钟 1 ABDE 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI

Example

9 9 12 9 12 12 9 12 12 12 12 12 12 12 12 6 6 6 5 -> 9 9 9 8-> 9 9 9 4 -> 12 9 9 9-> 12 12 12 6 3 6 6 6 6 9 9 9 12 9 9 12 12 12

[但这可能不是正确的方法，请看下面] 格式

PROGRAM NAME: clocks INPUT FORMAT: (file clocks.in)

第1-3行: 三个空格分开的数字，每个数字表示一个时钟的初始时间，3,6,9,12。数字的含意和上面第一个例子一样。 OUTPUT FORMAT: (file clocks.out)

单独的一行包括一个用空格分开的将所有指针指向12:00的最短移动顺序的列表。

如果有多种方案，输出那种使其连接起来数字最小的方案。(举例来说5 2 4 6 < 9 3 1 1)。 SAMPLE INPUT 9 9 12 6 6 6 6 3 6

第 13 页 共 53 页

SAMPLE OUTPUT 4 5 8 9

Arithmetic Progressions 等差数列 描述

一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...)的数列。 在这个问题中a是一个非负的整数，b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p^2＋q^2的数的集合)S中长度为n的等差数列。 格式

TIME LIMIT: 5 秒

PROGRAM NAME: ariprog INPUT FORMAT: (file ariprog.in)

第一行: N(3<= N<=25),要找的等差数列的长度。

第二行: M(1<= M<=250),搜索双平方数的上界0 <= p,q <= M。 OUTPUT FORMAT: (file ariprog.out)

如果没有找到数列,输出`NONE'。

如果找到了，输出一行或多行, 每行由二个整数组成:a,b。 这些行应该先按b排序再按a排序。

所求的等差数列将不会多于10,000个。 SAMPLE INPUT 5 7

SAMPLE OUTPUT 1 4 37 4 2 8 29 8 1 12 5 12 13 12 17 12 5 20 2 24

Mother's Milk 母亲的牛奶 描述

农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数， 最初，A和B桶都是空的，而C桶是装满牛奶的。有时，农民把牛奶从一个桶倒到 另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约， 牛奶不会有丢失。 写一个程序去帮助农民找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。 格式

第 14 页 共 53 页

PROGRAM NAME: milk3 INPUT FORMAT: (file milk3.in)

单独的一行包括三个整数A,B和C。 OUTPUT FORMAT: (file milk3.out)

只有一行，升序地列出当A桶是空的时候，C桶牛奶所剩量的所有可能性。 SAMPLE INPUT 1 8 9 10

SAMPLE OUTPUT 1 1 2 8 9 10

SAMPLE INPUT 2 2 5 10

SAMPLE OUTPUT 2 5 6 7 8 9 10

Section 1.5

Number Triangles 数字三角形 描述

观察下面的数字三角形。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大和:30 格式

PROGRAM NAME: numtri INPUT FORMAT: (file numtri.in)

第一个行包含 R(1<= R<=1000) ,表示行的数目。 后面每行为这个数字金字塔特定行包含的整数。 所有的被供应的整数是非负的且不大于100。 OUTPUT FORMAT: (file numtri.out)

单独的一行,包含那个可能得到的最大的和。 SAMPLE INPUT 5 7 3 8 8 1 0

第 15 页 共 53 页

2 7 4 4 4 5 2 6 5

SAMPLE OUTPUT 30

Prime Palindromes 回文质数 描述

因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 是回文质数。

写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数; 格式

PROGRAM NAME: pprime INPUT FORMAT: (file pprime.in)

第 1 行: 二个整数 a 和 b . OUTPUT FORMAT: (file pprime.out)

输出一个回文质数的列表，一行一个。 SAMPLE INPUT 5 500

SAMPLE OUTPUT 5 7 11 101 131 151 181 191 313 353 373 383

HINTS(use them carefully!)

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数（素数）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。 (产生长度为5的回文数：）

for (d1 = 1; d1 <= 9; d1+=2) { （只有奇数，偶数必非质数）

for (d2 = 0; d2 <= 9; d2++) {

第 16 页 共 53 页

for (d3 = 0; d3 <= 9; d3++) {

palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;

判断回文... } } }

Superprime Rib 特殊的质数肋骨 描述

农民约翰的母牛总是产生最好的肋骨。 你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。 农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说: 7 3 3 1 全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。 7331 被叫做长度 4 的特殊质数。 写一个程序对给定的肋骨的数目 N (1<=N<=8),求出所有的特殊质数。 数字1不被看作一个质数。 格式

PROGRAM NAME: sprime INPUT FORMAT: (file sprime.in)

单独的一行包含N。 OUTPUT FORMAT: (file sprime.out)

按顺序输出长度为 N 的特殊质数,每行一个。 SAMPLE INPUT 4

SAMPLE OUTPUT 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939

第 17 页 共 53 页

7193 7331 7333 7393

Checker Challenge 跳棋的挑战 描述

检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。 列号

1 2 3 4 5 6 ------------------------- 1 | | O | | | | | ------------------------- 2 | | | | O | | | ------------------------- 3 | | | | | | O | ------------------------- 4 | O | | | | | | ------------------------- 5 | | | O | | | | ------------------------- 6 | | | | | O | | -------------------------

上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6 列号 2 4 6 1 3 5

这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。

特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式），这是作弊。如果你坚持作弊，那么你登陆USACO Training的帐号将被无警告删除 格式

TIME LIMIT: 1s

PROGRAM NAME: checker INPUT FORMAT: (checker.in)

一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。 OUTPUT FORMAT: (checker.out)

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

SAMPLE INPUT

第 18 页 共 53 页

6

SAMPLE OUTPUT 2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4 Hint1

使用递归：

function placequeen(column) { # place columns 0..max-1 if (column == max) { deal with answer; return; } for (row = 0; row < max; row++) { if (canplacequeen (row)) { mark queen placed at column,row; placequeen(column+1); un-mark queen placed at column,row; } } } Hint2

尽量减少频繁搜索的次数。通常最好的方法是以空间换时间。当检测某个皇后能否放在某一行时，存一个数组表示是否有皇后已经被放在那儿： function placequeen(column) { # place columns 0..max-1 if (column == max) { deal with answer; return; } for (row = 0; row < max; row++) {

if (rowok[row] && canplacequeen(row,column)) { rowok[row] = 1; mark queen placed at column,row; placequeen(column+1); un-mark queen placed at column,row; rowok[row] = 0; } } } Hint3

使用“让一切绝对化（absolutely everything）” (在搜索中)您能避免程序中频繁的重复。不仅要记录下合法的皇后所在的那一行，还要标记所在的两条对角线(也就是象?/?和?\\?的两条）使用大小为 2*max - 1的布尔数组来判断其他皇后所在的对角线是否合法。 Hint4

对称： 您能否通过利用旋转、对称来削减一半或3/4的枚举量 ？ [提示：能] Hint5

还是超时吗？如果你已经编好各个模块并且有检查对角线的子程序或者还有别的，把它们的代码移动到主过程中，子程序的……调用常令人出乎意料（The subroutine call overhead is nontrivial. ） Hint6

第 19 页 共 53 页

多数成功的Java题解用位运算存储“用过的行（列、对角线）”。

Chapter2

Section 2.1

The Castle城堡 描述

我们憨厚的USACO主人公农夫约翰(Farmer John)以无法想象的运气,在他生日那天收到了一份特别的礼物：一张“幸运爱尔兰”（一种彩票）。结果这张彩票让他获得了这次比赛唯一的奖品——坐落于 爱尔兰郊外的一座梦幻般的城堡！(RP...详情可以参见RP导论....)

喜欢吹嘘的农夫约翰立刻回到有着吹嘘传统的威斯康辛老家开始吹嘘了, 农夫约翰想要告诉他的奶牛们关于他城堡的一切。他需要做一些吹嘘前的准备工作：比如说知道城堡有多少个房间，每个房间有多大。另外，农夫约翰想要把一面单 独的墙（指两个单位间的墙）拆掉以形成一个更大的房间。 你的工作就是帮农夫约翰做以上的准备，算出房间数与房间的大小。

城堡的平面图被划分成M*N（M是宽度）个正方形的单位，一个这样的单位可以有0到4面墙环绕。城堡周围一定有外墙环绕以遮风挡雨。（就是说平面图的四周一定是墙。）

请仔细研究下面这个有注解的城堡平面图：

1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | # # # # # #---#####---#####---#####---# 3 # | | # # # # # #---#########---#####---#---# 4 # -># | | | | # # #############################

# =墙壁 -,| = 没有墙壁

-> =指向一面墙，这面墙推掉的话我们就有一间最大的新房间 友情提示，这个城堡的平面图是7×4个单位的。一个“房间”指的是平面图中一个连通的“正方形单位”的集合。比如说这个样例就有5个房间。（大小分别为9、7、3、1、8个单位（排名不分先后））

移去箭头所指的那面墙，可以使2个房间合为一个新房间，且比移去其他墙所形成的房间都大。（原文为：Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall. ） 城堡保证至少有2个房间，而且一定有一面墙可以被移走。 格式

PROGRAM NAME: castle

INPUT FORMAT: 城堡的平面图用一个由数字组成的矩阵表示，一个数字表示一个单位，矩阵有N行M列。输入与样例的图一致。

每一个单位的数字告诉我们这个单位的东西南北是否有墙存在。每个数字是由以下四个整数

第 20 页 共 53 页

的某个或某几个或一个都没有加起来的。 1: 在西面有墙 2: 在北面有墙 4: 在东面有墙 8: 在南面有墙

城堡内部的墙会被规定两次。比如说（1，1）南面的墙，亦会被标记为（2，1）北面的墙。 (file castle.in)

第 1 行: 二个被空格分开的整数: M 和 N（N,M<=50） 第 2 到 N+1 行: M x N 个整数,每行M个。 OUTPUT FORMAT: (file castle.out)

输出包含如下4行:

第 1 行: 城堡的房间数目。 第 2 行: 最大的房间的大小

第 3 行: 移除一面墙能得到的最大的房间的大小 第 4 行: 移除哪面墙可以得到面积最大的新房间。

选择最佳的墙来推倒。有多解时选（重心）最靠西的（仍然有多解时选这些里面（重心）最靠南的）。 用该墙的南邻单位的北墙或西邻单位的东墙来表示这面墙，方法是输出邻近单位的行数、列数和墙的方位（\（北）或者\（东））。 SAMPLE INPUT 7 4

11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13 SAMPLE OUTPUT 5 9 16 4 1 E

Ordered Fractions顺序的分数 描述

输入一个自然数N,对于一个最简分数a/b（分子和分母互质的分数）,满足1<=b<=N,0<=a/b<=1,请找出所有满足条件的分数。

这有一个例子，当N=5时，所有解为： 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

给定一个自然数N，1<=n<=160，请编程按分数值递增的顺序输出所有解。 注：①0和任意自然数的最大公约数就是那个自然数②互质指最大公约数等于1的两个自然数。 格式

PROGRAM NAME: frac1 INPUT FORMAT: (file frac1.in)

第 21 页 共 53 页

单独的一行 一个自然数N(1..160) OUTPUT FORMAT: (file frac1.out)

每个分数单独占一行，按照大小次序排列 SAMPLE INPUT 5

SAMPLE OUTPUT 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

Sorting a Three-Valued Sequence三值的排序

描述

排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌序的时候。在这个任务中可能的值只有三种1，2和3。我们用交换的方法把他排成升序的。

写一个程序计算出，给定的一个1,2,3组成的数字序列，排成升序所需的最少交换次数。 格式

PROGRAM NAME: sort3 INPUT FORMAT: (file sort3.in) Line 1:

N (1 <= N <= 1000) Lines 2-N+1:

每行一个数字，共N行。（1..3） OUTPUT FORMAT: (file sort3.out)

共一行，一个数字。表示排成升序所需的最少交换次数。 SAMPLE INPUT 9 2 2 1 3

第 22 页 共 53 页

3 3 2 3 1

SAMPLE OUTPUT 4

Healthy Holsteins健康的荷斯坦奶牛 描述

农民JOHN以拥有世界上最健康的奶牛为骄傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持它们的健康，使喂给牛的饲料的种数最少。

给出牛所需的最低的维他命量，输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少。 维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解。 格式

PROGRAM NAME: holstein INPUT FORMAT: (file holstein.in)

第1行：一个整数V(1<=V<=25)，表示需要的维他命的种类数。

第2行：V个整数(1<=每个数<=1000)，表示牛每天需要的维他命的最小量。 第3行：一个整数G(1<=G<=15)，表示可用来喂牛的饲料的种数。 下面G行，第i行表示编号为i饲料包含的各种维他命的量的多少。 OUTPUT FORMAT: (file holstein.out)

输出文件只有一行，包括： 牛必需的最小的饲料种数P

后面有P个数，表示所选择的饲料编号（按从小到大排列）。 如果有多个解，输出饲料序号最小的（即字典序最小）。 SAMPLE INPUT 4

100 200 300 400 3

50 50 50 50 200 300 200 300 900 150 389 399 SAMPLE OUTPUT 2 1 3

Hamming Codes海明码 描述

给出 N，B 和 D：找出 N 个编码（1 <= N <= 64），每个编码有 B 位[二进制]（1 <= B <= 8），使得两两编码之间至少有 D 个单位的“海明距离”（1 <= D <= 7）。“海明距离”是指对于两个编码，他们的二进制表示法中的不同二进制位的数目。看下面的两个编码 0x554 和

第 23 页 共 53 页

0x234 之间的区别（0x554 表示一个十六进制数，每个位上分别是 5，5，4）:

0x554 = 0101 0101 0100

0x234 = 0010 0011 0100(不是将每一位分别转为2进制，这里空格只是为了方便演示) 不同位 xxx xx

因为有五个位不同，所以“海明距离”是 5。 格式

PROGRAM NAME: hamming INPUT FORMAT: (file hamming.in)

一行，包括 N, B, D。 OUTPUT FORMAT: (file hamming.out)

N 个编码（用十进制表示），要排序，十个一行。如果有多解，你的程序要输出这样的解：假如把它化为 2^B 进制的数，它的值要最小。 SAMPLE INPUT 16 7 3

SAMPLE OUTPUT

0 7 25 30 42 45 51 52 75 76 82 85 97 102 120 127

提示

必须与其他所有的数相比、海明码都符合要求,这个数才正确!

Section 2.2

Preface Numbering序言页码 一类书的序言是以罗马数字标页码的。传统罗马数字用单个字母表示特定的数值，以下是标准数字表:

I 1 L 50 M 1000 V 5 C 100 X 10 D 500

最多3个同样的可以表示为10n的数字(I,X,C,M)可以连续放在一起，表示它们的和: III=3 CCC=300

可表示为5x10n的字符(V,L,D)从不连续出现。

除了下一个规则，一般来说，字符以递减的顺序接连出现: CCLXVIII = 100+100+50+10+5+1+1+1 = 268

有时，一个可表示为10n的数出现在一个比它大1级或2级的数前(I在V或X前面，X在L或C前面，等等)。在这种情况下，数值等于后面的那个数减去前面的那个数: IV = 4 IX = 9 XL = 40

像XD, IC, 和XM这样的表达是非法的，因为前面的数比后面的数小太多。对于XD(490的

第 24 页 共 53 页

错误表达)，可以写成 CDXC; 对于IC(99的错误表达)，可以写成XCIX; 对于XM(990的错误表达)，可以写成CMXC。

给定N(1 <= N < 3,500)， 序言的页码数，请统计在第1页到第N页中，有几个I出现，几个V出现，等等 (从小到大的顺序)。不要输出并没有出现过的字符。

比如N = 5, 那么页码数为: I, II, III, IV, V. 总共有7个I出现，2个V出现。 格式

PROGRAM NAME: preface INPUT FORMAT: (preface.in) 一个整数N。

OUTPUT FORMAT: (preface.out)

每行一个字符和一个数字k，表示这个字符出现了k次。字符必须按数字表中的递增顺序输出。

SAMPLE INPUT 5

SAMPLE OUTPUT I 7 V 2

Subset Sums集合 描述

对于从1到N (1 <= N <= 39) 的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的： {3} 和 {1,2}

这是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数） 如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分法的子集合各数字和是相等的:

{1,6,7} 和 {2,3,4,5} {注 1+6+7=2+3+4+5} {2,5,7} 和 {1,3,4,6} {3,4,7} 和 {1,2,5,6} {1,2,4,7} 和 {3,5,6}

给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。 格式

PROGRAM NAME: subset INPUT FORMAT: (file subset.in)

输入文件只有一行，且只有一个整数N OUTPUT FORMAT: (file subset.out)

输出划分方案总数，如果不存在则输出0。 SAMPLE INPUT

第 25 页 共 53 页

7

SAMPLE OUTPUT 4

Runaround Numbers循环数 描述

循环数是那些不包括0且没有重复数字的整数(比如81362)并且还应同时具有一个有趣的性质, 就像这个例子:

如果你从最左边的数字开始(在这个例子中是8)向右数最左边这个数(如果数到了最右边就回到最左边),你会停止在另一个新的数字(如果没有 停在一个不同的数字上，这个数就不是循环数).就像: 8 1 3 6 2 从最左边接下去数8个数字: 1 3 6 2 8 1 3 6 所以下一个数字是6 重复这样做 (这次从“6”开始数6个数字) 并且你会停止在一个新的数字上: 2 8 1 3 6 2, 也就是2

再这样做 (这次数两个): 8 1 再一次 (这次一个): 3

又一次: 6 2 8 这时你回到了起点,在经过每个数字一次后回到起点的就是循环数。如果你经过每一个数字一次以后没有回到起点, 你的数字不是一个循环数。

给你一个数字 M (在1到9位之间), 找出第一个比 M大的循环数, 输入数据保证结果能用一个无符号长整型数装下。 格式

PROGRAM NAME: runround INPUT FORMAT: (file runround.in) 仅仅一行, 包括M OUTPUT FORMAT: (file runround.out)

仅仅一行，包括第一个比M大的循环数。 SAMPLE INPUT 81361

SAMPLE OUTPUT 81362

Party Lamps派对灯(IOI98) 描述

在IOI98的节日宴会上，我们有N(10<=N<=100)盏彩色灯，他们分别从1到N被标上号码。 这些灯都连接到四个按钮：

按钮1：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。 按钮2：当按下此按钮，将改变所有奇数号的灯。 按钮3：当按下此按钮，将改变所有偶数号的灯。

按钮4：当按下此按钮，将改变所有序号是3*K+1(K>=0)的灯。例如：1,4,7...

一个计数器C记录按钮被按下的次数。当宴会开始，所有的灯都亮着，此时计数器C为0。 你将得到计数器C(0<=C<=10000)上的数值和经过若干操作后某些灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态，并且没有重复。 格式

第 26 页 共 53 页

PROGRAM NAME: lamps INPUT FORMAT: (file lamps.in)

不会有灯会在输入中出现两次。 第一行: N。

第二行: C最后显示的数值。

第三行: 最后亮着的灯,用一个空格分开，以-1为结束。 第四行: 最后关着的灯,用一个空格分开，以-1为结束。 OUTPUT FORMAT: (file lamps.out)

每一行是所有灯可能的最后状态(没有重复)。每一行有N个字符，第1个字符表示1号灯，最后一个字符表示N号灯。0表示关闭，1表示亮着。这些行必须从小到大排列（看作是二进制数）。

如果没有可能的状态，则输出一行'IMPOSSIBLE'。 SAMPLE INPUT 10 1 -1 7 -1

在这个样例中，有10盏灯，只有1个按钮被按下。最后7号灯是关着的。 SAMPLE OUTPUT 0000000000 0101010101 0110110110

在这个样例中，有三种可能的状态： 所有灯都关着

1,4,7,10号灯关着，2,3,5,6,8,9亮着。 1,3,5,7,9号灯关着，2, 4, 6, 8, 10亮着。

Section 2.3

Longest Prefix最长前缀 IOI'96 描述

在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的（称之为元素的）序列很感兴趣。

如果一个集合 P 中的元素可以通过串联（允许重复；串联，相当于 Pascal 中的 “+” 运算符）组成一个序列 S ，那么我们认为序列 S 可以分解为 P 中的元素。并不是所有的元素都必须出现。举个例子，序列 ABABACABAAB 可以分解为下面集合中的元素： {A, AB, BA, CA, BBC}

序列 S 的前面 K 个字符称作 S 中长度为 K 的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列，计算这个序列中(由集合元素组成的)最长的前缀的长度。 格式

PROGRAM NAME: prefix INPUT FORMAT

第 27 页 共 53 页

输入数据的开头包括 1..200 个元素（长度为 1..10 ）组成的集合，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个 “.” 的行。集合中的元素没有重复。接着是大写字母序列 S ，长度为 1..200,000 ，用一行或者多行的字符串来表示，每行不超过 76 个字符。换行符并不是序列 S 的一部分。 OUTPUT FORMAT

只有一行，输出一个整数，表示 S 能够分解成 P 中元素的最长前缀的长度。 SAMPLE INPUT (file prefix.in) A AB BA CA BBC .

ABABACABAABC

SAMPLE OUTPUT (file prefix.out) 11

Cow Pedigrees 奶牛家谱 描述

农民约翰准备购买一群新奶牛。 在这个新的奶牛群中, 每一个母亲奶牛都生两小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3 <= N < 200)。这些二叉树有如下性质:

每一个节点的度是0或2。度是这个节点的孩子的数目。

树的高度等于K(1 < K < 100)。高度是从根到最远的那个叶子所需要经过的结点数; 叶子是指没有孩子的节点。

有多少不同的家谱结构? 如果一个家谱的树结构不同于另一个的, 那么这两个家谱就是不同的。输出可能的家谱树的个数除以9901的余数。 格式

PROGRAM NAME: nocows

INPUT FORMAT (file nocows.in)

第1行: 两个空格分开的整数, N和K。

OUTPUT FORMAT (file nocows.out)

第 1 行: 一个整数，表示可能的家谱树的个数除以9901的余数。 SAMPLE INPUT 5 3

SAMPLE OUTPUT 2

OUTPUT DETAILS

有5个节点，高为3的两个不同的家谱：

@ @ / \\ / \\

第 28 页 共 53 页

@ @ 和 @ @ / \\ / \\ @ @ @ @

Zero Sum 描述

请考虑一个由1到N（N=3, 4, 5 ... 9）的数字组成的递增数列：1 2 3 ... N。 现在请在数列中插入“+”表示加，或者“-”表示减，“ ”表示空白(例如1-2 3就等于1-23)，来将每一对数字组合在一起（请不在第一个数字前插入符号）。 计算该表达式的结果并判断其值是否为0。 请你写一个程序找出所有产生和为零的长度为N的数列。 格式

PROGRAM NAME: zerosum INPUT FORMAT

单独的一行表示整数N (3 <= N <= 9)。 OUTPUT FORMAT

按照ASCII码的顺序，输出所有在每对数字间插入“+”, “-”, 或 “ ”后能得到和为零的数列。 SAMPLE INPUT (file zerosum.in) 7

SAMPLE OUTPUT (file zerosum.out) 1+2-3+4-5-6+7 1+2-3-4+5+6-7 1-2 3+4+5+6+7 1-2 3-4 5+6 7 1-2+3+4-5+6-7 1-2-3-4-5+6+7

Money Systems货币系统 描述

母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。由于他们特殊的思考方式，他们对货币的数值感到好奇。

传统地，一个货币系统是由1,5,10,20 或 25,50, 和 100的单位面值组成的。 母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。

举例来说, 使用一个货币系统 {1,2,5,10,...}产生 18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。 写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数将会适合long long (C/C++) 和 Int64 (Free Pascal)，即在0 到2^63-1之间。 格式

PROGRAM NAME: money INPUT FORMAT: (file money.in)

货币系统中货币的种类数目是 V (1<= V<=25)。要构造的数量钱是 N (1<= N<=10,000)。 第 1 行: 二整数，V 和 N 。 第 2 行： 可用的货币的面值 。

第 29 页 共 53 页

OUTPUT FORMAT: (file money.out)

单独的一行包含那个可能的用这v种硬币凑足n单位货币的方案数。 SAMPLE INPUT 3 10 1 2 5

SAMPLE OUTPUT 10

Controlling Companies 控制公司

题目

有些公司是其他公司的部分拥有者，因为他们获得了其他公司发行的股票的一部分。例如，福特公司拥有马自达公司12%的股票。据说，如果至少满足了以下三个条件之一，公司A就可以控制公司B了：

1. 公司A = 公司B。

2. 公司A拥有大于50%的公司B的股票。

3. 公司A控制K(K >= 1)个公司，记为C1, ..., CK，每个公司Ci拥有xi%的公司B的股

票，并且x1+ .... + xK > 50%。

给你一个表，每行包括三个数(i,j,p)；表明公司i享有公司j的p%的股票。计算所有的数对(h,s)，表明公司h控制公司s。至多有100个公司。 写一个程序读入三对数(i,j,p)，i,j和p是都在范围(1..100)的正整数，并且找出所有的数对(h,s)，使得公司h控制公司s。 INPUT FORMAT

第一行： N，表明接下来三对数的数量。{即(i,j,p)的数量}

第二行到第N+1行： 每行三个整数作为一个三对数(i,j,p)，如上文所述。{表示公司 i 拥有公司j p%的股份}

SAMPLE INPUT (file concom.in) 3 1 2 80 2 3 80 3 1 20

OUTPUT FORMAT

输出零个或更多个的控制其他公司的公司。每行包括两个整数A、B,表示A公司控制了B公司。将输出的数对以升序排列。 请不要输出控制自己的公司。

SAMPLE OUTPUT (file concom.out) 1 2 1 3 2 3

Section 2.4

第 30 页 共 53 页

The Tamworth Two 两只塔姆沃斯牛

题目描述

两只牛逃跑到了森林里。农夫John开始用他的经验追捕这两头牛。你的任务是模拟他们的行为(牛和John)。

追击在10x10的平面网格内进行。一个格子可以是：

一个障碍物, 两头牛(它们总在一起), 或者 农民John. 两头牛和农民John可以在同一个格子内(当他们相遇时)，但是他们都不能进入有障碍的格子。 一个格子可以是： . 空地 * 障碍物 C 两头牛 F 农民John

这里有一个地图的例子： *...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*......

牛在地图里以固定的方式游荡。每分钟，它们可以向前移动或是转弯。如果前方无障碍且不会离开地图，它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转90度。 农民John深知牛的移动方法，他也这么移动。

每次(每分钟)农民John和两头牛的移动是同时的。如果他们在移动的时候穿过对方，但是没有在同一格相遇，我们不认为他们相遇了。当他们在某分钟末在某格子相遇，那么追捕结束。

读入十行表示农夫John,两头牛和所有障碍的位置的地图。每行都只包含10个字符，表示的含义和上面所说的相同，你可以确定地图中只有一个'F'和一个'C'.'F'和'C'一开始不会处于同一个格子中。

计算农夫John需要多少分钟来抓住他的牛，假设牛和农夫John一开始的行动方向都是正北（即上）。 如果John和牛永远不会相遇，输出0。

PROGRAM NAME: ttwo INPUT FORMAT 第1-10行:

每行10个字符，表示如上文描述的地图。 SAMPLE INPUT (file ttwo.in) *...*..... ......*...

第 31 页 共 53 页

...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*......

OUTPUT FORMAT

输出一个数字，表示John需要多少时间才能抓住牛们。如果John无法抓住牛，则输出0。 SAMPLE OUTPUT (file ttwo.out) 49

Overfencing穿越栅栏 描述

农夫John在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，他所建造的 迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。 给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。 2*H+1行，每行2*W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数(就是从最“糟糕”的一点， 走出迷宫的最少步数）。（即使从这一点以最优的方式走向最靠近的出口，它仍然需要最多的步数）当然了，牛们只会水平或垂直地在X或Y轴上移动，他们从来不 走对角线。每移动到一个新的方格算作一步（包括移出迷宫的那一步） 这是一个W=5,H=3的迷宫： +-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+

如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。 格式

PROGRAM NAME: maze1 INPUT FORMAT: (file maze1.in)

第一行： W和H（用空格隔开）

第二行至第2*H+1行： 每行2*W+1个字符表示迷宫 OUTPUT FORMAT: (file maze1.out)

输出一个单独的整数，表示能保证牛从迷宫中任意一点走出迷宫的最小步数。 SAMPLE INPUT 5 3

+-+-+-+-+-+ | |

第 32 页 共 53 页

+-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+

SAMPLE OUTPUT 9

Cow Tours牛的旅行

农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区通过任何路径都不连通。这样，农民John就有多个牧场了。

John想在农场里添加一条路径(注意，恰好一条)。对这条路径有以下限制：

一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。考虑如下的有5个牧区的牧场，牧区用“*”表示，路径用直线表示。每一个牧区都有自己的坐标：

15,15 20,15 D E *-------* | _/| | _/ | | _/ | |/ | *--------*-------* A B C 10,10 15,10 20,10

这个牧场的直径大约是12.07106, 最远的两个牧区是A和E，它们之间的最短路径是A-B-E。 这里是另一个牧场：

*F 30,15 / _/ _/ / *------* G H

25,10 30,10

这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。 注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。

输入文件包括牧区、它们各自的坐标，还有一个如下的对称邻接矩阵： A B C D E F G H A 0 1 0 0 0 0 0 0 B 1 0 1 1 1 0 0 0

第 33 页 共 53 页

C 0 1 0 0 1 0 0 0 D 0 1 0 0 1 0 0 0 E 0 1 1 1 0 0 0 0 F 0 0 0 0 0 0 1 0 G 0 0 0 0 0 1 0 1 H 0 0 0 0 0 0 1 0

输入文件至少包括两个不连通的牧区。 请编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。 格式

PROGRAM NAME: cowtour INPUT FORMAT: (file cowtour.in)

第1行: 一个整数N (1 <= N <= 150), 表示牧区数

第2到N+1行: 每行两个整数X,Y (0 <= X ,Y<= 100000), 表示N个牧区的坐标。注意每个 牧区的坐标都是不一样的。

第N+2行到第2*N+1行: 每行包括N个数字(0或1) 表示如上文描述的对称邻接矩阵。 OUTPUT FORMAT: (file cowtour.out)

只有一行，包括一个实数，表示所求直径。数字保留六位小数。 SAMPLE INPUT 8 10 10 15 10 20 10 15 15 20 15 30 15 25 10 30 10 01000000 10111000 01001000 01001000 01110000 00000010 00000101 00000010

SAMPLE OUTPUT 22.071068

第 34 页 共 53 页

Bessie Come Home 回家

描述

现在是晚餐时间,而母牛们在外面分散的牧场中。 农民约翰按响了电铃,所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只速度最快的母牛)。 在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。 每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。 有时，两个牧场(可能是自我相同的)之间会有超过一条道路相连。 至少有一个牧场和谷仓之间有道路连接。 因此,所有的母牛最后都能到达谷仓,并且母牛总是走最短的路径。 当然,母牛能向着任意一方向前进,并且她们以相同的速度前进。 牧场被标记为'a'..'z'和'A'..'Y',在用大写字母表示的牧场中有一只母牛,小写字母中则没有。 谷仓的标记是'Z',注意没有母牛在谷仓中。 注意'm'和'M'不是一个牧场 格式

PROGRAM NAME: comehome INPUT FORMAT

第 1 行: 整数 P(1<= P<=10000),表示连接牧场(谷仓)的道路的数目。 第 2 ..P+1行: 用空格分开的两个字母和一个整数:

被道路连接牧场的标记和道路的长度(1<=长度<=1000)。 SAMPLE INPUT (file comehome.in) 5 A d 6 B d 3 C e 9 d Z 8 e Z 3

OUTPUT FORMAT

单独的一行包含二个项目: 最先到达谷仓的母牛所在的牧场的标记,和这只母牛走过的路径的长度。

SAMPLE OUTPUT (file comehome.out) B 11

Fractions to Decimals 分数化小数

描述

写一个程序，输入一个形如N/D的分数(N是分子，D是分母)，输出它的小数形式。 如果小数有循环节的话，把循环节放在一对圆括号中。

例如, 1/3 =0.33333333 写成0.(3), 41/333 = 0.123123123... 写成0.(123), 用xxx.0 等表示整数。 典型的转化例子： 1/3 = 0.(3) 22/5 = 4.4

1/7 = 0.(142857) 2/2 = 1.0

第 35 页 共 53 页

3/8 = 0.375

45/56 = 0.803(571428) PROGRAM NAME fracdec

INPUT FORMAT

单独的一行包括被空格分开的N和D(1 <= N,D <= 100000)。 SAMPLE INPUT (file fracdec.in) 45 56

OUTPUT FORMAT

按照上面规则计算出的小数表达式.如果结果长度大于76,每行输出76个字符.

SAMPLE OUTPUT (file fracdec.out) 0.803(571428)

Chapter3

Section 3.1

Agri-Net最短网络 描述

农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。 约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。 你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。 每两个农场间的距离不会超过100000 格式

PROGRAM NAME: agrinet INPUT FORMAT: (file agrinet.in)

第一行： 农场的个数，N（3<=N<=100）。

第二行..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。 OUTPUT FORMAT: (file agrinet.out)

只有一个输出，其中包含连接到每个农场的光纤的最小长度。 SAMPLE INPUT 4

0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0

第 36 页 共 53 页

SAMPLE OUTPUT 28

Score Inflation总分 描述

学生在我们USACO的竞赛中的得分越多我们越高兴。

我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。

我们可以从几个种类中选取竞赛的题目,这里的一个\种类\是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。 你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。 输入包括竞赛的时间,M(1 <= M <= 10,000)(不要担心,你要到了训练营中才会有长时间的比赛)和N,\种类\的数目1 <= N <= 10,000。 后面的每一行将包括两个整数来描述一个\种类\

第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。 你的程序应该确定我们应该从每个\种类\中选多少道题目使得能在竞赛的时间中得到最大的分数。

来自任意的\种类\的题目数目可能任何非负数(0或更多)。 计算可能得到的最大分数。 格式

PROGRAM NAME: inflate INPUT FORMAT： (file inflate.in)

第 1 行: M, N--竞赛的时间和题目\种类\的数目。

第 2-N+1 行: 两个整数:每个\种类\题目的分数和耗时。 OUTPUT FORMAT： (file inflate.out)

单独的一行包括那个在给定的限制里可能得到的最大的分数。 SAMPLE INPUT 300 4 100 60 250 120 120 100 35 20

SAMPLE OUTPUT 605

{从第2个\种类\中选两题第4个\种类\中选三题}

Humble Numbers丑数 描述

对于一给定的素数集合 S = {p1, p2, ..., pK},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p1、p1*p2、p1*p1、p1*p2*p3...(还有其它)。该集合被称为S集合的“丑数集合”。

注意：我们不认为1 是一个丑数。

你的工作是对于输入的集合S去寻找“丑数集合”中的第N个“丑数”。所有答案可以用

第 37 页 共 53 页

longint(signed 32-bit)存储。 格式

PROGRAM NAME: humble INPUT FORMAT: (file humble.in)

第 1 行: 二个被空格分开的整数:K 和 N ， 1<= K<=100 ， 1<= N<=100,000. 第 2 行: K 个被空格分开的整数:集合S的元素 OUTPUT FORMAT: (file humble.out)

单独的一行，输出对于输入的S的第N个丑数。 SAMPLE INPUT 4 19 2 3 5 7

SAMPLE OUTPUT 27

Shaping Regions形成的区域 描述

N个不同的颜色的不透明的长方形(1 <= N <= 1000)被放置在一张宽为A长为B的白纸上。 这些长方形被放置时，保证了它们的边与白纸的边缘平行。 所有的长方形都放置在白纸内，所以我们会看到不同形状的各种颜色。 坐标系统的原点(0,0)设在这张白纸的左下角，而坐标轴则平行于边缘。 格式

PROGRAM NAME: rect1 INPUT FORMAT: (file rect1.in)

按顺序输入放置长方形的方法。第一行输入的是那个放在底的长方形(即白纸)。 第 1 行: A ， B 和 N, 由空格分开 (1 <=A, B<=10,000)

第 2 到N+1行: 为五个整数 llx, lly, urx, ury, color 这是一个长方形的左下角坐标，右上角坐标和颜色。

颜色 1和底部白纸的颜色相同。 (1 <= color <= 2500) OUTPUT FORMAT： (file rect1.out)

输出文件应该包含一个所有能被看到颜色连同该颜色的总面积的清单( 即使颜色的区域不是连续的)，按color增序排列。 不要显示没有出现过的颜色。 SAMPLE INPUT 20 20 3 2 2 18 18 2 0 8 19 19 3 8 0 10 19 4

SAMPLE OUTPUT 1 91 2 84

第 38 页 共 53 页

3 187 4 38

INPUT EXPLANATION

请注意：被(0,0)和(2,2)所描绘的是2个单位宽、2个单位高的区域 这里有一个示意图输入： 11111111111111111111 33333333443333333331 33333333443333333331 33333333443333333331 33333333443333333331 33333333443333333331 33333333443333333331 33333333443333333331 33333333443333333331 33333333443333333331 33333333443333333331 33333333443333333331 11222222442222222211 11222222442222222211 11222222442222222211 11222222442222222211 11222222442222222211 11222222442222222211 11111111441111111111 11111111441111111111

'4'在(8,0)与(10,19)形成的是宽为2的区域,而不是3.（也就是说，4形成的区域包含(8,0)和(8,1) ，而不是(8,0)和(8,2)） 。

Contact 联系 描述

奶牛们开始对用射电望远镜扫描牧场外的宇宙感兴趣。最近，他们注意到了一种非常奇怪的脉冲调制微波从星系的中央发射出来。他们希望知道电波是否是被某些地外生命发射出来的，还是仅仅是普通的的星星发出的。

帮助奶牛们用一个能够分析他们在文件中记下的记录的工具来找到真相。他们在寻找长度在A到B之间（含）在每天的数据文件中重复得最多的比特 序列 (1 <= A <= B <= 12)。他们在找那些重复得最多的比特序列。一个输入限制告诉你应输出多少频率最多的序列。 符合的序列可能会重叠，并且至少重复一次的序列会被计数。 格式

PROGRAM NAME: contact INPUT FORMAT: (file contact.in)

第一行： 三个用空格分隔的整数: A, B, N; (1 <= N < 50)

第二行及以后: 一个最多200，000字符的序列，全是0或1; 每行有80个字符，除了可能的最后一行。

第 39 页 共 53 页

OUTPUT FORMAT: (file contact.out)

输出N个频率最高的序列（按照频率由高到低的次序）。由短到长排列频率相同的这些序列，如果长短相同，按二进制大小排列。如果出现的序列个数小于N，输出存在的序列。 对于每个存在的频率，先输出单独包含该频率的一行，再输出以空格分隔的这些频率。每行六个（除非少于六个剩下）。 SAMPLE INPUT 2 4 10

01010010010001000111101100001010011001111000010010011110010000000

在样例里，序列100出现了12次，而序列1000出现了5次。次数最多的序列是00，出现了23次。

SAMPLE OUTPUT 23 00 15 01 10 12 100 11

11 000 001 10 010 8 0100 7

0010 1001 6

111 0000 5

011 110 1000 4

0001 0011 1100

Stamps 邮票 描述

已知一个 N 枚邮票的面值集合（如，{1 分，3 分}）和一个上限 K —— 表示信封上能够贴 K 张邮票。计算从 1 到 M 的最大连续可贴出的邮资。

例如，假设有 1 分和 3 分的邮票；你最多可以贴 5 张邮票。很容易贴出 1 到 5 分的邮资（用 1 分邮票贴就行了），接下来的邮资也不难： 6 = 3 + 3 7 = 3 + 3 + 1 8 = 3 + 3 + 1 + 1 9 = 3 + 3 + 3

10 = 3 + 3 + 3 + 1

第 40 页 共 53 页

11 = 3 + 3 + 3 + 1 + 1 12 = 3 + 3 + 3 + 3

13 = 3 + 3 + 3 + 3 + 1。

然而，使用 5 枚 1 分或者 3 分的邮票根本不可能贴出 14 分的邮资。因此，对于这两种邮票的集合和上限 K=5，答案是 M=13。 [规模最大的一个点的时限是3s] 格式

PROGRAM NAME: stamps INPUT FORMAT: (file stamps.in)

第 1 行： 两个整数，K 和 N。K（1 <= K <= 200）是可用的邮票总数。N（1 <= N <= 50）是邮票面值的数量。

第 2 行 .. 文件末： N 个整数，每行 15 个，列出所有的 N 个邮票的面值，每张邮票的面值不超过 10000。 OUTPUT FORMAT: (file stamps.out)

第 1 行：一个整数，从 1 分开始连续的可用集合中不多于 K 张邮票贴出的邮资数。 SAMPLE INPUT 5 2 1 3

SAMPLE OUTPUT 13

Section 3.2

Factorials阶乘 描述

N的阶乘写作N!表示小于等于N的所有正整数的乘积。

阶乘会很快的变大，如13!就必须用32位整数类型来存储，70！即使用浮点数也存不下了。 你的任务是找到阶乘最后面的非零位。举个例子: 5!=1*2*3*4*5=120所以5!的最后面的非零位是2 7!=1*2*3*4*5*6*7=5040，所以最后面的非零位是4 格式

PROGRAM NAME: fact4 INPUT FORMAT: (file fact4.in)

共一行，一个整数不大于4,220的整数N。 OUTPUT FORMAT: (file fact4.out)

共一行，输出N!最后面的非零位。 SAMPLE INPUT 7

SAMPLE OUTPUT 4

第 41 页 共 53 页

Stringsobits01串 描述

考虑排好序的N(N<=31)位二进制数。

你会发现，这很有趣。因为他们是排列好的，而且包含所有可能的长度为N且含有1的个数小于等于L(L<=N)的数。

你的任务是输出第i（1<=i<=长度为N的二进制数的个数）小的，长度为N，且含有1的个数小于等于L的那个二进制数。 格式

PROGRAM NAME: kimbits INPUT FORMAT: (file kimbits.in)

共一行，用空格分开的三个整数N，L，i。 OUTPUT FORMAT: (file kimbits.out)

共一行，输出满足条件的第i小的二进制数。 SAMPLE INPUT 5 3 19

SAMPLE OUTPUT 10011

Spinning Wheels纺车的轮子 描述

一架纺车有五个纺轮，这五个不透明的轮子边缘上都有一些缺口。这些缺口必须被迅速而准确地排列好。每个轮子都有一个起始标记（在0度），这样所有的 轮子都可以在统一的已知位置开始转动。轮子按照角度变大的方向旋转，所以从起始位置开始，在一定的时间内，它们依次转过1度，2度等等（虽然这些轮子很可 能不会同时转过这些角度）。

这是一个整数问题。轮子不会转过1.5度或23.51234123度这样的角度。例如，轮子可能在一秒钟内转过20到25度甚至30到40度（如果转得快的话）。

这个问题中的所有角度都限制在 0 <= 角度 <= 359 这个范围内。轮子转过 359 度后接下来就是 0 度。每个轮子都有一个确定的旋转速度，以秒作为单位。1 <= 速度 <= 180。 轮子上的缺口的起始角度和缺口大小（或长度）各由一个整数表示，都以度为单位。在一个轮子上，两个缺口之间至少有一度的间隔。

在起始位置，设时间为 0，所有的轮子的起始标记排列成一条直线。你的程序必须计算，最早出现每个的轮子上的缺口同其他轮子上的缺口对准（也就是一束光可以通过五个轮子上的五个缺口）情况的时间。这些缺口在任意一个角度对准。 格式

PROGRAM NAME: spin INPUT FORMAT: (file spin.in)

输入中的五行对应五个轮子。

第一个数字表示轮子的转动速度。下一个数字是缺口的数目 W。1 <= W <= 5。接下来的 W 对数字表示每个缺口的起始角度和长度。 OUTPUT FORMAT: (file spin.out)

第 42 页 共 53 页

只有一行，包括一个整数，表示光能够通过这五个轮子的最早时间。如果无解，输出'none'（小写，不含引号）。 SAMPLE INPUT 30 1 0 120 50 1 150 90 60 1 60 90 70 1 180 180 90 1 180 60

SAMPLE OUTPUT 9

Feed Ratios饲料调配 描述

农夫约翰从来只用调配得最好的饲料来喂他的奶牛。饲料用三种原料调配成：大麦，燕麦和小麦。他知道自己的饲料精确的配比，在市场上是买不到这样的饲料的。他只好购买其他三种混合饲料（同样都由三种麦子组成），然后将它们混合，来调配他的完美饲料。

给出三组整数，表示 大麦：燕麦：小麦 的比例，找出用这三种饲料调配 x：y：z 的饲料的方法。

例如，给出目标饲料 3：4：5 和三种饲料的比例： 1:2:3 3:7:1 2:1:2

你必须编程找出使这三种饲料用量最少的方案，要是不能用这三种饲料调配目标饲料，输出“NONE”。“用量最少”意味着三种饲料的用量（整数）的和必须最小。 对于上面的例子，你可以用8份饲料1，1份饲料2，和5份饲料3，来得到7份目标饲料： 8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) = (21:28:35) = 7*(3:4:5) 表示饲料比例的整数，都是小于100的非负整数。表示各种饲料的份数的整数，都小于100。一种混合物的比例不会由其他混合物的比例直接相加得到。 格式

PROGRAM NAME: ratios INPUT FORMAT: (file ratios.in)

Line 1: 三个用空格分开的整数，表示目标饲料

Line 2..4: 每行包括三个用空格分开的整数，表示农夫约翰买进的饲料的比例 OUTPUT FORMAT: (file ratios.out)

输出文件要包括一行，这一行要么有四个整数，要么是“NONE”。前三个整数表示三种饲料的份数，用这样的配比可以得到目标饲料。第四个整数表示混合三种饲料后得到的目标饲料的份数。

SAMPLE INPUT 3 4 5 1 2 3 3 7 1 2 1 2

第 43 页 共 53 页

SAMPLE OUTPUT 8 1 5 7

Magic Squares 魔板 描述

在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有8个大小相同的格子的魔板： 1 2 3 4 8 7 6 5

我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针 方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列（1，2，3，4，5，6，7，8）来表示。这是基本状态。

这里提供三种基本操作，分别用大写字母“A”，“B”，“C”来表示（可以通过这些操作改变魔板的状态）：

“A”：交换上下两行；

“B”：将最右边的一列插入最左边； “C”：魔板中央四格作顺时针旋转。 下面是对基本状态进行操作的示范： A: 8 7 6 5 1 2 3 4 B: 4 1 2 3 5 8 7 6 C: 1 7 2 4 8 6 3 5

对于每种可能的状态，这三种基本操作都可以使用。

你要编程计算用最少的基本操作完成基本状态到目标状态的转换，输出基本操作序列。 格式

PROGRAM NAME: msquare INPUT FORMAT: (file msquare.in)

只有一行，包括8个整数，用空格分开（这些整数在范围 1——8 之间），表示目标状态。 OUTPUT FORMAT: (file msquare.out)

Line 1: 包括一个整数，表示最短操作序列的长度。

Line 2: 在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出60个字符。

SAMPLE INPUT 2 6 8 4 5 7 3 1

SAMPLE OUTPUT 7

BCABCCB

Sweet Butter 香甜的黄油

第 44 页 共 53 页

描述

农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。

农夫John很狡猾。像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。 农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。 格式

PROGRAM NAME: butter INPUT FORMAT: (file butter.in)

第一行: 三个数：奶牛数N，牧场数P（2<=P<=800），牧场间道路数C(1<=C<=1450). 第二行到第N+1行: 1到N头奶牛所在的牧场号.

第N+2行到第N+C+1行： 每行有三个数：相连的牧场A、B，两牧场间距（1<=D<=255），当然,连接是双向的. OUTPUT FORMAT: (file butter.out)

一行 输出奶牛必须行走的最小的距离和. SAMPLE INPUT 3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5

样例图形

P2 P1 @--1--@ C1 \\ |\\ \\ | \\ 5 7 3 \\ | \\ \\| \\ C3 C2 @--5--@ P3 P4

SAMPLE OUTPUT 8

{说明： 放在4号牧场最优. }

第 45 页 共 53 页

Section 3.3

Riding the Fences骑马修栅栏 描述

农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。

每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。

你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。 输入数据保证至少有一个解。 格式

PROGRAM NAME: fence INPUT FORMAT： (fence.in)

第1行: 一个整数F(1 <= F <= 1024)，表示栅栏的数目

第2到F+1行: 每行两个整数i, j(1 <= i,j <= 500)表示这条栅栏连接i与j号顶点。 OUTPUT FORMAT： (fence.out)

输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。 SAMPLE INPUT 9 1 2 2 3 3 4 4 2 4 5 2 5 5 6 5 7 4 6

SAMPLE OUTPUT 1 2 3 4 2 5 4

第 46 页 共 53 页

6 5 7

Shopping Offers商店购物 描述

在商店中，每一种商品都有一个价格（用整数表示）。例如,一朵花的价格是 2 zorkmids （z），而一个花瓶的价格是 5z 。为了吸引更多的顾客，商店举行了促销活动。 促销活动把一个或多个商品组合起来降价销售，例如：

三朵花的价格是 5z 而不是 6z， 两个花瓶和一朵花的价格是 10z 而不是 12z。 编写一个程序，计算顾客购买一定商品的花费，尽量利用优惠使花费最少。尽管有时候添加其他商品可以获得更少的花费，但是你不能这么做。 对于上面的商品信息，购买三朵花和两个花瓶的最少花费是：以优惠价购买两个花瓶和一朵花（10z），以原价购买两朵花（4z）。 格式

PROGRAM NAME: shopping INPUT FORMAT： （file shopping.in)

输入文件包括一些商店提供的优惠信息，接着是购物清单。 第一行 优惠商品的种类数（0 <= s <= 99）。

第二行..第s+1 行 每一行都用几个整数来表示一种优惠方式。第一个整数 n （1 <= n <= 5），表示这种优惠方式由 n 种商品组成。后面 n 对整数 c 和 k 表示 k （1 <= k <= 5）个编号为 c （1 <= c <= 999）的商品共同构成这种优惠，最后的整数 p 表示这种优惠的优惠价（1 <= p <= 9999）。优惠价总是比原价低。 第 s+2 行 这一行有一个整数 b （0 <= b <= 5），表示需要购买 b 种不同的商品。

第 s+3 行..第 s+b+2 行 这 b 行中的每一行包括三个整数：c ，k ，和 p 。 C 表示唯一的商品编号（1 <= c <= 999），k 表示需要购买的 c 商品的数量（1 <= k <= 5）。p 表示 c 商品的原价（1 <= p <= 999）。最多购买 5*5=25 个商品。 OUTPUT FORMAT： (file shopping.out)

只有一行，输出一个整数：购买这些物品的最低价格。 SAMPLE INPUT 2

1 7 3 5 2 7 1 8 2 10 2 7 3 2 8 2 5

SAMPLE OUTPUT 14

Camelot亚瑟王的宫殿 描述

很久以前，亚瑟王和他的骑士习惯每年元旦去庆祝他们的友谊。为了纪念上述事件，我们把

第 47 页 共 53 页

这些是看作是一个有一人玩的棋盘游戏。有一个国王和若干个骑士被放置在一个由许多方格组成的棋盘上，没有两个骑士在同一个方格内。 这个例子是标准的8*8棋盘

国王可以移动到任何一个相邻的方格，从下图中黑子位置到下图中白子位置前提是他不掉出棋盘之外。

一个骑士可以从下图中黑子位置移动到下图中白子位置(走“日”字形） 但前提是他不掉出棋盘之外。

在游戏中，玩家可在每个方格上放不止一个棋子，假定方格足够大，任何棋子都不会阻碍到其他棋子正常行动。

玩家的任务就是把所有的棋子移动到同一个方格里——用最小的步数。为了完成这个任务，他必须按照上面所说的规则去移动棋子。另外，玩家可以 选择一个骑士跟国王从他们两个相遇的那个点开始一起行动，这时他们按照骑士的行动规则行动，其他的单独骑士则自己一直走到集中点。骑士和国王一起走的时 候，只算一个人走的步数。

写一个程序去计算他们集中在一起的最小步数，而且玩家必须自己找出这个集中点。当然，这些棋子可以在棋盘的任何地方集合。 格式

PROGRAM NAME: camelot INPUT FORMAT (file camelot.in)

第一行： 两个用空格隔开的整数：R,C 分别为棋盘行和列的长。不超过26列，30行。 第二行..结尾： 输入文件包含了一些有空格隔开的字母/数字对，一行有一个或以上。第一对为国王的位置，接下来是骑士的位置。可能没有骑士，也可能整个棋盘都是骑士。行从1开始，列从大写字母A开始。

第 48 页 共 53 页

OUTPUT FORMAT (file camelot.out)

单独一行表示棋子集中在一个方格的最小步数。 SAMPLE INPUT 8 8 D 4 A 3 A 8 H 1 H 8

国王位置在D4。一共有四个骑士，位置分别是A3,A8,H1和H8。 SAMPLE OUTPUT 10

SAMPLE OUTPUT ELABORATION 他们集中在B5。

骑士1: A3 - B5 (1步) 骑士2: A8 - C7 - B5 (2步)

骑士3: H1 - G3 - F5 - D4 (此时国王开始与这个骑士一起走) - B5 (4步) 骑士4: H8 - F7 - D6 - B5 (3步) 1 + 2 + 4 + 3 = 10步

Home on the Range 家的范围 描述

农民约翰在一片边长是N (2 <= N <= 250)英里的正方形牧场上放牧他的奶牛。(因为一些原因，他的奶牛只在正方形的牧场上吃草。)遗憾的是,他的奶牛已经毁坏一些土地。( 一些1平方英里的正方形)

农民约翰需要统计那些可以放牧奶牛的正方形牧场(至少是2x2的,在这些较大的正方形中没有一个点是被破坏的，也就是说，所有的点都是“1”)。

你的工作要在被供应的数据组里面统计所有不同的正方形放牧区域(>=2x2)的个数。当然，放牧区域可能是重叠。 格式

PROGRAM NAME: range INPUT FORMAT: (file range.in)

第 1 行:N,牧区的边长。

第 2 到 n+1行:N个没有空格分开的字符。

0 表示 \那一个区段被毁坏了\表示 \准备好被吃\。 OUTPUT FORMAT: (file range.out)

输出那些存在的正方形的边长和个数，一种一行。 SAMPLE INPUT 6

101111 001111 111111 001111

第 49 页 共 53 页

101101 111001

SAMPLE OUTPUT 2 10 3 4 4 1

A Game游戏 描述

有如下一个双人游戏:N(2 <= N <= 100)个正整数的序列放在一个游戏平台上，两人轮流从序列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。

编一个执行最优策略的程序，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为两位玩家执行最优策略。 格式

PROGRAM NAME: game1 INPUT FORMAT: (file game1.in)

第一行: 正整数N, 表示序列中正整数的个数。

第二行至末尾: 用空格分隔的N个正整数（大小为1-200）。 OUTPUT FORMAT: (file game1.out)

只有一行，用空格分隔的两个整数: 依次为玩家一和玩家二最终的得分。 SAMPLE INPUT 6

4 7 2 9 5 2

SAMPLE OUTPUT 18 11

Section 3.4

Closed Fences闭合的栅栏 描述

一个闭合的栅栏是平面上的一些不相交的首尾相连的线段形成的多边形，有N个角(顶点) (3 < N < 200)。 顶点不重合，它以逆时针方式以数组{xi, yi}给出(i=1,2,...,N)。

每一对相邻的顶点都是一条栅栏。因此共有N条栅栏 (定义xN+1=x1, yN+1=y1)。 这里有一个栅栏的例子和一个点x,y:

* x3,y3 x5,y5 / \\ x,y * * / \\ / \\ / \\ / * \\ x6,y6* x4,y4 \\

第 50 页 共 53 页

本文来源：https://www.bwwdw.com/article/gzua.html