<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8">
<meta name="generator" content="pdf2htmlEX">
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css">
<link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css">
<link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/622b2edcff7f9c46a68aa17f/raw.css">
<script src="https://static.pudn.com/base/js/compatibility.min.js"></script>
<script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script>
<script>
try{
pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({});
}catch(e){}
</script>
<title></title>
</head>
<body>
<div id="sidebar" style="display: none">
<div id="outline">
</div>
</div>
<div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/622b2edcff7f9c46a68aa17f/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">The 2004 28</div><div class="t m0 x2 h2 y2 ff1 fs0 fc0 sc0 ls1 ws1">th</div><div class="t m0 x3 h3 y1 ff1 fs0 fc0 sc0 ls2 ws2"> Annual<span class="fs1 ls3 ws3"> <span class="ff2 ls4 ws1">acm</span> </span><span class="ls5 ws4">International Collegiate<span class="fs2 ls3 ws5"> </span></span></div><div class="t m0 x4 h4 y3 ff2 fs3 fc0 sc0 ls6 ws1">Programmin<span class="_ _0"></span><span class="ls7 ws6">g Contest World Finals<span class="_ _1"></span><span class="ff1 ls3 ws7"> </span></span></div><div class="t m0 x5 h4 y4 ff2 fs4 fc0 sc0 ls8 ws8">sponsored by <span class="_ _2"></span><span class="fs3 ls9 ws1">IBM<span class="ls3 ws7"> </span></span></div><div class="t m0 x6 h5 y5 ff3 fs2 fc0 sc0 ls3 ws9"> </div><div class="t m0 x6 h5 y6 ff3 fs2 fc0 sc0 ls3 ws9"> </div><div class="t m0 x7 h6 y7 ff1 fs5 fc0 sc0 lsa wsa">Problem A<span class="_ _3"></span><span class="ls3 wsb"> </span></div><div class="t m0 x8 h7 y8 ff1 fs3 fc0 sc0 lsb wsc">Carl the Ant<span class="_ _3"></span><span class="ls3 ws7"> </span></div><div class="t m0 x9 h8 y9 ff1 fs4 fc0 sc0 lsc wsd">Input File: carl.in<span class="ls3 wse"> </span></div><div class="t m0 x6 h5 ya ff3 fs2 fc0 sc0 lsd wsf">Ants leave small chemical trails on the ground in order to mark paths for other ants to follow. Ordinarily these </div><div class="t m0 x6 h5 yb ff3 fs2 fc0 sc0 lse ws10">trails follow rather straight lines. But in one ant colony there is an ant named Carl, and Carl is n<span class="_ _2"></span><span class="lsf ws11">ot an ordinary </span></div><div class="t m0 x6 h5 yc ff3 fs2 fc0 sc0 ls10 ws12">ant. Carl will often zigzag for no apparent reason, sometimes crossing his own path numerous times in the </div><div class="t m0 x6 h5 yd ff3 fs2 fc0 sc0 ls11 ws13">process. When other ants come to an intersection, they always follow the path with the strongest scent, which is </div><div class="t m0 x6 h5 ye ff3 fs2 fc0 sc0 ls12 ws14">the most recent path t<span class="_ _4"> </span><span class="ls13 ws15">hat leads away from the intersection point.<span class="_ _2"></span><span class="ls3 ws9"> </span></span></div><div class="t m0 x6 h5 yf ff3 fs2 fc0 sc0 ls14 ws16">Ants are 1 centimeter long, move <span class="_ _0"></span><span class="ls15 ws17">and burrow <span class="_ _0"></span><span class="ls16 ws18">at 1 centimeter per second, and follow their path<span class="_ _3"></span><span class="ls17 ws1">s<span class="_ _2"></span><span class="ls18 ws19"> exactly (bending </span></span></span></span></div><div class="t m0 x6 h5 y10 ff3 fs2 fc0 sc0 ls19 ws1a">at right angles when moving around corners). Ants cannot cross or overlap each other. If two ants me<span class="_ _2"></span><span class="ls1a ws1b">et at the </span></div><div class="t m0 x6 h5 y11 ff3 fs2 fc0 sc0 ls1b ws1c">exact same instant at an intersection point, the one that has been on Carl’s path the longest has <span class="_ _2"></span><span class="ls1c ws1d">the <span class="_ _0"></span><span class="ls1d ws1e">right of way; </span></span></div><div class="t m0 x6 h5 y12 ff3 fs2 fc0 sc0 ls1e ws1f">otherwise, the ant that has been waiting the longest at an intersection will move first.<span class="_ _2"></span><span class="ls3 ws9"> </span></div><div class="t m0 x6 h5 y13 ff3 fs2 fc0 sc0 ls1f ws20">Carl burrows up from the ground to start <span class="_ _2"></span><span class="ls20 ws21">at the origin at time 0. He then walks his path and burrows back down </span></div><div class="t m0 x6 h5 y14 ff3 fs2 fc0 sc0 ls21 ws22">into the ground at the endpoint. The rest of the ants follow at regular intervals. Given the description of Carl’s </div><div class="t m0 x6 h5 y15 ff3 fs2 fc0 sc0 ls22 ws23">path and <span class="_ _0"></span><span class="ls23 ws1">when<span class="_ _3"></span><span class="ls24 ws24"> the other ants start the path, you are to determine how l<span class="_ _0"></span><span class="ls25 ws25">ong it takes the entire set of ants to <span class="_ _2"></span><span class="ls26 ws26">finish </span></span></span></span></div><div class="t m0 x6 h5 y16 ff3 fs2 fc0 sc0 ls27 ws1">burrowing<span class="_ _2"></span><span class="ls28 ws27"> back into the ground. All the ants are guaranteed to finish.<span class="_ _0"></span><span class="ls3 ws9"> </span></span></div><div class="t m0 x6 h5 y17 ff3 fs2 fc0 sc0 ls3 ws9"> </div><div class="t m0 x6 h9 y18 ff2 fs6 fc0 sc0 ls29 ws1">Input<span class="ls3 ws28"> </span></div><div class="t m0 x6 h5 y19 ff3 fs2 fc0 sc0 ls2a ws29">Input consists of several test cases. The first line of the input file contains a single integer indicating the number </div><div class="t m0 x6 h5 y1a ff3 fs2 fc0 sc0 ls2b ws2a">of test cases<span class="_ _1"> </span><span class="ls2c ws1">.<span class="ls3 ws9"> </span></span></div><div class="t m0 x6 h5 y1b ff3 fs2 fc0 sc0 ls2d ws2b">The input for each test case starts with a single line containing three positive integers <span class="_ _2"></span><span class="ff4 ls2e ws1">n<span class="ls3 ws9"> </span><span class="ff3 ls2f">(1<span class="_ _3"></span><span class="ls3 ws9"> <span class="_ _0"></span><span class="ls30 ws1">=</span><span class="ff4"> <span class="ls2e ws1">n</span> </span><span class="ls30 ws1">=</span> <span class="ls31 ws1">50),<span class="_ _2"></span><span class="ff4 ls3 ws9"> </span></span></span></span></span></div><div class="t m0 x6 h5 y1c ff4 fs2 fc0 sc0 ls32 ws1">m<span class="ff3 ls3 ws9"> <span class="ls33 ws1">(1</span> <span class="ls30 ws1">=</span><span class="ff4"> </span></span>m<span class="ls3 ws9"> </span><span class="ff3 ls30">=<span class="ls3 ws9"> <span class="ls34 ws2c">100), and <span class="_ _0"></span></span></span></span><span class="ls2e">d<span class="_ _2"></span><span class="ls3 ws9"> <span class="_ _0"></span><span class="ff3 ls2f ws1">(1<span class="_ _2"></span><span class="ls3 ws9"> <span class="_ _2"></span><span class="ls30 ws1">=<span class="_ _0"></span><span class="ff4 ls3 ws9"> <span class="ls2e ws1">d</span> </span>=<span class="ls3 ws9"> </span><span class="ls35">100)<span class="ff4 ls2c">. <span class="_ _2"></span><span class="ff3 ls36">Here,<span class="_ _2"></span><span class="ff4 ls2e ws2d"> n<span class="ff3 ls37 ws2e"> is the number of line segments in Carl’s path, <span class="_ _2"></span><span class="ff4 ls32 ws1">m<span class="_ _0"></span><span class="ff3 ls38 ws2f"> is the number of </span></span></span></span></span></span></span></span></span></span></span></span></div><div class="t m0 x6 h5 y1d ff3 fs2 fc0 sc0 ls39 ws30">ants traveling the path (including C<span class="ls3a ws31">arl), and <span class="ff4 ls2e ws1">d</span><span class="ls3b ws32"> is the time delay before each successive ant’s emergence. Carl </span></span></div><div class="t m0 x6 h5 y1e ff3 fs2 fc0 sc0 ls3c ws33">(who is numbered 0) starts at time 0. The next ant (ant number 1) will emerge at time <span class="ff4 ls3d ws1">d,<span class="_ _0"></span></span><span class="ls2d ws34"> the next at time 2<span class="_ _0"></span><span class="ff4 ls3e ws1">d,<span class="_"> </span></span><span class="ls3f ws35"> and </span></span></div><div class="t m0 x6 h5 y1f ff3 fs2 fc0 sc0 ls26 ws36">so on. If the burrow is blocked, the ants will emerge as soon as po<span class="ls40 ws37">ssible in the correct order.<span class="_ _2"></span><span class="ls3 ws9"> </span></span></div><div class="t m0 x6 h5 y20 ff3 fs2 fc0 sc0 lse ws38">Each of the next <span class="_ _2"></span><span class="ff4 ls2e ws1">n<span class="ff3 ls41 ws39"> lines for the test case consists of a unique integer pair <span class="_ _0"></span></span><span class="ls42 ws3a">x y<span class="_ _2"></span><span class="ff3 ls43 ws3b"> (<span class="_ _3"></span><span class="ls44 ws1">-<span class="_ _0"></span><span class="ls45">100<span class="_ _4"> </span><span class="ls3 ws9"> </span><span class="ls30">=<span class="_ _2"></span><span class="ff4 ls3 ws9"> <span class="_ _0"></span><span class="ls46 ws1">x,<span class="_ _3"></span><span class="ls3 ws9"> <span class="_ _0"></span><span class="ls42 ws1">y</span> <span class="_ _0"></span><span class="ff3 ls30 ws1">=<span class="_ _2"></span><span class="ls3 ws9"> <span class="_ _0"></span><span class="ls47 ws3c">100), which is the </span></span></span></span></span></span></span></span></span></span></span></span></div><div class="t m0 x6 h5 y21 ff3 fs2 fc0 sc0 ls48 ws3d">endpoint of a line segment of Carl’s path, in the order that Carl travels. The first line starts at the origin (0,0) and </div><div class="t m0 x6 h5 y22 ff3 fs2 fc0 sc0 ls49 ws3e">the starting point of every <span class="ls4a ws1">subsequent<span class="_ _0"></span><span class="ls4b ws3f"> line is the endpoint of the previous line.<span class="ls3 ws9"> </span></span></span></div><div class="t m0 x6 h5 y23 ff3 fs2 fc0 sc0 ls4c ws40">For simplicity, Carl alwa<span class="_ _2"></span><span class="ls4d ws41">ys travels on line segments parall<span class="ls4e ws42">el to the axes, and no endpoints<span class="_ _0"></span><span class="ls4f ws43"> lie on any segment </span></span></span></div><div class="t m0 x6 h5 y24 ff3 fs2 fc0 sc0 ls50 ws44">other than the ones which they serve as an endpoint.<span class="_ _2"></span><span class="ls3 ws9"> </span></div><div class="t m0 x6 h5 y25 ff3 fs2 fc0 sc0 ls3 ws9"> </div><div class="t m0 x6 h9 y26 ff2 fs6 fc0 sc0 ls51 ws1">Output<span class="ls3 ws28"> </span></div><div class="t m0 x6 h5 y27 ff3 fs2 fc0 sc0 ls52 ws45">The output for each case is described as follows:<span class="_ _2"></span><span class="ls3 ws9"> </span></div><div class="t m0 x6 h5 y28 ff3 fs2 fc0 sc0 ls3 ws9"> </div><div class="t m0 x6 ha y29 ff5 fs2 fc0 sc0 ls53 ws46">Case C:<span class="_ _0"></span><span class="ls3 ws47"> </span></div><div class="t m0 x6 ha y2a ff5 fs2 fc0 sc0 ls54 ws48">Carl finished the path at time t1<span class="_ _0"></span><span class="ls3 ws47"> </span></div><div class="t m0 x6 ha y2b ff5 fs2 fc0 sc0 ls55 ws49">The ants finishe<span class="_ _2"></span><span class="ls56 ws4a">d in the following order:<span class="_ _0"></span><span class="ls3 ws47"> </span></span></div><div class="t m0 x6 ha y2c ff5 fs2 fc0 sc0 ls57 ws4b">a1 a2 a3 ... am<span class="_ _0"></span><span class="ls3 ws47"> </span></div><div class="t m0 x6 ha y2d ff5 fs2 fc0 sc0 ls58 ws4c">The last ant finished the path at time t2<span class="_ _0"></span><span class="ls3 ws47"> </span></div><div class="t m0 x6 h5 y2e ff3 fs2 fc0 sc0 ls59 ws4d">Here, <span class="_ _2"></span><span class="ff5 ls5a ws1">C<span class="_ _0"></span><span class="ff3 ls5b ws4e"> is the case number (starting at 1), <span class="_ _2"></span><span class="ff5 ls5c ws1">a1<span class="_ _2"></span><span class="ff3 ls2c">,<span class="ff5 ls5c ws4f"> a2<span class="_ _2"></span><span class="ff3 ls2c ws1">,<span class="ff5 ls5a ws50"> a3<span class="_ _4"> </span></span><span class="ls5d ws51">, … <span class="_ _2"></span><span class="ff5 ls5c ws1">am<span class="_ _2"></span><span class="ff3 ls5e ws52"> are the ant numbers in the order that they go </span></span></span></span></span></span></span></span></span></div><div class="t m0 x6 h5 y2f ff3 fs2 fc0 sc0 ls5f ws53">back underground, and <span class="_ _0"></span><span class="ff5 ls5c ws1">t1<span class="_ _2"></span><span class="ff3 ls3f ws54"> and <span class="ff5 ls5a ws1">t2<span class="_ _0"></span></span><span class="ls60 ws55"> are the times (in seconds) at whi<span class="ls61 ws56">ch Carl and the last ant finish going </span></span></span></span></div><div class="t m0 x6 h5 y30 ff3 fs2 fc0 sc0 ls62 ws1">underground.<span class="_ _0"></span><span class="ls3 ws9"> <span class="_ _2"></span><span class="ls63 ws57">You should separate consecutive cases with a single blank line.<span class="ls3 ws9"> </span></span></span></div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>
</body>
</html>
2004ACM国际大学生程序设计决赛题目.rar
- godoyoyo了解作者
- Others开发工具
- 98KB文件大小
- rar文件格式
- 0收藏次数
- 1 积分下载积分
- 38下载次数
- 2005-08-04 17:15上传日期
2004ACM国际大学生程序设计决赛题目
2004ACM国际大学生程序设计决赛题目.rar
- www.pudn.com.txt218B
- 2004ACM国际大学生程序设计决赛题目.pdf123.6KB
内容介绍
评论
相关推荐
- ACM.rar有关ACM的电子书，是斯坦福大学的ACM教程，很好的东西
- acm.zipjava源acm包适合编写小程序。非常棒的。可以给大家带来很多的好处
- ACM竞赛题目和源代码计算机ACM程序设计竞赛题目和源程序代码
- acm.rar杭电ACM测试用的题目，2000，正确通过。希望对你们有用。
- ACM.rarACM程序设计导引及上机实践，很适合对ACM有兴趣，刚接触ACM的朋友
- acm模板acm竞赛模板，适合acm竞赛以及准备蓝桥杯，PAT，CCF的同学备战使用
- ACMACM 使用guide.py更快地复制模板文件 测试框架 可以考虑使用CUnit来测试C代码（由于CxxTest是为C ++设计的，因此无法测试每个C程序），但是，对于简单程序而言，CUnit似乎太大了 因此，我们现在考虑使用CuTest ...
- acm模板.zipacm的模板，供acmer使用，各种算法的实现都有
- f_acm.zip基于Linux 4.0 内核下的USB acm 驱动， 可供参考
- acm.raracm 竞赛的一些基础算法练习题 包括搜索、数论、几何、模拟等
最新资源