ACMer 2013 Daily Training"/>
[翻译]ACMer 2013 Daily Training
[A] Oil Deposits
有一家石油公司负责探勘某块地底下的石油含量,这块地是矩行的,并且为了探勘的方便被切割为许多小块。然后使用仪器对每个小块去探勘。含有石油的小块称为一个pocket。假如两个pocket相连,则这两个pocket属于同一个oil deposit。(所谓相连的定义与踩地雷游戏中的定义相同,请参考sample input, sample output) 你的任务就是要找出这块地包含几个不同的oil deposit。
Input
输入包含好几组资料,每组资料的第一行有2个整数m,n。m代表这块地的列数,n代表这块地的行数。(1<=m,n<=100),接下来的m行就是这块地探勘的内容。'@'代表此小块含石油,'*'代表此小块不含石油。m=0 n=0代表输入结束。
Output
对每组测试资料输出oil deposit的数目。
Sample input
1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0
Sample Output
0 1 2 2
[B] - Sending email
网路上有n部邮件伺服器。如果某2部伺服器之间有网路线直接相连,我们可以知道email在这段路线传送要花多少时间。现在要传送一个email从伺服器S到伺服器T ,请问最少需要花多少时间?
你可以假设email在伺服器上不会有任何延迟,也就是说传送email的时间只跟网路线有关。
Input
输入的第一列有一个整数,代表有多少组测试资料。
每组测试资料的第一列有4个整数,n , m , S , T。
- n 代表伺服器的数目(2 <= n <= 20000)
- m 代表网路线段的数目(0 <= m <= 50000)
- S、T 代表email起始及目的伺服器。(0 <= S, T < n ,并且S不等于T)
接下来m 列,每列有3个整数u, v, w。代表伺服器u和伺服器v之间有网路线直接相连(双向都可传输),其email传送时间为w。(0 <= w <= 10000)
请参考Sample Input。
Output
对于每笔测资输出这是第几组测试资料,以及从伺服器S到伺服器T所要花的传送时间最少是多少?如果没有路径可以送达,请输出 unreachable 。请参考Sample Output。
Sample Input | Sample Output |
3 2 1 0 1 0 1 100 3 3 2 0 0 1 100 0 2 200 1 2 50 2 0 0 1 | Case #1: 100 Case #2: 150 Case #3: unreachable |
[C] A Graph Problem
给一个有n ( 1 <= n <= 76 )个节点的无向图形(图形如下):
你的任务是:给你n ,请算出这个图形有以下性质的节点子集合共有多少个。
- 集合里不能有两个相邻的点。例如图形中有n=3个节点,则集合{1,2} 是违法的,而集合{1,3} 是合法的。
- 当这个集合能再加入任一节点,却可以不和其它节点相邻,则这个集合是违法的。例如图形中有n=5个节点,则集合{1,5} 是违法的,因为这个集合再加入节点3仍不和其它节点相邻,而集合{1,3,5} 则是合法的。
所以,当图形有n=5 个节点时,应该有4 个合法的集合:{1,3,5},{2,4},{2,5},{1,4}.
Input
测试资料中有很多个测资,每个测资一列,每列包含一个数字n,1 <= n <= 76。请用EOF来判断档案结束。
Output
请输出一列含有上述性质的子集合的数目。你可以假设答案不会超过2 31。
Sample Input
1 2 3 4 5 30
Sample Output
1 2 2 3 4 4410
translated by TimeString
[D] Base -2
每个人都知道二进位(binary)及十进位数字(decimal)。但是来个-2 进位如何?一个-2 进位的数仅由0与1组成,并且下列的等式必须成立:
n = b 0 + b 1 (-2) + b 2 (-2) 2 + b 3 (-2) 3 + ...
最酷的是每一个整数(包含负数)都有一个唯一的-2 进位表达方式,而且不必用到负号。你的任务就是找出这样的表达方式。Input
输入的第一列有一个整数代表以下有几组测试资料。每组测试资料一列有一个十进位的整数n。(-1000000000 <= n <= 1000000000)
Output
每组测试资料输出这是第几组测试资料,然后输出n的-2进位表达方式。
输出格式请参考Sample Output。
Sample Input | Sample Output |
6 1 7 -2 0 -1 4 | Case #1: 1 Case #2: 11011 Case #3: 10 Case #4: 0 Case #5: 11 Case #6: 100 |
[E] Ordering Tasks
John有n件事情要做,不幸的是这些事情并不是各自独立的,而是有相依性的。换句话说可能有某件事情一定要在另一件事情做完之后才能做。
Input
每组测试资料可能有好几列。第一列有2个整数n,m。(1 <= n <= 100)n代表共有几件事情要做(编号从1 到n),m 代表事情之间有几个相依关系存在。接下来的m列每列有2个整数i 和j。代表i 这件事情一定要在j 这件事前被执行。
n=m=0时代表输入结束。
Output
对每组测试资料,请输出n个整数,代表事情被执行的顺序。
注:答案可能不是唯一解
Sample Input
5 4 1 2 2 3 1 3 1 5 0 0
Sample Output
1 4 2 5 3
[F] Tight Words
给你一个数字k(0 <= k <= 9),我们说一个由0~k 组成且长度为n 的字串是「紧密」的,如果任何相邻的数字相差不会超过1 的话。
例如:k=2, n=3, 那所有可能的字串为000, 001, 002, 010, 011, 012, 020, 021, 022, 100, 101, 102, ......, 220,221,222。共27个。
其中000, 001, 010, 011, 012 这些字串都是「紧密」的。但是002, 020, 102 这些字串则不是(因为0 跟2 相邻,其差超过1)。
Input
输入含有多组测试资料。每组测试资料一列,含有2 个正整数k 和n ( 1 <= n <= 100)。
Output
对每一组测试资料输出一列,输出所有可能字串中,「紧密」字串所占的百分比。请四舍五入到小数点后5 位。
例如:k=2, n=5, 所有可能的字串共有243 个,其中「紧密」的字串共有99 个,所以百分比为40.74074。请参考Sample Output。
Sample Input | Sample Output |
4 1 2 5 3 5 8 7 | 100.00000 40.74074 17.38281 0.10130 |
[G] Jugs
在电影「终极警探3(Die Hard 3)」中布鲁斯威利(Bruce Willis)和山谬杰克森(Samuel L. Jackson)遇到坏蛋设下的谜题:给一个3加仑和5加仑的桶子,要求他们必须在5加仑的桶子中装4加仑的水。现在你的任务就是解决这个问题。
给你2个桶子A、B和无限供应的水,你可以做3个动作:(1)把一个桶子装满水(2)把一个桶子的水倒光(3)把一个桶子的水倒到另一个桶子中。把水从一个桶子倒到另一个桶子的动作停止有2个可能的原因:第一个桶子的水倒光了或第二个桶子的水满了。例如:A有5加仑的水,B有6加仑的水且B的容量为8加仑,则当把A的水倒到B后,B就满了(8加仑)而A中还剩3加仑。在本问题中,给你Ca,Cb,N。Ca,Cb分别代表A桶子和B桶子的容量而N是我们要求的目标。我们希望你的程式输出一连串的动作之后,可以得到N加仑的水(不论在A或B中都可以)。这一连串的动作包含:
fill A fill B empty A empty B pour AB pour BA success
在这里,"pour AB"代表把A的水倒到B中,而"success"代表任务已经完成了。你可以假设给你的输入一定有解答。
Input
每组测试资料一列,含有3个正整数Ca,Cb,N。(0 < Ca <= Cb,N <= Cb <= 1000)
Output
每组测试资料输出一连串的动作(总是以success作为结束),使得可以得到N加仑的水(不论在A或B中都可以)。请参考Sample Output。
Sample Input
3 5 4 5 7 3 1 1 1
Sample Output
fill B pour BA empty A pour BA fill B pour BA success fill A pour AB fill A pour AB success fill A success
[H] Tiling
在2*n的矩形区域中,以2*1 或2*2 的小磁砖来贴总共有多少种方法?
以下为2*17矩形区域一种贴磁砖的方式。
Input
每组测试资料一列,有1个整数n(0 <= n <= 250)。
Output
对每组测试资料请输出一列,在2*n的矩形区域中共有多少种贴磁砖的方法。
Sample Input | Sample Output |
0 2 8 12 100 200 | 1 3 171 2731 845100400152152934331135470251 1071292029505993517027974728227441735014801995855195223534251 |
更多推荐
[翻译]ACMer 2013 Daily Training
发布评论