注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

2010NOI团体对抗赛:FourColors  

2010-07-19 18:14:43|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

第二十七届全国信息学奥林匹克竞赛

NOI 2010

团体对抗赛

竞赛时间:201085日上午8:00-12:00

题目名称

四色地图

英文名称

fourcolours

输入

标准输入

输出

标准输出

每步输出时限

1

是否有部分分

题目类型

交互


提交源程序须加后缀

对于Pascal语言

fourcolours.pas

对于C/C++语言

fourcolours.cpp


注意:最终测试时,所有编译命令均不打开任何优化开关。


四色地图

【问题描述】

四色定理是一个著名的主要由计算机证明的理论。它指出,每幅地图都可以用四种颜色染色,使得相邻的区域染上不同的颜色。

小凡是一个有趣的小朋友,对于四色定理,她有着自己独特的理解和想法。在六一儿童节前夕的一个阳光和煦、微风轻拂的日子里,她发现了一个与四色地图相关的小游戏,兴奋不已,于是迫不及待地邀请小诚与她一起玩。

四色地图游戏是一个双人游戏。有四支颜色为ABCD的画笔,先手拥有AC,后手拥有BD。他们在一张空白的地图上,按照A -> B -> C -> D -> A -> B -> C -> D -> ……的次序使用画笔染色。轮到某支画笔染色时,必须保证所染区域与相邻区域不同色。如果不存在可染色的区域,则应当搁置这支画笔;如果存在可染色的区域,则可以选择其中之一染色,也可以搁置画笔。一支画笔一旦被搁置后将不能再次启用,即之后轮到它时,也必须搁置。如果在某一步之后,所有的画笔都已搁置,则游戏结束。地图上的每个区域都有一定的面积,游戏的目标是让己方染色区域面积之和尽可能大。

小诚玩了几局后,感到很有意思,就把这个游戏推荐给了他的好朋友小峰和小戈。但是,他们玩了以后却直呼不够过瘾,用期待的眼神企盼着小诚想出更有趣的游戏。

六月一日是属于儿童的节日,而这一天,也同时激发起了小诚富有童趣的灵感。他想到,真实的地图上有些区域是陆地,有些区域是海洋,有些区域是山峰。而用一支画笔为一块陆地染色,就像用一支军队占领了一个国家。紧接着,以下规则顿时从他的脑海中涌现出来:

  1. 海洋的归属,取决于与之相邻的陆地区域中,哪个玩家占领的块数更多。较多的一方可占其为领海。如果两个玩家占领的块数一样多,或者它周围没有陆地区域被占领,则这块海洋区域为公海。

  2. 山峰易攻难守,因而它的归属,取决于与之相邻的陆地区域中,最后被占领的那一块属于哪个玩家。该玩家可占其为领山。如果它周围没有陆地区域被占领,则这块山峰区域为荒山。

下面的表格梳理了每种类型的区域各种状态的称谓:

区域状态

区域类型

无人占领

玩家甲占领

玩家乙占领

陆地

空地

甲的领地

乙的领地

海洋

公海

甲的领海

乙的领海

山峰

荒山

甲的领山

乙的领山

海洋区域和山峰区域都是不能被染色的。游戏结束的条件,仍为四支画笔均被搁置。而如今游戏的目标,是让己方的领地、领海和领山的面积之和尽可能大。

【数据规模和约定

陆地区域共有U2 U 60U为偶数)块,编号依次为1…U;海洋区域共有V1 V 10)块,编号依次为U+1…U+V;山峰区域共有W1 W 10)块,编号依次为U+V+1…U+V+W

地图将在一定的约束条件下随机生成。这些约束条件包括:每个区域的面积都是不超过1000的正整数;每块陆地区域面积的数学期望值相同;每块海洋区域和山峰区域面积的数学期望值也相同,均为一块陆地区域面积的数学期望值的2倍。

【输入、输出格式】

输入的第一行包含4个整数UVWF。其中UVW分别表示陆地、海洋、山峰区域的块数;F表示先后手信息,1为先手,2为后手。接着输入U+V+W行,其中的第i行包含了编号为i的区域的信息,依次为该区域的面积Si、与之相邻的区域块数Ni,以及这Ni块区域的编号。以上每行输入的每两个数之间用一个空格分隔。输入保证存在这样的平面地图。

接下来的部分中的奇数行为输入,偶数行为输出。每行输入代表对方的一步,包括一个整数,表示对方染色区域的编号,如果是0,则表示对方搁置画笔。对于先手而言,第一行输入为一个单独的整数0,没有意义,可以忽略。

每行输出代表己方的一步,包括一个整数,即己方染色的区域编号,如果搁置画笔,则输出0。输出每一行之后必须刷新缓冲区(flush)。当己方的两支画笔均已搁置,即对两支画笔均输出过0之后,程序应当结束。

当对方的两支画笔均已搁置,但己方的程序还未结束时,将仍然保持交替的输入与输出,只不过每行输入均为一个单独的整数0

【输入、输出样例】

行数

输入

输出

画笔

己方领地、领海、领山编号

对方领地、领海、领山编号

1

6 2 2 1





2

10 3 7 3 4





3

10 3 7 5 9





4

10 3 1 4 10





5

10 6 1 7 3 5 10 8





6

10 6 7 2 4 9 8 6





7

10 3 5 9 8





8

15 4 1 2 4 5





9

25 4 4 5 10 6





10

30 3 2 5 6





11

25 3 3 4 8





12

0





13


4

A

4, 7, 8, 10

NULL

14

5


B

4, 10

5, 9

15


1

C

1, 4, 7, 10

5, 9

16

6


D

1, 4, 7, 10

5, 6, 8, 9

17


2

A

1, 2, 4, 7, 9, 10

5, 6, 8

18

3


B

1, 2, 4, 7, 9

3, 5, 6, 8, 10

19


0

C

1, 2, 4, 7, 9

3, 5, 6, 8, 10

20

0


D

1, 2, 4, 7, 9

3, 5, 6, 8, 10

21


0

A

1, 2, 4, 7, 9

3, 5, 6, 8, 10

己方程序结束

【样例说明】

样例中的地图如下所示:

陆地区域1

海洋区域7

陆地区域2

陆地区域3

陆地区域4

陆地区域5

山峰区域9

山峰区域10

海洋区域8

陆地区域6

【评分方法】

如果你的程序每次都在时限内给出了合法的输出,直至两支画笔均被你搁置之后正常结束,则你的得分即为你所占的领地、领海和领山的面积之和。在样例中,己方的得分为75分。

如果你的程序崩溃、超时、输出非法,或者意外退出,那么系统将终止你的程序,但不会结束游戏,而是代替你继续游戏。系统的策略是,在之后的每一步都替你搁置画笔,直至游戏结束。你的得分是游戏结束后所占的领地、领海和领山的面积之和。


  评论这张
 
阅读(1786)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017