题目名称 荒岛野人 新俄罗斯方块 机器人M号
目录 day2/savage day2/tetris day2/robot
可执行文件名 savage \ robot
输入文件名 savage.in tetris1.in~tetris10.in \ robot.in
输出文件名 savage.out tetris1.out~tetris10.out \ robot.out
是否有部分分 否 是 是
附加文件 无 game 无
时限 2秒 \ 2秒
题1
荒岛野人
【问题描述】
克里特岛以野人群居而著称。岛上有排列成环行的M个山洞。这些山洞顺时针编号为1,2,…,M。岛上住着N个野人,一开始依次住在山洞C1,C2,…,CN中,以后每年,第i个野人会沿顺时针向前走Pi个洞住下来。每个野人i有一个寿命
值Li,即生存的年数。下面四幅图描述了一个有6个山洞,住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为1,2,3;每年要走过的洞穴数依次为3,7,2;寿命值依次为4,3,1。
(图1~图4见附件)
奇怪的是,虽然野人有很多,但没有任何两个野人在有生之年处在同一个山洞中,使得小岛一直保持和平与宁静,这让科学家们很是惊奇。他们想知道,至少有多少个山洞,才能维持岛上的和平呢?
【输入文件】
输入文件savage.in的第1行为一个整数N(1<=N<=15),即野人的数目。第2
行到第N+1每行为三个整数Ci, Pi, Li (1<=Ci,Pi<=100, 0<=Li<=106 ),表示每个野
人所住的初始洞穴编号,每年走过的洞穴数及寿命值。
【输出文件】
输出文件savage.out 仅包含一个数M,即最少可能的山洞数。输入数据保证
有解,且M不大于10[sup]6[/sup]。
【样例输入】
3
1 3 4
2 7 3
3 2 1
【样例输出】
6
【样例说明】
该样例对应于题目描述中的例子。
题2 新俄罗斯方块
新俄罗斯方块
【问题描述】
圆圆玩腻了传统的“俄罗斯方块” 游戏,发明了一种新的玩法:游戏在一个无限高的N列棋盘中进行,棋盘的各列从左到右依次编号为1,2,…N。在游戏中,游戏者可以使用如图1所示的19种形状的基块,无论哪一种基块都是由四
个小方块连接起来的。图上标有基块形状编号T(1 <= T <= 19):(见附件)
棋局描述与游戏规则:
1.棋盘中棋局状态的描述:游戏中所有可能的棋局状态都用每列连在一起的小方块数来描述。例如图2的棋局,棋盘为4列,N = 4,第1列有3个小方块;第2列有2个小方块;第3列有3个小方块;第4列有0个小方块。因此,可以用(3, 2, 3, 0)来描述这一棋局。
2.游戏时先选基块T(1 <= T <= 19),再将它放到该放的列C(1 <= C <= N)上去,称之为指令(T, C),含意是,将形状编号为T的基块的最左边的小方块对准C列放下。比如对图2的棋局,选T = 1的基块,放至第4列,即指令(1, 4),基块可落下至底部,刚刚执行完指令(1, 4)之后的棋局为(3, 2, 3, 4),由于底部两行是占满的,游戏规则让占满的两行自动消失,得到的棋局为图3,可描述为(1, 0, 1, 2)。
3.当棋盘上每一列的小方块数都为0时游戏结束。比如在图3的棋局上,选择9号基块,让其最左边的小方块处于棋盘上的第1列,即指令(9, 1),从上往下落到底,则得棋局状态为(2, 2, 2, 2),占满两行,自动消失后得(0, 0, 0, 0),
游戏成功结束。
4.游戏规定在放每一个基块时都不允许越出棋盘边界。比如图2,N = 4,指令(18, 4)会越界。
5.游戏还规定不允许出现“悬空”的小方块。“悬空”的含意是,在同一列上,所有小方块没有连在一起。比如图5属于这种情况。在图2的棋局下,指令(2, 1),(17, 2),(10, 3)是非法的。
(见附件)
虽然任意选择形状会让游戏容易许多,可要把方块弄得一块也不剩仍然是件很头疼的事情。你愿意试试吗?现在把“新俄罗斯方块”这个游戏程序交给你。
该程序可以读入你的(T,C)指令,告诉你指令完成后的棋局状态。
【输入文件】
输入文件 tetris1.in 到tetris10.in 已经放在用户目录中,文件第一行包含一个整数N,即棋盘的列数,第二行包含N 个整数,分别表示各列包含的连在一起的小方块数。
【输出文件】
本题是一道提交答案式的题目。你应当提供十个输出文件tetris1.out 到tetris10.out,放在用户目录中。每个文件包含若干行,每一行为两个整数T,C,依次表示各条指令。输入数据保证有解。当解不唯一时,任意输出一组解即可。
【样例输入】
4
3 2 3 0
【样例输出】
1 4
9 1
【评分标准】
对于每个测试点,如果你的输出不正确或者指令条数超过1,000,000,得0分;如果你的输出正确且指令不超过100,000 条,你可以得到10 分;如果你的输出正确,但指令超过100,000条,你就只能得到7分。
【你如何测试自己的输出】
圆圆的游戏程序game放在用户目录下。使用方法为: game <测试点编号X>。
程序会自动读取输入文件tetrisX.in和你的输出文件tetrisX.out,其中X=1,2,…,10。
Ø 如果game异常退出,你的输出视为错误;
Ø 如果你的输出文件非法,game将指出第一个有错误的行;
Ø 如果输出合法,game会产生一个tetris.log。该文件的第一行包含列数N,第二行,有N 个整数,依次表示按照你的输出进行游戏后各列连在一起的小方块的个数。
Ø game程序会同时在屏幕上输出你的得分。
题3
机器人M 号
【问题描述】
3030年,Macsy正在火星部署一批机器人。
第1秒,他把机器人1号运到了火星,机器人1号可以制造其他的机器人。
第2秒,机器人1号造出了第一个机器人——机器人2号。
第3秒,机器人1号造出了另一个机器人——机器人3号。
之后每一秒,机器人1号都可以造出一个新的机器人。第m 秒造出的机器人编号为m。我们可以称它为机器人m号,或者m号机器人。
机器人造出来后,马上开始工作。m号机器人,每m秒会休息一次。比如3号机器人,会在第6,9,12,……秒休息,而其它时间都在工作。
机器人休息时,它的记忆将会被移植到当时出生的机器人的脑中。比如6号机器人出生时,2,3 号机器人正在休息,因此,6 号机器人会收到第2,3 号机器人的记忆副本。我们称第2,3号机器人是6号机器人的老师。
如果两个机器人没有师徒关系,且没有共同的老师,则称这两个机器人的知识是互相独立的。注意:1 号机器人与其他所有机器人的知识独立(因为只有1号才会造机器人),它也不是任何机器人的老师。
一个机器人的独立数,是指所有编号比它小且与它知识互相独立的机器人的个数。比如1号机器人的独立数为0,2号机器人的独立数为1(1号机器人与它知识互相独立),6号机器人的独立数为2(1,5号机器人与它知识互相独立,2,
3号机器人都是它的老师,而4号机器人与它有共同的老师——2号机器人)。
新造出来的机器人有3种不同的职业。对于编号为m的机器人,如果能把m分解成偶数个不同奇素数的积,则它是政客,例如编号15;否则,如果m本身就是奇素数或者能把m分解成奇数个不同奇素数的积,则它是军人,例如编号3,
编号165。其它编号的机器人都是学者,例如编号2, 编号6, 编号9。
第 m 秒诞生的机器人m 号,想知道它和它的老师中,所有政客的独立数之和,所有军人的独立数之和,以及所有学者的独立数之和。可机器人m 号忙于工作没时间计算,你能够帮助它吗?
为了方便你的计算,Macsy已经帮你做了m的素因子分解。为了输出方便,只要求输出总和除以10000的余数。
【输入文件】
输入文件 robot.in 的第一行是一个正整数k(1<=k<=1000),k 是m 的不同的素因子个数。
以下k行,每行两个整数,pi, ei,表示m的第i个素因子和它的指数(i = 1, 2, …,k)。p1, p2, …, pk是不同的素数,(m大小见附件)。 所有素因子按照从小到大排列,即p1<p2<…<pk。输入文件中,2<=pi<10,000, 1<=ei<=1,000,000。
【输出文件】
输出文件robot.out 包括三行。
第一行是机器人 m号和它的老师中,所有政客的独立数之和除以10000的余数。
第二行是机器人m号和它的老师中,所有军人的独立数之和除以10000的余数。
第三行是机器人m号和它的老师中,所有学者的独立数之和除以10000的余数。
【样例输入】
3
2 1
3 2
5 1
【样例输出】
8
6
75
【样例说明】
m = 2´32 ´5 = 90。90号机器人有10个老师,加上它自己共11个。其中政客只有15 号;军人有3 号和5 号;学者有8 个,它们的编号分别是:2,6,9,10,18,30,45,90。
【评分标准】
输出文件包含三个数。如果你的程序算对了三个数,该测试点得10 分;如果你的程序算对了两个数,该测试点得7分;如果你的程序算对了一个数,该测试点得4分;如果你的程序一个数也没算对,该测试点得0分; |