[活动] 第四届CFAN编程挑战赛—算法类[比赛已经结束]

活动资料

比赛结束, 在此可查看所有提交邮件


2008CFan论坛编程大奖赛


比赛细则


(算法类)



-------------------------------------------------------------------------------------------------------------------


一、 竞赛要求

引用:

  利用任意编程语言解决指定问题并给出正确格式的结果。


二、 组织形式

引用:

  所有Cfan注册会员(除承办人外)均可以个人名义报名参赛,选手在得到题目后便可以开始编写程序,在指定日期前完成作品。最后向组委会提交作品。
三、 时间
引用:

7月14日00:00到7月21日00:00为报名时间
7月21日00:00到7月26日00:00为比赛时间
四、 要求
引用:

1. 可选语言
本次比赛不限制使用语言的种类,但是有如下要求:
(1) 算法设计中,所使用语言必须能够在Windows平台运行。
(2) 算法设计中,使用语言应该能够提供控制台运行方法。算法设计只接受控制台应用程序
      ps:对于比较特殊的语言,比如Visual Basic 6 允许使用IDE自带的调试控制台或等价物

2. 时间与空间限制
运行时间各个测试点都不能超过2秒(JAVA不能超过4秒),空间不能超过128MB(JAVA不能超过256MB),不包括虚拟内存。

3. 其他要求
(1) 对于VB/VC/VF:不能调用任何dll文件,不能有窗体文件,只能有模块和相关的Sub Main,不能有Declare的相关声明。
(2) 对于.NET:只能生成控制台程序,只能调用Math类和System.IO类,不能调用其他的类或dll。
(3) Free Pascal可使用ansitring,Java语言可使用BigInteger。
(4) 其他语言请参照以上标准。
提交作品应当注明参赛者论坛ID及联系方式。参赛者应声明拥有作品全部的知识产权,没有抄袭或盗版行为。
五、 程序的测试
引用:
  测试采用黑盒形式。每题共有10组测试数据,每回答正确一组得10分,不正确得0分,累计得分即是本题的得分。程序测试都采用文件输入输出,请只输出题目要求的数据,不能输出其他任何数据。
六、 版权声明
引用:
  选手所提交的必须是自己完成的,拥有独立知识产权的软件系统。如果由于选手不正当使用他人代码所带来的版权问题,由选手自己负责。
  本次比赛所提交的作品默认使用GNU/GPL v2作为版权协议,如果作者有意见,请另行通知大赛组委会。否则组委会有权在比赛结束后将所有代码公开。
  无论参赛者使用何种版权协定,都必须向大赛组委会提供所提交的作品的可编译源代码,不提供源代码的按弃权处理。
七、 奖金及评定方式
引用:
算法类根据题目难度不同,分为ABC三类。奖金分别为:
种类
基本奖金(Cfan现金)
A
1000
B
3000
C
6000

  另外,根据不同选手的作品表现,可以给予一定限度的奖金加成,加成幅度不超过基本奖金的50%
八、 题目信息
引用:
作品提交方式:邮件提交
提交内容:源文件
,请不要发送可执行文件
作品提交邮箱地址是:cfan-coding-contest@googlegroups.com
A类题:

     1:天气炎热,兔子也想过个清凉的暑假,就去买啤酒1.5元钱一瓶啤酒,喝完后一个空瓶可以在GC(回收垃圾的)那里换0.5元,问:兔  子只有30元钱,最多能喝到几瓶啤酒?  


     2:由键盘输入N, A={1,2,...,N}为连续N个整数的集合, 取A中若干不同的整数, 使这些整数之和为给定的M, 共有多少种不同的取法?


      3:兔子特别爱吃肉,所以肉库有放了很多很多的肉(肉价疯长说不定可以成为固定资产),但是肉多了兔子就不记得肉食多久买回来的,所以兔子把肉按日期为100个编号,编号为0~99之间的数字,但是由于编号太多,兔子决定把同种编号的放到对应编号的柜子里面。例如编号是{1,4,4,5,3,5,7,7}变成编号{1,3,4,5,7}。


      4:北京喜迎2008年的奥运会,某熊也是很高兴的,但是现在有个难题在某熊面前,据说做不出来某熊不但不能看奥运会了,还要去收集AV 你能帮帮某熊吗 :                (2008个1)的(2008个1)次方 mod 2008 =?
mod: java/c/c++/python...中的%运算符



     5:{交互式题目,通过输入与输出流}
       在给定的区间猜一个整数
       程序开始运行时,我们将向stdin写入4个整数并使用系统默认的换行符换行
        min max sh sl#min=可能的最小整数 max=可能的最大整数 sh=获得满分的猜测次数 sl=获得0分的猜测次数
        当猜测时,向stdout写入一个整数(不夹杂任何字母/符号)并使用系统默认的换行符换行         
        我们将向stdin写入:
        gt #你猜的数过大
        lt #你猜的数过小
        并使用系统默认的换行符换行
        结束:1.猜中 2.次数超出sl 3.猜测时间超过0.01s
        评分:猜测次数x:
        x小于或等于sh:满分
        在之间:按线性函数计分,取到较大的整数
         x大于或等于sl:0分

6. unique
unique.in
<blockquote>一个或多个整数,每个均不大于2.1e9,不小于-2.1e9,以换行分隔,请忽略空行</blockquote>
unique.out
<blockquote>去除重复后的数字,顺序为每一个数字第一次出现时的顺序</blockquote>
sample
input
5
56
12
32
12
56
46
5

output
5
56
12
32
46

B类题:
       1:话说兔子一直怕人家找到了他的藏肉保险柜密码,所以兔子找了一种加密的方式,使用了某种密码古老的流行的一种采用座标系换字表的加密系统。采用字母表作为座标系统:   
A B C D E
F G H I/J K
L M N O P
Q R S T U
V W X Y Z
加密的方法是:
<1>. 把讯息分拆成一对对的字母,即字母对(digraphs)。而字母对内之字母必须不同,相同时则在中间插入x、z或q等(选其一)较少用的字母。如最後只剩一个字母,同样地,加入 x 等来组成字母对。  

<2>. 从表中可看出,所有字母对可分成三类:两个字母在同一行,两个字母在同一列,或前述情况皆非。

<3>. 对明文加密时,若两个字母都在同一行就各自用右边的字母代替,如果右边没字了,则用同行开头(即最左边)的字母代替。例如:lo变成MP,wz则变成XV。

<4>. 同样道理,对同一列的字母,则用其下方的字母取代,最底的则用同列最上方的字母取代。例如:gr变成MW,jy则变了OD。

<5>. 至于遇到第三种情况时,则用另一种加密方法:取字母对中第一个字母所在的行,及第二个字母所在的列,它们所交汇出的字母就用来加密第一个字母;加密第二个字时,则取字母对中第一个字母所在的栏,及第二个字母所在的行所交汇出的字母为替身。所以, mt 会变成 OR ,而 by 则变成DW。

如:明文 minimize cheese cake   
分解成字母对的明文 mi ni mi ze ch ex es ec ak ex   
密码文 OG OH OG EK HN CZ AD EF CZ   

现在需要兔子需要一套根据上面加密的原理所制作加密解密的程序你能帮助设计出来吗?


      2:将一个N*N方阵旋转四次,再回到原来的样子,过程如下(以N=3为例):
1 2 3
4 5 6
7 8 9
过程:
7 4 1
8 5 2
9 6 3

9 8 7
6 5 4
3 2 1

3 6 9
2 5 8
1 4 7

1 2 3
4 5 6
7 8 9

现要求编程模拟该过程。



      3:为了提高读取速度,我们引入了缓存系统缓存共有n级,每一级的容量有一定限制在存贮时,我们可以很清楚的知道,将来要对每份数据做多少次读取一份数据一旦被确定储存在什么位置就不能再变动,所有没有被存贮在缓存中的数据也可以被读取同一份数据必须存在于同一级缓存中,或全部不在缓存中
cache.in
m n tx#m份数据,n个缓存,读取没有被存贮在缓存中的每个容量单位数据需要时间tx
s1 t1#第一级缓存的大小和读取每个容量单位的时间,共n行
ms1 mr1#第一份数据的大小和它将被读取的次数
cache.out
t#所需最短读取时间  

4.
{你的程序将只对指定目录拥有读取权限}
请按要求对给定文件的内容进行统计
提示:数据可能较大,但最大不会超过1e200
请说明程序运行平台
在你的程序的工作目录下,将存在一个stat.in文件,
该文件的内容描述了你的程序需要对这一批文件作怎样的统计
你需要统计的文件将在工作目录中的stat子目录下,
要统计的文件的路径不包含stat/及之前的部分
统计结果输出到stat.out文件
stat.in的内容:
<blockquote>x #这意味着接下来有x组统计任务
# 一个空行,接下来为每组任务,每组之间用一个空行隔开
y #这意味着这组任务有y种文件要统计,以下将列出每种的要求
sp #这是一类文件的说明的第一行,当到任何一个文件的相对路径符合该字符串时该文件属于这一类,可能使用*和?通配符,请注意*ab*c*而非ab*c匹配dabxxc.txt文件
d #这是一个数字,意味着符合要求的文件的第几行将被统计。我们保证该行为数字,如果行数不够,该文件的统计结果为0
so #这是一类文件的说明的最后一行,它意味着这种文件中每个文件的统计结果将被怎样处理。sum要求求和,product要求求积,average要求求算术平均数
sgo #在每一类文件的要求列举完后,该字符串确定这组的结果将由其中每类的结果怎样计算。sum要求求和,product要求求积,average要求求算术平均数</blockquote>stat.out的内容:
<blockquote>依次列出每一组文件的统计结果</blockquote>


C类题:

      1.我下载了一些文件,需要把它刻录成光盘,为了尽量节省费用,我希望用尽量少的光盘数完成刻录,但不能分割或压缩文件。每张盘的容量完全相同。同时,出于方便考虑,我希望一些文件被放在同一张光盘上。
burn.in
c s #c=文件数, s=光盘容量, 以下共有c行
fn s r #fn=文件名(8.3格式) s=文件大小 r=必须在同一张光盘上的文件名(保证有此列,可能恰为本文件名)
burn.out
cc #最少需要的光盘数 如不可能完成 请输出-1


      2:A family of N people is passing a bridge at night. Since it is extremely dark, they walk with the help of a lamp. Unfortunitely the bridge is narrow, as a result a maximum of two people can cross at one time, and they must have the lamp with them. Each person walks at a different speed, and a pair must walk together at the rate of the slower person. Now here is the problem: given the size of the family (N) and the time needed for each person to cross the bridge, try to figure out the minimum total time that the family can cross the bridge.
Input

There are several test cases.

In each test case, there are 2 lines.

In the first line, an integer N will be given, which satisfies 0<=N<=100000. (Though a family of 100000 people is somewhat ridiculous.)

In the second line, N integers will be given, which are the time needed to cross the bridge for each person.

There are no extra line(s) between test cases.

Output

For each test case, output a line with one number, the minimum total time.

Sample Input

5
1 3 6 8 12

Sample Output

29

CFAN论坛及CFAN编程版管理层拥有此次比赛的最终解释权



[ 本帖最后由 Liangent 于 2008-8-4 12:15 编辑 ]

活动信息

活动类别 挑战赛
开始时间 2008-8-5 12:00
活动地点 中国CFAN论坛
每人花销 每人大约 10 元
性别 不限
征集截止日期 2008-7-21 00:00