没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
内容概要:本文档为2011年ACM国际大学生程序设计竞赛东中部区域赛的比赛规则和题目。比赛由IBM赞助,在五小时内完成九道编程题。参赛者需从标准输入读取数据并输出到标准输出,不允许使用文件或非标准库。编程语言限于C、C++和Java。比赛涉及的问题包括行星旅行的最便宜路径计算、图灵自行车链脱落周期计算、投票系统中的康多塞胜者判定、台球摆放的数学问题、董事会成员权力评估、GPS路径选择优化、桥梁建设节省路程计算、平衡移动雕塑的重量分配以及恋人相遇时间计算。 适合人群:计算机科学专业的学生和有一定编程基础的研发人员,特别是对算法和数据结构有浓厚兴趣的人士。 使用场景及目标:①熟悉ACM竞赛规则,提升编程竞赛技巧;②掌握经典算法题目的解法,如图论、动态规划、组合数学等;③提高解决复杂问题的能力,培养严谨的编程习惯。 其他说明:本文档不仅提供了具体的编程挑战,还展示了如何将实际问题抽象成算法模型,并通过编程手段求解。参赛者可以通过这些问题加深对计算机科学理论的理解,同时锻炼编程实践能力。文档中的题目难度适中,适合用于编程训练和竞赛准备。
资源推荐
资源详情
资源评论

ACM International Collegiate Programming Contest
2011 East Central Regional Contest
Grand Valley State University
University of Cincinnati
University of Windsor
Youngstown State University
October 22, 2011
Sponsored by IBM
Rules:
1. There are nine problems to be completed in five hours.
2. All questions require you to read the test data from standard input and write results to standard
output. You cannot use files for input or output. Additional input and output specifications can
be found in the General Information Sheet.
3. No whitespace should appear in the output except between printed fields .
4. All whitespace, either in input or output, will consist of exactly one blank character.
5. The allowed programming languages are C, C++ and Java.
6. All programs will be re-compiled prior to testing with the judges’ data.
7. Non-standard libraries cannot be used in your solutions. The Standard Template Library (STL)
and C++ string libraries are allowed. The standard Java API is available, except for those
packages that are deemed dangerous by contestant officials (e.g., that might generate a security
violation).
8. The input to all problems will consist of multiple test cases.
9. Programming style is not considered in this contest. You are free to code in whatever style you
prefer. Documentation is not required.
10. All communication with the judges will be handled by the PC
2
environment.
11. Judges’ decisions are to be considered final. No cheating will be tolerated.

2011 East Central Regional C ontest 1
Problem A: The Agency
Following in the footsteps of a number of flight searching startups you want to create the first inter-
planetary travel website. Your first problem is to quickly find the cheapest way to travel between two
planets. You have an advantage over your competitors because you have realized that all the planets
and the flights between them have a special structure. Each planet is represented by a string of N bits
and there is a flight between two planets if their N-bit strings differ in exactly one position.
The cost of a flight is the cost of landing on the destination planet. If the ith character in a planet’s
string is a 1 then the ith tax must be paid to land. The cost of landing on a planet is the sum of the
applicable taxes.
Given the starting planet, ending planet, and cost of the ith tax compute the cheapest set of flights to
get from the starting planet to the ending planet.
Input
Input for each test case will consist of two lines. The first line will have N (1 ≤ N ≤ 1,000), the number
of bits representing a planet; S, a string of N zeroes and ones representing the starting planet; and E,
a string representing the ending planet in the same format. The second line will contain N integers the
ith of which is the cost of the ith tax. All costs will be between 1 and 1,000,000. The input will be
terminated by a line with a single 0.
Output
For each test case output one number, the minimum cost to get from the starting planet to the ending
planet, using the format given below.
Sample Input
3 110 011
3 1 2
5 00000 11111
1 2 3 4 5
4 1111 1000
100 1 1 1
30 000000000000000000000000000000 111111111111111111111111111111
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
0
Sample Output
Case 1: 4
Case 2: 35
Case 3: 106
Case 4: 4960

2011 East Central Regional C ontest 2
Problem B: Chain of Fools
Many of you have heard the story of Turing’s bicycle: Seems the sprocket on the crank of the bicycle
had a broken prong. Also his chain had one link that was bent. When the bent link on the chain came
to hook up with the broken prong, the chain would fall off and Turing would stop and put the chain
back on. But Turing, being who he was, could predict just when this was going to happen — meaning
he would know how many pedal strokes it would be — and so would hop off his bike just before it
happened and gently move the pedals by hand as the undesired coupling passed. Then he’d be merrily
(we imagine) on his way. (A picture of the sprocket-chain set up is shown below.)
Your job here is to calculate the number of revolutions required in such a situation as Turing’s: You’ll
be given the number of prongs on the front sprocket, the number of links on the chain, the location of
the broken prong and the location of the bent link in the chain. The top prong is at location 0, then
the next one forward on the sprocket is location 1 and so on until prong numbered s − 1. (See the
diagram. Notice that prong s − 1 is the next prong that moves to the top of the sprocket as Turing
pedals.) Location of the links is similar: The link at the top of the sprocket is location 0 and so on
forward until c − 1. The chain falls off when broken prong and bent link are both at location 0.
Input
Input for each test case will be one line of the form s c p l, where s is the number of prongs on the front
sprocket (1 < s < 100) , c is the number of links in the chain (200 > c > s), p is the initial position of
the broken prong, and l is the initial position of the bent link. The line 0 0 0 0 will follow the last line
of input.
Broken prong and bent link will never both start at position 0.
Output
For each test case output a single one line as follows:
Case n: r m/s
if it requires r m/s revolutions to first fail, or
Case n: Never
if this can never happen.
Note that the denominator of the fraction will always be the number of prongs on the sprocket; the
fraction will not necessarily be in lowest terms. Always print the values of r and m, even if 0.
剩余12页未读,继续阅读
资源评论
ModelBulider
- 粉丝: 5138
创作灵感
更多 >
上传资源 快速赚钱
我的内容管理
展开
我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏
我的下载
下载帮助
前往需求广场,查看用户热搜最新资源
- 在AI+时代,中小技术转移机构如何利用数字化升级路径挖掘品牌影响力?.docx
- 在AI+数智化浪潮中,地方政府如何利用AI知识产权解决方案升级精细化管理效能?.docx
- 在AI+数智化浪潮中,科技园区如何利用数字化升级路径赋能市场占有率?.docx
- 在AI+数智化浪潮中,科研院所如何借助低成本的AI+数智技术解决收入增长乏力,同时重构服务升级,最终重构抢占市场先机?.docx
- 在AI+数智化浪潮中,破解市场竞争白热化难题,产业园区的出路在哪里?.docx
- 在AI+数智化浪潮中,政府部门如何借助全面的AI知识产权解决方案解决信息不对称壁垒,最终重构市场占有率,最终重构实现弯道超车?.docx
- 在当前经济形势下,技术转移服务公司如何利用数字化升级路径驱动精细化管理效能?.docx
- 在当前经济形势下,科技服务合作伙伴如何利用AI知识产权解决方案增强产品服务差异化?.docx
- 在人工智能+时代,地方管理部门如何利用AI+数智服务重塑区域创新环境?.docx
- 在人工智能+时代,地方管理部门如何借助体系化的AI知识产权解决方案解决信息不对称壁垒,从而驱动服务升级,最终驱动实现弯道超车?.docx
- 在人工智能+时代,科技管理部门如何借助个性化的AI+数智服务解决收入增长乏力,以增强精细化管理效能,最终增强实现弯道超车?.docx
- 在人工智能+时代,市场化技术转移机构如何借助个性化的新一代技术转移SaaS系统解决需求挖掘不精准,从而挖掘服务价值,最终挖掘实现弯道超车?.docx
- 在数字化转型大背景下,科研院所如何利用AI赋能的科技管理服务激活降本增效?.docx
- 政府部门如何借助_智改数转_一体化服务激活产业升级?.docx
- 政府部门如何借助_智改数转_一体化服务突破收入增长乏力,以打造创新的市场占有率?.docx
- 政府部门如何借助AI+数智服务突破平台_建而无用_,并打造一站式的体系化核心优势?.docx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈



安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功