acm程序设计大赛

《acm程序设计大赛》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9届南京大学ACM程序设计大赛9thNanjingUniversityACMLocalProgrammingContest试题册2011-05-07第9届南京大学ACM程序设计大赛A.打饭问题描述一天中午，星星来到了食堂吃午饭，如往常一样，食堂里已经排起了长长的队伍。然而今天有一个很奇特的现象，队伍中的同学全都是星星的好朋友。众所周知，食堂的饭菜是很折磨人的，以至于星星只对某几种菜感兴趣。为了能打到自己感兴趣的菜，星星只好采取一种邪恶的方案——插队。虽然星星的朋友都很乐意让星星插队到他们前面以便和星星一起探讨“学术”问题，但是星星还是不想影响到太多的同学。星星通过某

2、种神奇的方式得知了队伍中每个同学对每种菜的需求量，以及食堂中每种菜剩余的量。星星告诉你他对每种饭菜的需求量，由于星星数学不好，希望你能编写一个程序告诉他在第几个同学前插队刚好能打到所需饭菜。输入格式第一行，两个整数：M;N。M表示今日食堂提供的饭菜的种类数，N表示队伍中一共有多少同学。第二行，M个整数，其中第j个数Aj表示星星到达食堂时第j种菜的剩余量。第三行，M个整数，其中第j个数Bj表示星星对第j种菜的需求量，Bj=0表示星星对第j种菜不感兴趣。接下来N行，每行M个整数，第i(1iN)行第j(1jM)个数Cij，表示队伍中第i个同学对第j种菜的需求量。其中

3、1N100;1M10;0Aj;Bj;Cij100。输出格式一个整数i，表示星星插队在第i个同学之前恰好能打到所需的菜。若星星无论如何都无法打到所需的菜，输出-1，若无需插队就能打到所需的菜，输出N+1。样例输入23101055237822样例输出2提示每位同学打菜时，即使第j种菜剩余量不足他所需时，也会打走剩余的所有第j种菜，然而星星是希望轮到他的时候，他感兴趣的菜都剩余足够的份量。1第9届南京大学ACM程序设计大赛B.X问题描述“说感觉不只嗅觉还有味觉有触觉听觉到体会都是误会偶而约会却没有感觉……”有一天，星星正在听林俊杰的“X”，突然灵光一现，发现X是

4、一个十分有意思的字母。星星在X的左上，右上，左下，右下四个方向上画上X，得到了如下的图形：XXXXX它仍然是X形的，星星狂热地迷恋一切X形和星形的东西。于是星星又干了如下的事情：星星继续在上图的左上，右上，左下，右下四个方向上重复同样的图形，得到如下的图形：XXXXXXXXXXXXXXXXXXXXXXXXX星星将刚才得到的图形编号为2，并将之前得到的图形编号为1，将一个“X”编号为0。星星继续在图形2的左上，右上，左下，右下四个方向上重复图形2，得到了图形3；紧接着星星又依次得到了图形4，图形5。可是当画到图形5的时候，星星的纸已经被画得满满的了。被逼无奈，星星只好求

5、助于你，你能写一个程序来帮助星星得到他想要的图形么？输入格式若干行，每行一个整数i(i7)，以1结束。输出格式对于每一个输入i，输出编号为i的图形，每个图形后面输出一空行。每行后面多余的空格不要输出。2第9届南京大学ACM程序设计大赛样例输入01-1样例输出XXXXXX提示每行后面多余的空格不要输出。3第9届南京大学ACM程序设计大赛C.星形面积问题描述上题说到，星星狂热地迷恋一切X形和星形的东西。星星希望得到自己所喜欢的星形的一切数据，包括面积。请你编写一个程序帮星星计算N角星的面积。输入格式第一行：一个整数N(5N20)。第2N+1行：每行两个实数Xi;

6、Yi，表示N角星的第i个角顶点的坐标。N个顶点按顺时针方向给出。输出格式一个实数，所给出N角星的面积，结果保留2位小数。样例输入60.000002.000001.732051.000001.73205-1.000000.00000-2.00000-1.73205-1.00000-1.732051.00000样例输出6.93提示所谓N角星，是题中所给N个顶点，第i个顶点与第(i+2)%N个顶点相连接围成的图形，例如样例中给出的是一个六角星：4第9届南京大学ACM程序设计大赛D.瓶子问题描述星星去火星旅行，但是准备回地球的时候，他发现飞船的燃料不够了。于是星星去向火星人借

7、燃料，火星人答应了，要求星星用飞船上的瓶子来交换。星星的飞船上共有N个瓶子(1N1;000)，经过协商，火星人只要其中的K个(1KN)。星星将K个瓶子交给火星人之后，火星人用他们装一些燃料给星星。所有的瓶子都没有刻度，只是在瓶口标注了容量，第i个瓶子的容量为vi（vi为整数，并满足1vi1;000;000;000）。火星人比较吝啬，他们并不会把所有的瓶子都装满燃料。他们拿到瓶子后，会跑到燃料库里鼓捣一通，弄出一小点燃料来交差。星星当然知道他们会来这一手，于是事先了解了火星人鼓捣的具体内容。火星人在燃料库里只会做如下的3种操作：•将某个瓶子