|
浙大三位获国际大学生程序设计竞赛全球总冠军 ，回来了！
 他们被称作全世界最聪明的人
6月1日，快报报道了浙江大学三位学生获得第35届ACM国际大学生程序设计竞赛全球总决赛冠军的消息。前几天三位学生回到了浙大。这段时间他们是浙大的名人。昨天，他们接受了快报采访，讲述夺得程序设计竞赛冠军的故事。 全球大学生计算机竞赛由ACM（美国计算机协会）主办，有30多年历史，这些年一直由IBM赞助，夺冠难度相当大。大赛是分赛区的，全球共有88个国家的2070个大学组成8305支队伍，进总决赛的是30多个国家和地区的105支队伍。大赛像世界杯一样，之前先要预赛，像麻省理工大学和哈佛大学分在同一个赛区，哈佛就被麻省PK下去了。麻省理工大学本次大赛最后排名是第27位。 这是世界上最顶尖的大学生国际级计算机类赛事，被称为“计算机领域奥林匹克竞赛”。 大赛举行30多年来，除了浙大今年获得本届比赛冠军，整个亚洲只有上海交通大学，在2002年、2005年、2010年获得过三次全球总决赛冠军。三位同学的获奖，对浙江来说是零的突破。 计算机比赛是这么进行的 解决一道题升一个气球 第35届程序设计大赛原本设在埃及，因为埃及政局不稳，比赛地点临时改在了美国佛罗里达州城市奥兰多。 在全球计算机大赛中，各大学组团参赛，每支队伍由3位队员组成。整个团队只能使用1台电脑，要在5个小时内用C、C++或Java中的任意一种程序语言编写程序，解决11个问题。正确解答题目最多并且用时最少的队获胜。 竞赛队教练，是浙大计算机学院的王灿老师。他说，在编程大赛现场，解决一个问题，主办方便会发给团队一个气球。在现场，当你看到别的团队的气球升起来时，压力是很大的。这次比赛共耗时5小时，在前4个小时，你还可以看到各队伍解决了多少问题，排名第几。而在最后一个小时，美国的主办方为了增加悬念，封存了排行榜。在封存前，清华排第一，浙大排第四。在最后一小时内，浙大队伍一举解决了两个问题，实现反超，赢得第一，当时非常激动。 浙江大学计算机学院副院长陈越教授，曾是带队老师。陈越说，比赛当天主办方是全球直播的，当时是国内的晚上，浙大有很多学生在网站上看大赛直播，大家都很兴奋。 陈越说，程序设计是计算机领域的基础，和你我的生活都有关。最简单的理解就是：所有计算机都离不开程序设计，而现在有多少人的生活和计算机没有关系呢？ 比赛题目很多是生活中的实际问题 昨天，3位获奖队员回忆了一些比赛题： 能吸引越多顾客的地方，地价越高。对于热爱咖啡的人来说，他们不愿意走太远的路去享受咖啡。现在给定这些咖啡爱好者的位置，以及他们能容忍的步行距离，房地产商希望知道能吸引最多咖啡爱好者的地点是哪里，以便修建咖啡厅，吸引人过来。 给定一些采矿点，以及采矿点间通道，矿主可以在某些采矿点上设立救生通道，但矿主为了降低成本，希望通过设立最少的救生通道，使得假如有一个矿及其直接相连的通道坍塌了，其余采矿点的矿工仍能到达救生通道，确保人身安全。 地铁站间的运行时间表通常都是精确到分钟的，而实际上运行时间不全都是整分钟的，现在给定地铁站之间的真实运行时间，要求给出相应的运行时间表（通过向上或向下取证，精确到整分钟），使得运行时间表与真实运行时间之间相差总和最小。 容量越大的粉碎机造价越贵，给定报废机器的外形（多边形），求粉碎机的最小宽度，使得报废机器能够竖直放入粉碎机中。 给你一些山川的地形，假设外围被大海包围，在下大暴雨后，会形成多少个湖，并给出每个湖的深度。 这些题的解题思路及过程，对于计算机外行来说，是很难理解的。欧阳嘉林为我们介绍了“粉碎机”这道题的大致解题思路。 要使得粉碎机的宽度最小，废弃机器（多边形）的两个顶点一定是同时紧贴粉碎机内壁的。有了这个大胆的假设，只要选定两个顶点，首先判断整个多边形是否在这两个顶点连线的同一侧，然后求出离两点连线最远顶点的距离。这就是选定两个顶点紧贴粉碎机内侧时，粉碎机的最小宽度。 所以，只要枚举所有合法的顶点组合，求出所有最大距离中的最小值即可。 陈越教授说，参加这项比赛，考验学生的多项能力，首先是编程能力，在这方面，三个孩子已经是世界级的优秀程序员。其次是算法分析能力，即在最短时间找到最快解决问题的能力。最后还考验学生的团队合作能力。浙大的三个学生认识多年，已经有了默契，几乎每题都是两人合作完成，而有些队每个选手都很强，但只是单打独斗。 这次比赛，三位同学共获得了12000美元的奖金。昨天，他们都说要继续读书，打算以后从事学术工作。 |
|
|
