2010-5-25 04:43
周瑜
几道编程题
[b]写在前面[/b]
本帖只讨论数学、数据结构与算法，不讨论软件工程。题目并非本人原创，而是从其他途径收集而来。
每题后附件压缩包内是测试用例，包含一个输入文件和一个输出文件，各位可以用来测试自己的程序。值得注意的是：
1.所有输入都满足限制条件，不必另行测试。
2.大部分程序都在10秒内运行完成，如果程序运行时间超过1分钟，请改进程序。
3.解题步骤：只根据题目条件和示例输入输出完成程序，然后下载测试用例，检验程序输出与标准输出是否一致。
[b]01 链式开关[/b]
共有N个开关串连起来，初始时所有的开关都是断开状态。第一个开关前连接电源，最后一个开关之后连上一个灯泡。
每按一次按钮能够让所有通电的开关翻转一次。
例如，按一次按钮，第一个开关连通，电流可流向第二个开关。
再按一次按钮，第一个开关断开，第二个开关接通。
按第三次按钮，第一个开关接通，第二个开关保持不变，电流可流向第三个开关。
求按下K次按钮之后，第N个开关后的灯泡是否点亮。
输入格式：
第一行为测试样本数量 T ，以下 T 行每行有 N 和 K 两个整数。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为ON或者OFF
限制条件：
1 ≤ T ≤ 10,000
1 ≤ N ≤ 30
0 ≤ K ≤ 10^8
示例输入：
4
1 0
1 1
4 0
4 47
示例输出：
Case #1: OFF
Case #2: ON
Case #3: OFF
Case #4: ON
[color=Silver][[i] 本帖最后由 周瑜 于 2010-10-22 16:09 编辑 [/i]][/color]
2010-5-25 04:44
周瑜
02 太空观测
自古以来，人们就认识到太空事件都严格遵循着固定的周期，可以通过过去的发生时间，推断出同一事件下次可能的发生时间。然后，由于资料缺失，流传下来的往往只有过去零散的观测结果，并不能确定唯一的周期。
为了精确记录时间，这里引进一个极小的时间单位，称之为 A 。根据历史记载，某事件曾在 26000A，11000A，6000A 以前发生，虽然不能求出其周期，却可以判断该事件在 4000A 以后必然再次发生。
本题的要求就是根据太空事件过去的 N 次发生时间，求出下一次必然发生的时间点 y (y>=0)，单位为 A 。注意，由于宇宙漫长的历史，普通的32位或者64位整数已不能满足需要。
输入格式：
第一行为测试样本数量 C ，以下 C 行每行为一个样本，每行以 N 开头，以后是 N 个以空格分隔的整数 ti ，表示过去的某次事件到现在的时间。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为如上所述。
限制条件：
1 ≤ C ≤ 100
2 ≤ N ≤ 1000
1 ≤ ti ≤ 10^50
∑(ti-tj)^2 ≠ 0
示例输入：
3
3 26000000 11000000 6000000
3 1 10 11
2 800000000000000000001 900000000000000000001
示例输出：
Case #1: 4000000
Case #2: 0
Case #3: 99999999999999999999
[color=Silver][[i] 本帖最后由 周瑜 于 2010-5-30 15:16 编辑 [/i]][/color]
2010-5-25 04:45
周瑜
03 主题公园
主题公园的疯狂过山车非常火爆，游客从早到晚排队游玩，直到公园关门。过山车每天运行 R 趟，每趟最大载客 k 人，游客共分 N 组，每组 gi 人(0≤i<N)。早晨开门时，g0 组首先登车，然后依次是 g1，g2...。每一整组必须同时登车，下车的游客按照原来的排队顺序继续排在队尾等待下一次登车。如果过山车没有足够空间装载下一组则出发，即使没有装满，后一组也不能越过前一组提前上车。
求过山车一天总的搭载人次。
举例：
R = 4，k = 6，分组为1，4，2，1
第一车：1，4
第二车：2，1，1
第三车：4，2
第四车：1，1，4
总搭载人次：21
输入格式：
第一行为测试样本数量 T ，每个样本包含两行，第一行为以空格分隔的R，k，N，第二行有 N 个整数，表示每组人数，g0，g1，g2，等等。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为总搭载人次。
限制条件：
1 ≤ T ≤ 50
1 ≤ R ≤ 10^8
1 ≤ k ≤ 10^9
1 ≤ N ≤ 1000
1 ≤ gi ≤ 10^7
gi ≤ k
示例输入：
3
4 6 4
1 4 2 1
100 10 1
1
5 5 10
2 4 2 3 4 2 1 2 1 3
示例输出：
Case #1: 21
Case #2: 100
Case #3: 20
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-17 12:18 编辑 [/i]][/color]
2010-5-25 04:45
周瑜
04 翻转积木
一个截面为 N×N 的木盒内放着若干红色和蓝色的积木，每个积木都是 1×1 的正方形，并且与木盒底面和侧面的距离都为整数。现在向右翻转木盒90度，积木会受重力作用坠落而重新排列。
[font=Fixedsys]下图中， R 表示红色积木， B 表示蓝色积木， . 表示空格：
初始状态 翻转后 坠落后
....... ....... .......
....... R...... .......
....... BB..... .......
...R... BRRR... R......
...RB.. RBB.... BB.....
..BRB.. ....... BRR....
.RBBR.. ....... RBBR...[/font]
已知翻转前所有积木都是静止状态，完全翻转后积木才开始坠落。求坠落后是否存在横、竖、或斜的连续 K 个相同颜色的积木，输出仅红色、仅蓝色、都有、都没有四种判断之一。
输入格式：
第一行为测试样本数量 T ，每个样本包含 N+1 行，第一行为 N 和 K 两个整数，以下每行有 N 个字符，表示积木的初始位置，格式和含义均与上图相同。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为 Red、Blue、Both 或者 Neither
限制条件：
1 ≤ T ≤ 100
3 ≤ K ≤ N
3 ≤ N ≤ 50
示例输入：
[font=Fixedsys]4
7 3
.......
.......
.......
...R...
...BB..
..BRB..
.RRBR..
6 4
......
......
.R...R
.R..BB
.R.RBR
RB.BBB
4 4
R...
BR..
BR..
BR..
3 3
B..
RB.
RB.[/font]
示例输出：
Case #1: Neither
Case #2: Both
Case #3: Red
Case #4: Blue
[color=Silver][[i] 本帖最后由 周瑜 于 2010-5-30 21:51 编辑 [/i]][/color]
2010-5-25 04:45
周瑜
05 光滑数组
如果一个数组所有相邻两个元素之差的绝对值都不超过 M ，那么该数组就是一个光滑数组。
为了使数组变得光滑，有以下三种操作：
1. 删除任意元素，开销为 D
2. 在任意位置插入任意元素，开销为 I
3. 修改任意元素，开销为新值与原值之差的绝对值。
给定一个由有 N 个元素组成的一维数组，每个元素都在 0~255 范围之内，求通过以上三种操作，使其变为光滑数组的最小开销。
注意：空数组和只有一个元素的数组，都是光滑数组。
输入格式：
第一行为测试样本数量 T ，每个样本包含两行，第一行为D，I，M，N，第二行有 N 个整数 ai，表示数组中元素的值。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为使数组光滑的最小开销。
限制条件：
1 ≤ T ≤ 100
0 ≤ D, I, M, ai ≤ 255
1 ≤ N ≤ 100
示例输入：
2
6 6 2 3
1 7 5
100 1 5 3
1 52 6
示例输出：
Case #1: 4
Case #2: 18
示例解释：
第一个例子中，把 7 修改为 3 ，开销为 4 。
第二个例子中，删除的开销非常大，而插入的开销非常小，因此可先把 52 改为 51 ，在 1 和 51 之间插入 9 个数， 51 和 6 之间插入 8 个数，总开销为 18 。
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-6 07:17 编辑 [/i]][/color]
2010-5-25 04:46
周瑜
06 取豆游戏
甲乙面前有两堆豆子，每人轮流取，每次只能从多的那堆取少的那堆豆子数量的正整数倍，把其中一堆取完的输掉游戏。
例如两堆豆子分别为 12 和 51，
甲先取，从 51 中拿掉 12 的 3 倍 36 个，剩余数量为 12 和 15，
乙再取，从 15 中拿掉 12 个，剩余 12 和 3，
甲再取，从 12 中拿掉 3 的 3 倍 9 个，剩余 3 和 3，
轮到乙，必然把其中一堆 3 取完，乙认输。
假设甲乙两人都足够聪明，因此只要确定了两堆豆子的初始数量 (A,B) ，就能判定游戏结果。如果先取的甲必胜，那么称 (A,B) 为先手必胜。
给定 A1，A2，B1，B2，当 A1 ≤ A ≤ A2 并且 B1 ≤ B ≤ B2 时，求有多少对 (A,B) 构成先手必胜。
输入格式：
第一行为测试样本数量 T ，以下 T 行每行为一个样本，包含以空格分隔的四个整数 A1，A2，B1，B2。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为先手必胜 (A,B) 对的个数。
限制条件：
1 ≤ T ≤ 100
1 ≤ A1 ≤ A2 ≤ 1,000,000
1 ≤ B1 ≤ B2 ≤ 1,000,000
示例输入：
3
5 5 8 8
11 11 2 2
1 6 1 6
示例输出：
Case #1: 0
Case #2: 1
Case #3: 20
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-3 14:16 编辑 [/i]][/color]
2010-5-25 04:46
周瑜
07 创建目录
在Unix操作系统，文件都存储在目录中。通常用路径来表示嵌套的深层目录，路径名以 / 开头，各层目录名也用 / 分隔，但最后不再有 / 符号。
如果一个路径存在，则这个路径中的所有目录全部存在。如果需要创建一个路径，则底层和各级的父目录，凡是不存在的都需要创建。
例如，/home/xycq/forum 就是一个路径名，根目录下第一层为 home ，第二层为 xycq ，第三层为 forum 。如果除根目录外无任何目录，则需要使用 mkdir 命令三次才能创建这个完整路径。
已知存在 N 个路径，需要创建 M 个路径，求需要使用命令 mkdir 的次数。
输入格式：
第一行为测试样本数量 T ，每个样本第一行为 N 和 M 两个整数，以下 N 行表示已经存在的路径，接下来 M 行表示需要创建的路径。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为需要使用 mkdir 的次数。
限制条件：
1 ≤ T ≤ 100
0 ≤ N ≤ 100
1 ≤ M ≤ 100
所有路径不多于 100 个字符。
示例输入：
3
0 2
/home/gcj/finals
/home/gcj/quals
2 1
/chicken
/chicken/egg
/chicken
1 3
/a
/a/b
/a/c
/b/b
示例输出：
Case #1: 4
Case #2: 0
Case #3: 4
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-4 18:56 编辑 [/i]][/color]
2010-5-25 04:46
周瑜
08 抓起小鸡
一些小鸡在笔直的窄道上同向行走，每只小鸡保持恒定的速度。当后面的小鸡追上前面的小鸡时，后面的小鸡会暂时把速度降为与前面小鸡的速度相等。此时如果抓起前面的小鸡并放下，两只小鸡将交换位置，并恢复各自本来的速度继续前进。抓起放下小鸡的动作瞬时完成，即使有多只小鸡在同一地点，每次抓起也只能让后面的一只小鸡超过。
给定小鸡数量 N ，初始坐标 Xi ， 初始速度 Vi ，目的地坐标 B ，求至少需要多少次抓起动作，才能保证至少有 K 只小鸡在时间 T 之内到达目的地。
输入格式：
第一行为测试样本数量 C ，每个样本包含三行，第一行为N，K，B，T，第二行有 N 个不同整数 Xi ，按照升序排列，表示小鸡的初始坐标，第三行有 N 个整数 Vi ，表示小鸡初始速度。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为最少需要交换的次数，或者 IMPOSSIBLE
限制条件：
1 ≤ C ≤ 100
1 ≤ B ≤ 1,000,000,000
1 ≤ T ≤ 1,000
0 ≤ Xi < B
1 ≤ Vi ≤ 100
1 ≤ N ≤ 50
0 ≤ K ≤ N
示例输入：
3
5 3 10 5
0 2 5 6 7
1 1 1 1 4
5 3 10 5
0 2 3 5 7
2 1 1 1 4
5 3 10 5
0 2 3 4 7
2 1 1 1 4
示例输出：
Case #1: 0
Case #2: 2
Case #3: IMPOSSIBLE
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-7 10:29 编辑 [/i]][/color]
2010-5-25 04:47
周瑜
09 绝对序号
127是个很有意思的数。首先，它是一个质数。在质数集合中，127是第31个质数，31又是第11个质数，11是第5个，5是第3个，3是第2个，2是第1个，1不是质数。
如上所示，序号的定义是集合中不大于该数的元素个数。如果某数在集合中的序号仍然在这个集合中，序号的序号也在这个集合中，序号的序号的序号……全都在这个集合中，最终通过有限次求序号操作后得到1，而1不在这个集合中。那么，就称该数在此集合中拥有绝对序号。
已知 n ，求 n 在集合 {2, 3, 4, ..., n} 的多少个子集中拥有绝对序号。由于计算结果很大，只需要回答子集个数除以 100003 的余数。
输入格式：
第一行为测试样本数量 T ，以下 T 行每行包含一个整数 n 。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 如上所述。
限制条件：
1 ≤ T ≤ 100
2 ≤ n ≤ 500
示例输入：
2
5
6
示例输出：
Case #1: 5
Case #2: 8
示例解释：
第一个例子中，5在{2, 3, 4, 5}{2, 3, 5}{3, 4, 5}{2, 5}{5} 这5个集合中拥有绝对序号。
第二个例子中，6在{2, 3, 4, 5, 6}{2, 3, 4, 6}{2, 4, 5, 6}{2, 3, 6}{3, 4, 6}{3, 5, 6}{2, 6}{6} 这8个集合中拥有绝对序号。
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-7 10:37 编辑 [/i]][/color]
2010-5-25 04:48
周瑜
10 有线网络
某公司在两栋相邻的办公楼都有不少办公室，这两栋楼称为左楼和右楼。铺设内部有线局域网时，使用了一些网线把位于左楼和右楼的办公室连接起来。
从侧面看去，网线如蜘蛛网般纵横交错。任何办公室最多只和对面楼的一间办公室有网线相连，没有三条或更多的网线在空中交于一点。
已知网线数量 N ，各条网线连接的楼层号 Ai，Bi，求从侧面看去网线在空中的交点数。
输入格式：
第一行为测试样本数量 T ，每个样本包含 N+1 行，第一行为网线数量 N ，以下 N 行每行有2个整数 Ai，Bi，分别表示该网线所连接的左右楼楼层号。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为侧面看去网线的交点数。
限制条件：
1 ≤ T ≤ 15
1 ≤ Ai ≤ 10^4
1 ≤ Bi ≤ 10^4
1 ≤ N ≤ 1000
示例输入：
2
3
1 10
5 5
7 7
2
1 1
2 2
示例输出：
Case #1: 2
Case #2: 0
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-7 10:42 编辑 [/i]][/color]
2010-5-25 04:49
周瑜
11 负载测试某网站的负载出错检测是突变的，同时在线人数不超过某个值 X 时可以正常工作，一旦达到 X+1，网站就会出错。
已知该网站可以支持 L 人但不能支持 P 人(L<P)同时在线。现在希望通过负载测试，缩小上下限区间到 C 倍以内。即存在某个正整数 a，网站可以支持 a 人但不支持 a*C 人。
求最坏情况最少需要多少次负载检测。
注：每次负载检测只会有通过和出错两种情况，不会有其他结果。
输入格式：
第一行为测试样本数量 T ，以下 T 行每行为一个样本，包含以空格分隔的三个整数 L，P，C。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为最坏情况下需要测试的次数。
限制条件：
1 ≤ T ≤ 1000
2 ≤ C ≤ 10
1 ≤ L < P ≤ 10^9
L，P，C 均为整数
示例输入：
4
50 700 2
19 57 3
1 1000 2
24 97 2
示例输出：
Case #1: 2
Case #2: 0
Case #3: 4
Case #4: 2
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-7 11:03 编辑 [/i]][/color]
2010-5-25 04:50
周瑜
12 制作棋盘
有一块 M 行 N 列的大石板，每个小方格都是黑白二色之一，现在需要把这块石板制作成若干棋盘。棋盘的定义是一个 X*X 的正方形，其任意两块相邻的小方格颜色都不同。
制作棋盘的方法是先从石板上剪下最大可能的棋盘，然后再剪下次大的棋盘，直到剪下 1*1 的微型棋盘。如果有相同大小的棋盘，先裁剪上方的，如果高度还相等，则先裁剪左方的。
求每种大小的棋盘各能制作多少个。
输入格式：
第一行为测试样本数量 T ，每个样本包含 M+1 行，第一行为 M 和 N 两个整数，以下 M 行每行表示石板的一行的颜色，第一行为最上方一行，最后一行为最下方一行。每行有 N/4 个字符，其中 N 一定被4整除。
为了减小输入文件大小，用每个字符表示相邻4个小方格的颜色。把输入文件的 0-9 和 A-F 换成二进制，高位表示左边的方格，低位表示右边的方格。1代表白色，0代表黑色。
输出格式：
每个样本第一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为可制作的不同大小棋盘的类别数量。以下 y 行每行包含两个整数，分别是棋盘边长和该边长的棋盘数量，并按棋盘大小降序排列。
限制条件：
1 ≤ T ≤ 100
1 ≤ M ≤ 512
1 ≤ N ≤ 512，N 是4的倍数
示例输入：
4
15 20
55555
FFAAA
2AAD5
D552A
2AAD5
D542A
4AD4D
B52B2
52AAD
AD552
AA52D
AAAAA
5AA55
A55AA
5AA55
4 4
0
0
0
0
4 4
3
3
C
C
4 4
6
9
9
6
示例输出：
Case #1: 5
6 2
4 3
3 7
2 15
1 57
Case #2: 1
1 16
Case #3: 2
2 1
1 12
Case #4: 1
2 4
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-9 14:09 编辑 [/i]][/color]
2010-5-25 04:50
周瑜
13 完美菱形
(由于论坛显示限制，本题数字与空格使用了全角字符，请读者自行转化为半角字符，测试样本实际输入字符也是半角字符)
通过一个菱形的中心，沿水平和竖直方向各作一条轴，如果菱形上的数关于这两条轴对称，那么这个菱形就是一个完美菱形。以下分别是边长为2和3的两个完美菱形：
１ １
２ ２ ２ ２
１ ３ ４ ３
２ ２
１
对于任意一个菱形，如果不是完美的，都可以通过添加一些数字，把这个菱形变得完美。下图中，左边是原菱形，右边是添加后的完美菱形：
５
４ ４ ４
２ ３ ２ ３ ２
４ ４ ４
５
给定一个菱形，求最少需要添加多少个数字才能把这个菱形变得完美。
输入格式：
第一行为测试样本数量 T ，每个样本包含 2k 行，第一行为菱形边长 k ，以下 2k-1 行为菱形初始数据，菱形中的每个数字都不大于 9。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为最少需要添加的数字个数。
限制条件：
1 ≤ T ≤ 100
1 ≤ k ≤ 51
示例输入：
４
１
０
２
１
２ ２
１
２
１
１ ２
１
３
１
６ ３
９ ５ ５
６ ３
１
示例输出：
Case #1: 0
Case #2: 0
Case #3: 5
Case #4: 7
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-13 19:08 编辑 [/i]][/color]
2010-5-25 04:51
周瑜
14 世界杯门票
南非世界杯已开幕，现在准备购买门票前往观看第二阶段淘汰赛。由于门票紧张，所有球票都应在第一轮比赛开始之前购买。每场比赛的开赛时间都不同，可以观看全部比赛。
淘汰赛共有 2^P 支球队参加，经过 P 轮比赛决出冠军。每场比赛必然分出胜负，否则加时点球，每轮之后有一半的球队被淘汰出局。淘汰赛开始后，每支球队的晋级路线、第一轮对手和以后各轮可能遇到的对手都已确定，而不用像冠军杯一样每轮之后抽签。
根据喜好不同，最多允许错过各球队 Mi 场比赛。即无论出现什么样的晋级可能，观看选择的比赛后，错过每支球队的比赛都不超过 Mi 场。
已知各场比赛的票价，和允许错过的场次，求最少需要花费多少钱购买门票才能满足要求。
输入格式：
第一行为测试样本数量 T ，每个样本包含 P+2 行，第一行为 P ，第二行有 2^P 个整数，分别是每支球队最多允许错过的比赛数 Mi ，以下 P 行为各场比赛门票 Si ，每行分别有 P/2， P/4， ...，4，2，1个整数。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为需要购买的门票价格总和最小值。
限制条件：
1 ≤ T ≤ 50
1 ≤ P ≤ 10
0 ≤ Mi ≤ P
0 ≤ Si ≤ 100000
示例输入：
2
2
1 1 0 1
1 1
1
3
1 2 3 2 1 0 1 3
100 150 50 90
500 400
800
示例输出：
Case #1: 2
Case #2: 1350
示例解释：
第二个例子中，由于不允许错过第六支球队的比赛，因此晋级路线上的三场比赛门票都应购买，花费50+400+800，此时唯有第一支球队观看要求未满足，选择购买其最便宜的一场100。这样，总花费是1350。
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-16 12:08 编辑 [/i]][/color]
2010-5-25 04:51
周瑜
15 细菌繁殖
在一块无限大平面上，许多细菌在正整数坐标点上繁殖与消亡，其规则如下：
1. 如果某细菌坐标点相邻的上方和左方都没有细菌，下一秒钟该细菌会消亡。
2. 如果某无细菌坐标点相邻的上方和左方都有细菌，下一秒钟此处会新产生一个细菌。
3. 其余坐标点保持不变。
上方指 y 坐标减小的方向，左方指 x 坐标减小的方法。在一个坐标点最多同时存在一个细菌，所有细菌的产生和消亡都一秒一秒同步进行，同一坐标同一秒钟不会同时发生产生与消亡。
例如，某平面的细菌分布如下(1表示有细菌，0表示无细菌)：
[font=Fixedsys]000010
011100
010000
010000
000000[/font]
6秒钟后，所有细菌会全部消亡，具体过程是：
[font=Fixedsys]000000 000000 000000 000000 000000 000000
001110 000110 000010 000000 000000 000000
011000 001100 000110 000010 000000 000000
010000 011000 001100 000110 000010 000000
000000 000000 000000 000000 000000 000000[/font]
已知初始状态细菌的分布，求经过多少秒后所有细菌会全部消亡。
输入格式：
第一行为测试样本数量 T ，每个样本用若干矩形表示初始细菌分布，在这些矩形内全是细菌，矩形可相互重叠和包含。
每个样本第一行为 R ，表示该样本的矩形数量，以下 R 行每行有以空格分隔的四个整数X1，Y1，X2，Y2，表示该矩形区域内全是细菌。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为细菌全部消亡所需要的秒数。
限制条件：
1 ≤ T ≤ 100
1 ≤ R ≤ 1000
1 ≤ X1 ≤ X2 ≤ 1000000
1 ≤ Y1 ≤ Y2 ≤ 1000000
示例输入：
1
3
5 1 5 1
2 2 4 2
2 3 2 4
示例输出：
Case #1: 6
[color=Silver][[i] 本帖最后由 周瑜 于 2010-10-21 15:10 编辑 [/i]][/color]
2010-5-25 04:51
周瑜
16 草原牧羊
现有 N 只羊，在无限大的草原上放牧。每只羊用长度为 Li 的绳子栓在一个位于 Pi 的木桩上，其活动范围为到 Pi 的距离不超过 Li 的区域。
另打算设一水槽，每只羊必须都能到达水槽饮水。但所有羊只聚在一起时会发生斗殴，因此应使所有羊都能活动的公共区域尽可能小。
木桩位置 Pi 均固定，但绳长 Li 不固定。水槽位于 M 个可能位置之一，用 Q1, Q2, ..., QM 表示。
已知 Pi 和 Qi，对于每一处 Qi 求所有羊都能活动的最小公共区域面积。
输入格式：
第一行为测试样本数量 T ，每个样本包含 N+M+1 行，第一行为 N 和 M 两个整数，以下 N 行每行有两个整数，表示木桩 Pi 坐标，接下来 M 行每行也有两个整数，表示水槽可能的坐标 Qi 。
输出格式：
每一行为 Case #x: A1 A2...AM 的格式，其中 x 为1开始的测试样本序号，Ai 为水槽设在 Qi 位置时的羊群可活动的最小公共区域面积，并用空格分隔。
绝对或相对误差不超过 10^(-6) 均视为正确。
限制条件：
1 ≤ T ≤ 10
2 ≤ N ≤ 5,000
1 ≤ M ≤ 1,000
Pi 和 Qi 坐标绝对值不超过 10, 000
Pi 和 Qi 没有任何两点重合
Pi 和 Qi 没有任何三点共线
示例输入：
3
2 3
0 20
20 0
-20 10
40 20
0 19
4 2
0 0
100 100
300 0
380 90
400 100
1000 5
3 1
0 0
10 10
20 0
10 5
示例输出：
Case #1: 1264.9865911 1713.2741229 0.2939440
Case #2: 1518.9063729 1193932.9692206
Case #3: 0.0000000
[color=Silver][[i] 本帖最后由 周瑜 于 2010-7-4 11:53 编辑 [/i]][/color]
2010-5-25 04:51
周瑜
17 伪随机数
现有一种伪随机数的算法，可以生成 0~P-1 之间的随机数，其中 P 是质数。
任取一个初始值 S (0 ≤ S ≤ P-1) 和两个非负整数 A、B ，根据以下递推公式，可以得到一个伪随机数列。
S[0] = S
S[i+1] = (A*S[i] + B) mod P , i≥0
已知用上述方法生成的伪随机数列前 K 项，并且 P 是不超过 D 位的质数(P<10^D)，求该伪随机数列的下一项。如果不存在或者可能存在多个不同的值，输出 I don't know.
输入格式：
第一行为测试样本数量 T ，每个样本包含两行，第一行为以空格分隔的D，K，第二行有 K 个整数，表示该数列的前 K 项。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为数列下一项或者 I don't know.
限制条件：
1 ≤ T ≤ 100
1 ≤ K ≤ 10
1 ≤ D ≤ 6
示例输入：
3
2 10
0 1 2 3 4 5 6 7 8 9
3 1
13
1 5
6 6 6 6 6
示例输出：
Case #1: 10
Case #2: I don't know.
Case #3: 6
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-16 12:07 编辑 [/i]][/color]
2010-5-25 04:52
周瑜
18 修建栅栏
我们需要修建一个非常长的栅栏，因此需要到商店中购买较短的栅栏拼接起来。
商店中有 N 种不同长度的栅栏出售，每种栅栏都可无限购买。为了节省原料，所有栅栏的长度相加应恰好等于所需要栅栏的长度。
已知需要修建的栅栏长度为 L ，商店出售栅栏长度为 Bi (0 ≤ i < N)，求最少需购买的栅栏数量。如果无法达到要求，输出 IMPOSSIBLE
输入格式：
第一行为测试样本数量 T ，每个样本包含两行，第一行为以空格分隔的 L，N，第二行有 N 个整数，表示商店出售的栅栏长度 Bi 。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为所需栅栏的数量或者 IMPOSSIBLE
限制条件：
1 ≤ T ≤ 50
10^10 ≤ L ≤ 10^18
1 ≤ N ≤ 100
1 ≤ Bi ≤ 100000
示例输入：
2
10000000001 3
23 51 100
10000000001 3
100 52 22
示例输出：
Case #1: 100000004
Case #2: IMPOSSIBLE
示例解释：
第一个例子，可以使用2个23，5个51，和99999997个100，总计100000004个栅栏。
第二个例子，只能拼接出偶数长度的栅栏。
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-17 12:22 编辑 [/i]][/color]
2010-5-25 04:53
周瑜
19 热狗商人
在一条无限长的东西方向的大街上每隔相等距离就有一个路口，若干热狗商人正在某些路口出售热狗。如果有两个或者更多的商人聚集在同一个路口出售热狗，他们之间会相互影响生意，必须进行如下疏散。
疏散方法为：如果某路口有多于一个的热狗商人，那么其中一个移动到东面的下一个路口，另一个移动到西面的下一个路口，其余商人留在原地。如果还有多于一个商人的路口，则进行下一次疏散，直到所有路口的商人都不多于一个。
比如相邻七个路口的热狗商人数量为 0 0 2 1 2 0 0 ，疏散一次后变为 0 1 0 2 2 0 0 ，疏散两次后变为 0 1 1 0 3 0 0 ，疏散三次后变为0 1 1 1 1 1 0 ，疏散完成。
已知各路口热狗商人的分布情况，求需要经过多少次疏散才能使每个路口的商人都不多于一个。
输入格式：
输入时，只给出至少存在一个热狗商人的路口坐标，和该路口的商人个数，其余路口都没有商人存在。
第一行为测试样本数量 T ，每个样本包含 C+1 行，第一行为整数 C，表示至少存在一个热狗商人的路口数量，以下 C 行每行有 P 和 V 两个整数，表示在路口 P 有 V 个商人。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为需要进行疏散的次数。
限制条件：
1 ≤ T ≤ 50
1 ≤ C ≤ 200
| Pi | ≤ 1,000,000
Pi ≠ Pj, if i ≠ j
∑Vi ≤ 100,000
示例输入：
2
3
-1 2
0 1
1 2
2
-1000 1
2000 1
示例输出：
Case #1: 3
Case #2: 0
[color=Silver][[i] 本帖最后由 周瑜 于 2010-7-16 21:00 编辑 [/i]][/color]
2010-5-25 04:53
周瑜
20 神秘加法
神秘加法是这样一种加法算式，如下所示：
[font=Fixedsys] 124
31
15
----
170[/font]
神秘加法算式至少有一个加数，多则不限，所有加数都为不以0开头的正数。除了横线下的和以外，各个加数在同一数位上的数字必须互不相同。如百位上只有1，十位上是2,3,1，个位上是4,1,5。如果把第三个加数改为25(和为180)，则十位上的2与第一个加数重复，此时该算式不再是神秘加法。
以上是一个十进制的神秘加法的例子，但我们还关心其他进位制的神秘加法。与十进制的定义相同，无论是多少进制，只要所有加数在同一数位上的数字或者符号互不相同，此算式就是一个神秘加法。
求和为 N 的 B 进制神秘加法有多少个，由于计算结果很大，只需要回答其个数除以 1000000007 所得余数。
注1：仅仅加数顺序不同的加法，是同一个神秘加法。
注2：本题运行时间较长。
输入格式：
第一行为测试样本数量 T ，以下 T 行每行有 N 和 B 两个整数，两个数都以十进制形式列出。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 如上所述。
限制条件：
1 ≤ T ≤ 20
1 ≤ N ≤ 10^18
2 ≤ B ≤ 70
示例输入：
2
6 10
8 4
示例输出：
Case #1: 4
Case #2: 4
示例解释：
第一个例子中，共有 6=6，1+5=6，2+4=6，1+2+3=6 四个和为 6 的神秘加法。
第二个例子中，共有 20=20，11+3=20，13+1=20，10+3+1=20 四个和为 20(即十进制的8) 的神秘加法。
[color=Silver][[i] 本帖最后由 周瑜 于 2010-7-17 10:01 编辑 [/i]][/color]
2010-5-25 08:18
zhouhuan
占沙发待评论:hz1025:
2010-5-25 08:44
狂笑四海
我也占个。
看到周大占楼26，莫非与字母有关？
2010-5-26 07:49
dimeterio
前排就座，无意识围观
2010-5-26 08:36
阿尔法孝直
晕，原来第一题是二进制计数啊
2010-5-26 10:33
阿尔法孝直
[code]#include <stdio.h>
#define MaxN 30
#define MaxK 10e8
unsigned long _2N(unsigned int N){
unsigned int i;
unsigned long result=1;
i=N;
while(i--)result*=2;
return(result);
}
unsigned int lighting(unsigned int N,unsigned long K){
unsigned int result;
unsigned int N1;
unsigned long K1;
N1=_2N(N);
K1=K+1;
result=!(unsigned int)(K1%N1);
return(result);
}
void main(){
unsigned int T;
unsigned int N[255];
unsigned long K[255];
unsigned int i;
scanf("%d\n",&T);
for (i=0;i<=T-1;++i)
scanf("%d %d\n",&N[i],&K[i]);
for (i=0;i<=T-1;++i){
printf("Case #%d:",i+1);
if (N[i]==0 || N[i]>MaxN || K[i]>MaxK)
printf("ERROR\n");
else if(lighting(N[i],K[i]))
printf("ON\n");
else printf("OFF\n");
}
printf("Press any key to exit...\n");
getchar();
}[/code]
2010-5-26 12:48
张洋
楼主这是变相增加发帖量吗？:hz1019:
话说编程俺还真的不懂
2010-5-26 18:34
崔浩
周公瑾童鞋占楼甚是凶猛，不过俺在此纯路过
:hz1019:
2010-5-26 23:47
周瑜
这区不能发附件，版主帮忙转到设计与修改去吧。
2010-5-29 00:38
岱瀛
第一题没怎么看明白，给画个电路图？
为啥串联的开关，第一个闭合，第二个打开，整个电路是断路啊，怎么有电流？
第三题公园，没有太细想，先按着条件写了一个，见附件。
输入in.txt,输出out.txt
2010-5-29 00:51
阿尔法孝直
回复 #35 岱瀛 的帖子
从右往左数，最右边是第一个开关。
一开始是：
灯—00000000……00000000—电源，第一个断开的开关是通电的，那么按一下按钮之后，最后一个开关状态翻转：
灯—00000000……00000001—电源，此时电流通过第一个开关到达第二个开关，那么按第二次按钮后，前两个开关状态都翻转：
灯—00000000……00000010—电源，此时第一个开关通电，第二个开关断电，那么按第三次按钮后，仅第一个开关状态翻转：
灯—00000000……00000011—电源，此时电流通过前两个开关到达第三个开关，那么按第四次按钮后，前三个开关状态翻转：
灯—00000000……00000100—电源，
……
从前几步就可以看出，其实这就是二进制计数的题目。显然每按下一次按钮，开关序列组成的二进制数+1。
那么如果有N个开关，就需要按(K*2^N-1)次按钮才能把灯点亮。(K为正整数。)
--------------------------------------------------------------
另外，通电未必等于有电流，如果电源是市电220V火线，你用手碰一下通电的开关……
[color=Silver][[i] 本帖最后由 阿尔法孝直 于 2010-5-29 00:53 编辑 [/i]][/color]
2010-5-29 02:32
周瑜
孝直的理解是正确的，无论是闭合且连接电源的开关，还是打开但有一半连接电源的开关，按下按钮后都会翻转。
如果要设计电路，那就是每个开关之前有一个翻转装置与按钮相连，开关前端一旦有电压，在按钮触发下翻转装置即可工作。
----------------------------------------------------------------------------
新上传了测试用例，各位可以用来测试自己的程序。如果文件读写困难，可以使用freopen重定向输入输出，不用修改源代码，继续使用scanf/cin/gets和printf/cout/puts来读写文件。
值得注意的是：
1.所有输入都满足限制条件，不必另行测试。
2.除非特殊说明，Case x:冒号之后有一个空格，然后才是输出结果。
3.大部分程序都在10秒内运行完成，如果程序运行超过1分钟，请改进程序。
[color=Silver][[i] 本帖最后由 周瑜 于 2010-5-28 16:46 编辑 [/i]][/color]
2010-5-29 07:53
Maxwell
[quote]原帖由 [i]周瑜[/i] 于 2010-5-25 04:43 发表
01 链式开关[/quote]
:hz1026:我的理解有问题吗，怎么感觉就是一个二进制进位？直接根据k输出各位的值就可以了。
2010-5-29 10:07
Maxwell
[quote]原帖由 [i]周瑜[/i] 于 2010-5-25 04:45 发表
主题公园[/quote]
算法上没仔细考虑，-O2在atom1.6上要20s，超时了，找个好机器试试。。。
[code]
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
typedef std::vector<int> TIntVector;
__int64 Calc(TIntVector const& Group, int R, int k)
{
__int64 Total = 0;
TIntVector Step;
TIntVector Count;
int const GroupSize = Group.size();
Step.resize(GroupSize);
Count.resize(GroupSize);
for (int i = 0; i < GroupSize; ++i)
{
int ItStep = 0;
int ItCount = 0;
for (int j = 0; j < GroupSize; ++j)
{
int Sub = i + j;
if (Sub >= GroupSize)
{
Sub -= GroupSize;
}
if (ItCount + Group[Sub] <= k)
{
++ItStep;
ItCount += Group[Sub];
}
else
{
break;
}
}
Step[i] = ItStep;
Count[i] = ItCount;
}
if (GroupSize == Step[0])
{
Total = Count[0] * static_cast<__int64>(R);
}
else
{
int Next = 0;
for (int i = 0; i < R; ++i)
{
Total += Count[Next];
Next += Step[Next];
if (Next >= GroupSize)
{
Next -= GroupSize;
}
}
}
return Total;
}
int main()
{
std::ifstream In("in.txt");
std::ofstream Out("testout.txt");
std::string Line;
int T = 0;
In >> T;
for (int i = 0; i < T; ++i)
{
int R = 0;
int k = 0;
int N = 0;
In >> R;
In >> k;
In >> N;
int Value;
TIntVector Group;
for (int j = 0; j < N; ++j)
{
In >> Value;
Group.push_back(Value);
}
__int64 Result = Calc(Group, R, k);
Out << "Case #" << i + 1 << ": " << Result << std::endl;
}
return 0;
}
[/code]
[color=Silver][[i] 本帖最后由 Maxwell 于 2010-5-29 11:01 编辑 [/i]][/color]
2010-5-29 10:29
Maxwell
找了个2G的台式机试了试，11s。。。
2010-5-29 10:56
周瑜
第1题并不是输出第k位，而是要求最低k位全是1。
第3题程序有点小错误，最后的
if (k == Step[0])
应改为
if (GroupSize == Step[0])
11秒已经是比较好的成绩了，但是算法上还有可以改进的地方，比换好机器管用。由于 N 比 R 小的多，就连 N^2 都比 R 小，可以尝试使用O(N^2)甚至O(NlogN)的算法。当然，这需要一点数学推导。
[color=Silver][[i] 本帖最后由 周瑜 于 2010-5-28 23:07 编辑 [/i]][/color]
2010-5-29 11:06
Maxwell
[quote]原帖由 [i]周瑜[/i] 于 2010-5-29 10:56 发表
第1题并不是输出第k位，而是要求最低k位全是1。
第3题程序有点小错误，最后的
if (k == Step)
应改为
if (GroupSize == Step)
11秒已经是比较好的成绩了，但是算法上还有可以改进的地方，比换好机器管 ... [/quote]
第1题没仔细看题，以为Case #x是第x位了。。。O(1)的题太少见了。。。
嗯，是写错了，测试用例里正好没有能暴露问题的用例，结果没发现。。。还是不太适应这种竞赛性质的题，一堆单字母一会儿就晕了。。。
作为懒的借口，我强调符合要求就好:hz1016:回头仔细想想算法去
[color=Silver][[i] 本帖最后由 Maxwell 于 2010-5-29 11:12 编辑 [/i]][/color]
2010-5-29 11:54
Maxwell
[quote]原帖由 [i]周瑜[/i] 于 2010-5-25 04:45 发表
主题公园[/quote]
一个新算法，复杂度似乎小于3N。
其它部分不变，改为调用Calc2即可。程序一闪就结束了，无法计时。
这段程序一次写成，没有经过调试，不保证在任何情况下都正确。
-----------------
上面的复杂度有问题。。。中午出了门想起来不对了，这个算法第一个循环还是O(N^2)的，不过可以改进到O(N)，大约是4N。代码不写了，只要缓存计算结果就可以。
[code]
__int64 Calc2(TIntVector const& Group, int R, int k)
{
__int64 Total = 0;
TIntVector Step;
TIntVector Count;
int const GroupSize = Group.size();
Step.resize(GroupSize);
Count.resize(GroupSize);
for (int i = 0; i < GroupSize; ++i)
{
int ItStep = 0;
int ItCount = 0;
for (int j = 0; j < GroupSize; ++j)
{
int Sub = i + j;
if (Sub >= GroupSize)
{
Sub -= GroupSize;
}
if (ItCount + Group[Sub] <= k)
{
++ItStep;
ItCount += Group[Sub];
}
else
{
break;
}
}
Step[i] = ItStep;
Count[i] = ItCount;
}
if (GroupSize == Step[0])
{
Total = Count[0] * static_cast<__int64>(R);
}
else
{
std::vector<__int64> PreCount;
TIntVector PreR;
TIntVector FlagN;
int Next = 0;
__int64 ItPreCount = 0;
int ItPreR = 0;
__int64 CycleCount = 0;
int CycleR = 0;
int TailNext = 0;
bool Finish = true;
PreCount.resize(GroupSize);
PreR.resize(GroupSize);
FlagN.resize(GroupSize);
for (int i = 0; i < R; ++i)
{
if (0 == FlagN[Next])
{
PreCount[Next] = Total;
PreR[Next] = i;
FlagN[Next] = 1;
Total += Count[Next];
Next += Step[Next];
if (Next >= GroupSize)
{
Next -= GroupSize;
}
}
else
{
ItPreCount = PreCount[Next];
ItPreR = PreR[Next];
CycleCount = Total - ItPreCount;
CycleR = i - ItPreR;
TailNext = Next;
Finish = false;
break;
}
}
if (!Finish)
{
__int64 Tail = 0;
for (int i = 0; i < ((R - ItPreR) % CycleR); ++i)
{
Tail += Count[TailNext];
TailNext += Step[TailNext];
if (TailNext >= GroupSize)
{
TailNext -= GroupSize;
}
}
Total = ItPreCount + (R - ItPreR) / CycleR * static_cast<__int64>(CycleCount) + Tail;
}
}
return Total;
}
[/code]
[color=Silver][[i] 本帖最后由 Maxwell 于 2010-5-29 18:51 编辑 [/i]][/color]
2010-5-29 18:46
Maxwell
上面的复杂度有问题。。。中午出了门想起来不对了，这个算法第一个循环还是O(N^2)的，不过可以改进到O(N)，大约是4N。代码不写了，只要缓存计算结果就可以。
2010-5-30 02:54
周瑜
Maxwell这道题做的相当精彩，我只想到了使用二分法的O(NlogN)算法，却没想到类似双指针的O(N)算法。
看来即使题目中对N的限制提高到10^6或者10^7，也可以在很短时间内跑完了。
2010-5-30 21:10
Maxwell
[quote]原帖由 [i]周瑜[/i] 于 2010-5-25 04:44 发表
02 太空观测[/quote]
这个题如果我没理解错的话，主要难度在大数运算上，不过可以全用减法，程序简单。10^50不到180位，6个32位或者3个64位就够了。按说明看应该输入是降序排序的，不过示例输入值有从大到小的也有从小到大的，关键是没说是不是保证有序的，从示例也看不出来。
但是全用减法速度上不去，实现个除法比较好。
[color=Silver][[i] 本帖最后由 Maxwell 于 2010-5-30 21:27 编辑 [/i]][/color]
2010-5-31 03:13
周瑜
可能是我描述的不够清楚，已把题目改为“整数ti，表示过去的某次事件到现在的时间。”ti未必有序，也未必互不相等，但不会全相等。
2010-5-31 12:12
Maxwell
[quote]原帖由 [i]周瑜[/i] 于 2010-5-31 03:13 发表
可能是我描述的不够清楚，已把题目改为“整数ti，表示过去的某次事件到现在的时间。”ti未必有序，也未必互不相等，但不会全相等。 [/quote]
后来想了一下，是否排序无所谓。不过两个相等的数值代表什么含义呢，是两次同时发生的事件还是重复数据？
2010-6-1 03:19
周瑜
[quote]原帖由 [i]Maxwell[/i] 于 2010-5-31 00:12 发表
后来想了一下，是否排序无所谓。不过两个相等的数值代表什么含义呢，是两次同时发生的事件还是重复数据？ [/quote]
是重复数据。其实这完全是干扰条件，只是手头拿到的数据就有重复的。
2010-6-1 09:20
Maxwell
[quote]原帖由 [i]周瑜[/i] 于 2010-6-1 03:19 发表
是重复数据。其实这完全是干扰条件，只是手头拿到的数据就有重复的。 [/quote]
乍想一下，似乎除法挺复杂，但是只用减法差不多要O(ti)了。有空先写个减法的试试，除法的慢慢想。另外，第3题用怎么用二分法能给讲讲不？我没想出来对谁二分。
2010-6-1 10:47
周瑜
把 Group 数组复制一遍，附在原数组后面，即：
Group[N...2N-1] = Group[0...N-1]
定义 S[i] 为 Group 数组前 i 项之和，则 S 为递增数组
S[0] = 0
S[i] = S[i-1] + Group[i-1]
计算以每组起始登车时可装载的最后一组时，可在 S[i] 到 S[i+N] 之间使用二分法，使用 upper_bound 函数找到第一个大于 S[i]+k 的，指针减一即为最后上车的一组。
其实还是双指针的方法好，只遍历一次。两个指针一个指向起始位置，一个指向截止位置，每次起始位置后移1，截止位置不动或者后移若干。然后移动时很容易算出实际上车人数。
[color=Silver][[i] 本帖最后由 周瑜 于 2010-6-1 08:01 编辑 [/i]][/color]
2010-6-3 18:44
Maxwell
[quote]原帖由 [i]周瑜[/i] 于 2010-5-25 04:44 发表
02 太空观测[/quote]
尝试写了一个大数类，只实现了减法，发现效率实在太低，除法没时间写了。下面的代码是gcc+gmp写的，恐怕不是出题的原意了。
[code]
#include <fstream>
#include <string>
#include <vector>
#include <gmp.h>
#include <gmpxx.h>
typedef std::vector<mpz_class> TMpzVector;
mpz_class Calc1(TMpzVector const& Data)
{
mpz_class MinTime = Data[0];
mpz_class MinGcd = 0;
size_t const DataLen = Data.size();
for (size_t i = 1; i < DataLen; ++i)
{
mpz_class Diff = abs(Data[0] - Data[i]);
if (Diff > 0)
{
if (0 == MinGcd)
{
MinGcd = Diff;
}
else
{
mpz_class Gcd;
mpz_gcd(Gcd.get_mpz_t(), Diff.get_mpz_t(), MinGcd.get_mpz_t());
if (Gcd < MinGcd)
{
MinGcd = Gcd;
}
}
}
if (Data[i] < MinTime)
{
MinTime = Data[i];
}
}
mpz_class R = MinTime % MinGcd;
mpz_class Ret;
if (0 == R)
{
Ret = 0;
}
else
{
Ret = MinGcd - R;
}
return Ret;
}
int main()
{
std::ifstream In("in.txt");
std::string Line;
int T = 0;
FILE* Out = fopen("testout.txt", "w");
In >> T;
for (int i = 0; i < T; ++i)
{
int N = 0;
std::string Num;
TMpzVector Data;
In >> N;
for (int j = 0; j < N; ++j)
{
In >> Num;
Data.push_back(mpz_class(Num));
}
mpz_class Result = Calc1(Data);
gmp_fprintf(Out, "Case #%d: %Zd\n", i + 1, Result.get_mpz_t());
}
return 0;
}
[/code]
2010-6-4 01:52
阿尔法孝直
[quote]原帖由 [i]周瑜[/i] 于 2010-5-25 04:46 发表
甲乙面前有两堆豆子，每人轮流取，每次只能从多的那堆取少的那堆豆子数量的[color=Red]整数[/color]倍，把其中一堆取完的输掉游戏。
例如两堆豆子分别为 12 和 51，
甲先取，从 51 中拿掉 12 的 3 倍 36 个，剩余数量为 12 和 ... [/quote]
这个整数是否包括0？
2010-6-4 02:03
周瑜
没什么原意不原意的，当然要利用各种资源把题做出来。出题者并没有限定语言，有些语言如 Java 和 Python 有内置的大数计算库，自然也可以用 GMP 这样的外置库。
我自己当时花了好几个小时写了个大数类。为了实现除法，写了长整数输入、输出、加法、减法、比较，32位乘长整数，长整数除以长整数但商是32位的试商。除了长整数乘长整数外，几乎把四则运算都实现了，后来看见别人都简单的完成了，才开始学习用库。
-------------------------------------------------------------
不包括0，否则游戏无法完成，我把题修改一下。
2010-6-4 02:10
阿尔法孝直
[quote]原帖由 [i]周瑜[/i] 于 2010-5-25 04:46 发表
输入格式：
第一行为测试样本数量 T ，以下 T 行每行为一个样本，包含以空格分隔的四个整数 A1，B1，A2，B2。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为先手必胜 (A,B) 对的个数。
限制条件：
1 ≤ T ≤ 100
1 ≤ A1 ≤ A2 ≤ 1,000,000
1 ≤ B1 ≤ B2 ≤ 1,000,000
示例输入：
3
5 5 8 8
11 11 2 2
1 6 1 6
示例输出：
Case #1: 0
Case #2: 1
Case #3: 20
[/quote]
样本2：A1=11，B1=11，A2=2，B2=2……好奇怪，A1>A2，B1>B2
样本3：A1=1，B1=6，A2=1，B2=6……这样看来只有1组，怎么结果会是20组呢？
[color=Silver][[i] 本帖最后由 阿尔法孝直 于 2010-6-4 02:11 编辑 [/i]][/color]
2010-6-4 02:17
周瑜
[quote]原帖由 [i]阿尔法孝直[/i] 于 2010-6-3 14:10 发表
样本2：A1=11，B1=11，A2=2，B2=2……好奇怪，A1>A2，B1>B2
样本3：A1=1，B1=6，A2=1，B2=6……这样看来只有1组，怎么结果会是20组呢？ [/quote]
题目又错了，再改，输入顺序应该是A1，A2，B1，B2
2010-10-23 18:12
zhaohaidao
[quote]原帖由 [i]阿尔法孝直[/i] 于 2010-5-29 00:51 发表
从右往左数，最右边是第一个开关。
一开始是：
灯—00000000……00000000—电源，第一个断开的开关是通电的，那么按一下按钮之后，最后一个开关状态翻转：
灯—00000000……00000001—电源，此时电流通过 ... [/quote]
000000000000000000100 的情况下，此时电流到了第四个开关，题目说按一下按钮可以让所有通电开关翻转一次，电流到了第四个开关，那第三个跟第四个开关变不变呢？
:hz1026::hz1026::hz1026:
2010-11-26 20:35
xihai
作记号，等大大
2010-11-27 12:09
Maxwell
[quote]原帖由 [i]zhaohaidao[/i] 于 2010-10-23 18:12 发表
000000000000000000100 的情况下，此时电流到了第四个开关，题目说按一下按钮可以让所有通电开关翻转一次，电流到了第四个开关，那第三个跟第四个开关变不变呢？
:hz1026::hz1026::hz1026: [/quote]
0100的情况下电流到不了第4个开关只到第1个开关，0111的时候电流才到第4个开关。
2010-12-19 00:57
周瑜
01 链式开关
每个开关翻转的条件是前面所有的开关全部连通，此时按下按钮，此开关可以翻转。如果用二进制数表示，1表示连通，0表示断开，最右侧的数位表示直接与电源相连的开关，则状态
1 0 0 1 0 1 1 1
表示开关1, 2, 3, 5, 8已连通，再次按下按钮时，开关1, 2, 3, 4将翻转，变成
1 0 0 1 1 0 0 0
注意，这种翻转与二进制的增"1"恰好相同。按下 x 次开关后，所有开关表示的整数恰好是 x 的二进制形式。
因此，判断按下 K 次按钮之后，第 N 个开关后的灯泡是否会亮，等同于判断整数 K 的低 N 位是否全部为1，程序可以简单的写出。
2010-12-19 07:25
周瑜
02 太空观测
本题的两个要点在于最大公约数和长整数计算。
1.由于已知某事件在过去发生时刻 ti (1≤i≤N)，因此该事件的最大正周期为 GCD(|t2-t1|, |t3-t2|, ..., |tN-t(N-1)|)。其中函数GCD(...)表示最大公约数。若 ti=t(i+1)，则不参与计算。
多个数的最大公约数可以通过逐次结合运算求得：
GCD(a, b, c, d) = GCD(GCD(GCD(a,b), c), d)
因此，只要写出求两个正整数最大公约数的方法，就可以求出多个正整数的最大公约数。
以此最大公约数为周期 T ，便可求得该事件下次发生时刻为：(T - ti MOD T) MOD T
2.最大公约数求法，辗转相除法
假设算式 GCD(a,b) 中 a>b，那么使用 a MOD b 代替参数中的 a，可得到相同的结果。GCD(a,b) = GCD(a MOD b, b)
即使用参数中大数除以小数的余数代替大数，然后反复交替相除取余，直到其中一参数为0，即得到答案。
递归代码
[code]function GCD(a, b)
if b = 0
return a
else
return GCD(b, a mod b)[/code]
非递归代码
[code]function GCD(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a[/code]
3.以上 ti 及最大公约数函数的参数 a,b 都是长整数，不能使用普通的四则运算方法，只能自定义一个长整数类，然后重载各种运算操作符。
由于限制了 ti 最大值不超过 10^50，因此可以使用固定长度的结构，而不用设计动态分配内存，可以简化程序。
我的代码中，实现的方法有：
长整数输入(普通整数和字符串转化为长整数)
长整数输出(屏幕输出和长整数转化为字符串)
长整数比较(大于，小于，等于)
长整数加法(加长整数或者短整数)
长整数减法(减长整数或者短整数)
长整数乘法(乘以短整数)
长整数除法(除以长整数)
长整数取模(除以长整数)
此外，长整数除法和取模中需要用到试商函数，其目的为求出商为短整数的两个长整数相除结果，可以使用二分法实现。
2010-12-25 07:50
周瑜
03 主题公园
本题题意清晰，直接使用枚举法模拟游客登车过程即可得到结果，可惜这种方法复杂度太高，为O(R∙N)。
当R = 10^8，N = 10^3 时，R∙N = 10^11，超出计算范围。
本题解法可以分为两步进行优化。第一步，求出以每个小组为登车第一小组时，最后登车小组序号和总登车人数，这样，此后只需要O(1)时间即可模拟一次登车过程，复杂度降为O(R)；第二步，找出是否存在周期，并根据登车周期求出结果，复杂度进一步降为O(N)。
一、先来看第一步，可以有O(N^2)，O(NlogN)，O(N)多种方法。
1. 每次登车组数不会超过 N 组，因此直接使用枚举法模拟登车过程，复杂度为O(N^2)。
2. O(NlogN)算法：
把 g 数组复制一遍，附在原数组后面，即：
g[N...2N-1] = g[0...N-1]
定义 S[i] 为 g 数组前 i 项之和，则 S 为递增数组
S[0] = 0
S[i] = S[i-1] + g[i-1]
计算以每组起始登车时可装载的最后一组时，可在 S[i] 到 S[i+N] 之间使用二分法，最后一个不大于 S[i]+k 的项即为最后上车的一组。
3. O(N)算法：
双指针法。第一个指针指向每次登车的第一组，第二个指针指向可装载的最后一组。每当第一个指针向后挪时，第二个指针或者停留原地，或者向后挪动一位或多位。因此，第二个指针不可能反向向前挪动。
第一个指针最多挪动 N 位，第二个指针最多挪动 2N-1 位，因此这复杂度为 O(N)。
二、寻找周期。
所谓周期，指的是从某时刻起，在过山车运行一次或多次后，原来首先登车的一组再次首先登车，此后所有登车情况完全与上一周期相同。
根据鸽巢原理，当运行次数 R 大于游客组数 N 时，周期必然存在。
若 R≤N，可直接得到结果。
若 R>N，可以模拟前 N+1 次登车过程，找出周期长度和开始位置，并求出周期数。
总登车人数 = 周期前登车人数 + 每周期登车人数*周期数 + 周期后登车人数
由于周期长度及周期前、周期后的运行次数均不大于 N，因此这一步和总的算法复杂度也为 O(N)。
[color=Silver][[i] 本帖最后由 周瑜 于 2010-12-25 12:36 编辑 [/i]][/color]
2010-12-26 21:24
trichromatic
[算了 考虑了一下 还是不贴了 以免打扰大家思维的乐趣。]
贴几个我自己的代码。
07 创建目录
#include<stdio.h>
#include<map>
#include<string>
using namespace std;
class folder
{
public:
map<string,folder*> Map;
folder(){}
} *root,*p,*q;
int main()
{
int _,t,n,m;
char s[110000];
scanf("%d",&_);
for(t=1; t<=_; t++)
{
scanf("%d%d",&n,&m);
int ans=0;
root=new folder();
for(int i=0; i<n+m; i++)
{
scanf("%s",s);
p=root;
for(int j=0;;)
{
string w="";
for(j++; s[j]!=0 && s[j]!='/'; j++)
w+=s[j];
if(p->Map.find(w)==p->Map.end())
{
p->Map[w]=new folder();
if(i>=n)
ans++;
}
p=p->Map[w];
if(s[j]==0)break;
}
}
printf("Case #%d: %d\n",t,ans);
}
return 0;
}
09 绝对序号
#include<stdio.h>
#define mod 100003
long long int dp[510][510],ans[510];
long long int c[510][510];
void init()
{
for(int i=0; i<=500; i++)
for(int j=0; j<=i; j++)
if(j==0 || j==i)
c[i][j]=1;
else
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
for(int i=2; i<=500; i++)
{
dp[i][1]=ans[i]=1;
for(int j=2; j<i; j++)//the rank of i in that set
{
for(int k=1; k<j; k++)//the rank of j in that set
dp[i][j]+=dp[j][k]*c[i-j-1][j-k-1]%mod;
dp[i][j]%=mod;
ans[i]+=dp[i][j];
}
ans[i]%=mod;
}
}
int main()
{
int _,t,n;
init();
scanf("%d",&_);
for(t=1; t<=_; t++)
{
scanf("%d",&n);
printf("Case #%d: %I64d\n",t,ans[n]);
}
return 0;
}
18 修建栅栏
#include<stdio.h>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
int n;
long long int a[100],l,g;
long long int gcd(long long int x,long long int y){return y?gcd(y,x%y):x;}
int dp[100010];
priority_queue<pair<int,long long int> > q;
int main()
{
int t,_;
scanf("%d",&_);
for(t=1; t<=_; t++)
{
scanf("%I64d%d",&l,&n);
g=0;
for(int i=0; i<n; i++)
{
scanf("%I64d",&a[i]);
g=gcd(g,a[i]);
}
sort(a,a+n);
printf("Case #%d: ",t);
if(l%g)
{
puts("IMPOSSIBLE");
continue;
}
memset(dp,-1,sizeof(dp));
dp[0]=0;
q.push(make_pair(0,0));
n--;
int u=a[n];
while(!q.empty())
{
int c=q.top().first;
long long int l1=-q.top().second;
q.pop();
if(dp[c]!=l1)continue;
for(int i=0; i<n; i++)
{
long long int l2=c+a[i],cost=dp[c]+1;
if(l2>=u)l2-=u,cost--;
if(dp[l2]==-1 || dp[l2]>cost)
{
dp[l2]=cost;
q.push(make_pair((int)(l2),-dp[l2]));
}
}
}
long long int w=l%a[n];
long long int ans=dp[w]+(l-w)/a[n];
printf("%I64d\n",ans);
fprintf(stderr,"%d\n",t);
}
return 0;
}
[color=Silver][[i] 本帖最后由 trichromatic 于 2010-12-26 22:00 编辑 [/i]][/color]
2011-4-3 04:31
Maxwell
02 太空观测
[font=Courier New][code]
import re
def gcd(x, y) :
while 0 != y :
x, y = y, x % y
return x
def gcd_list(l) :
while len(l) > 1 :
x = l.pop()
y = l.pop()
l.append(gcd(x, y))
return l[0]
with open('in.txt') as in_file :
x = in_file.readline()
index = 0
for line in in_file :
index += 1
l = re.findall(' \d+', line)
g = gcd_list(list({abs(int(l[0]) - int(i)) for i in l if i != l[0]}))
print('Case #{}: {}'.format(index, (g - int(l[0]) % g) % g))
[/code][/font]
[color=Silver][[i] 本帖最后由 Maxwell 于 2011-4-3 04:34 编辑 [/i]][/color]
2011-4-3 12:27
Maxwell
04 翻转积木
[font=Courier New][code]
def get_list(file) :
[n, k] = map(int, file.readline().split(' '))
l = []
for i in range(0, n) :
l.append([ch for ch in file.readline().strip()])
return n, k, l
def turn_list(l) :
n = len(l)
for i in range(0, n) :
for j in range(n - 1, -1, -1) :
if '.' == l[i][j] :
for k in range(j - 1, -1, -1) :
if '.' != l[i][k] :
l[i][j] = l[i][k]
l[i][k] = '.'
break
def find_h(l, x, y, ch, n) :
for i in range(x + 1, x + n) :
if ch != l[y][i] :
return False
return True
def find_v(l, x, y, ch, n) :
for i in range(y + 1, y + n) :
if ch != l[i][x] :
return False
return True
def find_lt_rb(l, x, y, ch, n) :
for i in range(1, n) :
if ch != l[y + i][x + i] :
return False
return True
def find_rt_lb(l, x, y, ch, n) :
for i in range(1, n) :
if ch != l[y + i][x - i] :
return False
return True
def find(l, x, y, ch, n) :
size = len(l)
d = {'h': False, 'v': False, 'r': False, 'l': False}
if size - y >= n :
d['v'] = True
if size - x >= n :
d['h'] = True
d['r'] = True
if x >= n - 1 :
d['l'] = True
else :
if size - x >= n :
d['h'] = True
r = False
if d['h'] :
r = find_h(l, x, y, ch, n)
if d['v'] and not r :
r = find_v(l, x, y, ch, n)
if d['r'] and not r :
r = find_lt_rb(l, x, y, ch, n)
if d['l'] and not r :
r = find_rt_lb(l, x, y, ch, n)
return r
def main() :
with open('in03.txt') as in_file :
t = int(in_file.readline())
for i in range(1, t + 1) :
n, k, l = get_list(in_file)
turn_list(l)
r = False
b = False
for y in range(0, n) :
for x in range(0, n) :
if 'B' == l[y][x] and not b :
b = find(l, x, y, 'B', k)
elif 'R' == l[y][x] and not r :
r = find(l, x, y, 'R', k)
if r and b :
print('Case #{}: Both'.format(i))
elif r :
print('Case #{}: Red'.format(i))
elif b :
print('Case #{}: Blue'.format(i))
else :
print('Case #{}: Neither'.format(i))
main()
[/code][/font]
[color=Silver][[i] 本帖最后由 Maxwell 于 2011-4-3 21:05 编辑 [/i]][/color]
2011-4-3 22:33
Maxwell
07 创建目录
[font=Courier New][code]
def add(dir_tree, path) :
l = path.split('/')
d = dir_tree
count = 0
for item in l :
if None == d.get(item) :
d[item] = {}
count += 1
d = d[item]
return count
def main() :
with open('in07.txt') as in_file :
T = int(in_file.readline())
for i in range(1, T + 1) :
dir_tree = {'': {}}
count = 0
[N, M] = map(int, in_file.readline().split(' '))
for j in range(0, N) :
add(dir_tree, in_file.readline().strip())
for j in range(0, M) :
count += add(dir_tree, in_file.readline().strip())
print('Case #{}: {}'.format(i, count))
main()
[/code][/font]