• godoyoyo
  • Others
  • 98KB
  • rar
  • 0
  • 1 积分
  • 38
  • 2005-08-04 17:15
  • www.pudn.com.txt
  • 2004ACM国际大学生程序设计决赛题目.pdf
<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&#8217;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&#8217;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&#8217;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&#8217;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&#8217;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">, &#8230; <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>
    • ACM.rar
    • acm.zip
    • ACM竞赛题目和源代码
    • acm.rar
    • ACM.rar
    • acm模板
    • ACM
      ACM 使用guide.py更快地复制模板文件 测试框架 可以考虑使用CUnit来测试C代码(由于CxxTest是为C ++设计的,因此无法测试每个C程序),但是,对于简单程序而言,CUnit似乎太大了 因此,我们现在考虑使用CuTest ...
    • acm模板.zip
    • f_acm.zip
      基于Linux 4.0 内核下的USB acm 驱动, 可供参考
    • acm.rar
      acm 竞赛的一些基础算法练习题 包括搜索、数论、几何、模拟等