百度之星2009程序设计大赛 初赛第一场试题

2009年5月30日19：00-22:30（由于第二题出错，比赛时间延长半小时），2008百度之星大赛在线资格赛（初赛）展开。百度爱好者（Baiduer.com.cn）在第一时间给大家带了初赛题目。第一场初赛共四题，分别是火柴游戏(250分)、电子商务平台商品推荐问题 （300分）、争车位（300分）和葫芦娃 （350分），总计1200分。

1.火柴游戏(250分)

题目描述

在百度，同事们之间喜欢交流游戏。其中，火柴游戏是一个比较经典的例子。游戏的规则很简单：恰好移动一根火柴，使等式成立。如下面的等式可以变成3+6=9（还有其他解）：移动哪一根火柴能使等式成立?

下面是所有火柴数字的样子

请你写一个程序，找出所有的规范解。所谓规范是指：

*只能改变数字，不能改变符号；

*数字和符号的组成方式必须严格的和图示的一样（减号由一根火柴组成）；

*新等式必须形如a+b=c或a-b=c，其中a、b、c都是不含前导0的非负整数。

当然，最重要的是：新的等式必须在数学上成立。

输入格式

输入仅一行，为一个格式为a+b=c或a-b=c的表达式，其中a、b、c均为不含前导0的非负整数。表达式长度不超过100，且不含空白字符。因此，加号/减号紧跟在a的后面、b紧跟在加号/减号的后面、等号紧跟在b的后面、c紧跟在等号的后面。

输出格式

输出所有规范解，按字典序输出（请注意：输出顺序不对将不得分）。无解时，仅输出一行-1。

样例输入1

9+5=9

样例输出1

3+5=8

3+6=9

样例输入2

1+1=2

样例输出2

-1

测试数据

共10个测试点，基本参数如下表：

测试点编号	表达式的长度
1-2	1-10
3-4	10-25
5-6	26-50
7-10	51-100

裁判问答：

Q:第一题的表达式长度不是只有5吗? A:可以多位整数

Q：把某根移出来再移到原来的位置上算不算移动? A：不算

2. 电子商务平台商品推荐问题 （300分）

题目描述

百度网络交易平台（“百度有啊”）是建立在百度旗下独有的搜索技术、强大社区资源基础上的中文互联网领域最具规模的网上个人C2C交易平台。伴随着“百度有啊”的成长，“有啊”的顾客也蜂拥而至；面对如此大量的用户，如何把平台上数以千万计的商品按一定的规则推荐给他们以促成交易，是“百度有啊”面临的重要问题。

在本题中，假设有M个用户和N种产品，每个用户的浏览历史可以用一个N维特征向量 X描述：Xi=1当且仅当该用户曾经浏览过商品i。如果用户A和用户B曾浏览过(部分)相同的商品，我们说用户A和用户B相似；如果用户A和用户B相似，或者用户A和一个“与用户B相似”的用户相似，则需要把用户A和用户B划分到同一个用户群。该用户群中所有用户的特征向量的“按位或” 便是整个用户群的特征向量——它表示至少被其中一个用户浏览过的商品集合。

每当一个新用户到来时，可以计算出它和所有用户群之间的相似度。假定他的特征向量为A，用户群的特征向量为B，则：

其中计算特征向量模长时使用的是二范数，即所有维度数值的平方和的算术平方根。

接下来，我们应找出该用户最接近的用户群，并从该用户群购买过的商品中选三个商品进行推荐。一般来说，一个商品被购买的次数越多，就越应该被优先推荐（若购买次数相同，优先推荐id值小的商品），但为了避免马太效应，我们需要做一个特殊处理：不推荐最畅销的商品（如果有多个商品的购买次数都是最多的，则它们都不应该被推荐, 为简单计, 如果所有商品的购买次数都一样的话就都不推荐了）。另外，推荐给用户的商品不能是他已经购买过的商品。

如果从最接近的用户群中无法推荐出三个商品，应从次接近的用户群购买的商品中以相同的规则补充，以此类推，直到选出三个推荐商品，或者无法选出更多商品。

测试数据保证任何一个用户不会跟两个不同用户群的相似度相同，因此商品推荐的结果总是惟一的。

注意：如果用户浏览记录跟某用户群的相似度为0，则在任何情况下都不从该用户群购买的商品中推荐。

输入格式

第1行：M、N，分别是平台用户数和商品总数。0 < M,N <= 100 000

第2行：K，表示接下来有K行记录。0 < K <= 100 000

第3~K+2行，每一行是一次用户的浏览-购买记录，记录格式为：

uid i1,i2, …,ip b1,b2,…,bq

其中uid是不超过M-1的非负整数，代表用户id。i为本次浏览的商品id集合（无重复元素，元素顺序无意义），而b为该用户在此次浏览后购买的商品集合（无重复元素，元素顺序无意义）。i中的每个元素均为不超过N-1的整数，b是i的子集。q <= p <= 50。注意：同一个用户ID可以对应多条记录

第K+3行：Q，表示接下来有Q次查询。0 < Q <= 125

第K+4~K+Q+3行：每一行是一次用户的浏览记录，格式为

uid i1,i2, …,ip

含义类似于浏览-购买记录。注意：用户群划分方式完全取决于第3行开始的K条记录。这里的查询不会导致用户群划分方式的变化（在实际的系统中，用户群数据也是定期更新，而非实时修改）。

输出格式

对每个查询输出一行，为推荐的最多三个商品的id（为不超过N-1的非负整数），按推荐度降序排列。如果没有任何可推荐的商品，输出NONE；如果有商品可推荐，但不足三个，应全部输出。

样例输入

9 12

8

0 0,1,2 1

1 3,4,5 3,4

2 1,5 1

3 6,7 6,7

4 8,9 8

5 8,10 8,10

0 11 11

8 6 6

3

6 0,1,2

1 0,1,2,6

3 8,9

样例输出

3 4 11

11 7

10

PS：原样例有错，于22：45分修正样例

样例解释

首先对购买历史进行预处理形成用户群，然后对每个用户群购买的商品按购买次数进行排序，结果如下：

用户群ID	用户ID	浏览过的商品ID集合	购买的商品ID
0	0,1,2	0,1,2,3,4,5,11	1(2次),3,4,11
1	3,8	6,7	6(2次),7
2	4,5	8,9,10	8(2次),10

接下来处理查询。

输入：0,1,2 输出：3,4,11

此浏览记录与用户群0最接近。根据规则推荐3,4,11 （1是最畅销商品，不推荐；对于被购买数量相同的商品3和4，优先推荐id值小的商品）

输入：0,1,2,6 输出：7,11

此浏览记录与用户群1最接近，根据规则推荐7（6是最畅销商品，不推荐）；由于不足三个商品，从次接近的用户群0中推荐，推荐11 （1是最畅销商品，3、4是购买过的商品）；仍然不足三个商品，但是已无更多商品可以推荐。

输入：8,9 输出：10

此浏览记录与用户群2最接近，根据规则推荐10；不足三个商品，但是已无更多商品可推荐。

测试数据

共20个测试点，基本参数如下表：

测试点编号	M	N	K	Q
1	<=100	<=100	<=100	<=100
2	<=100	<=100	<=100	<=100
3	<=100	<=100	<=100	<=100
4	<=100	<=100	<=100	<=100
5	<=100	<=100	<=100	<=100
6	<=1000	<=1000	<=1000	<=100
7	<=1000	<=1000	<=1000	<=100
8	<=1000	<=1000	<=1000	<=100
9	<=1000	<=1000	<=1000	<=100
10	<=1000	<=1000	<=1000	<=100
11	10000	10000	10000	100
12	20000	20000	20000	100
13	30000	30000	30000	100
14	40000	40000	40000	100
15	50000	50000	50000	100
16	60000	60000	60000	100
17	70000	70000	70000	100
18	80000	80000	80000	100
19	90000	90000	90000	100
20	100000	100000	100000	100

3.争车位（300分）

题目描述

争车位是目前SNS网站上比较热门的游戏之一。假如小明有N个好友和M辆车。每个好友都有K个车位。这些车位可能停放了小明的车，也可能停放了其它人的车，还能没有停任何车辆（空车位）。在当前状态中，小明的M辆车全停放在他的好友的车位上。

任务一：考虑如下的移车规则：

1.必须按一定顺序依次移动自己的车，而不能移动别人的车。

2.每辆车只可以移动一次。

3.车只能从原来的位置移到空车位处，不能移动到一个已停放了车的车位（无论这辆车是谁的）。移动后，原来的位置就成了空车位。

4.只能跨好友移车。也就是说，一辆车不能从某好友的车位移到这个好友的另一车位。

请帮助小明把他的所有M辆车都移动一遍。

任务二：考虑如下的移车规则：

1.每个车位都对应一个金额。当小明把一辆车最终停在某个车位时，将会得到该车位对应的金额。

2.不一定需要把所有车都移一遍，但只有移动前后处于不同车位的车才能得到对应的金额。

3.可以把自己的车开到附近的空地上（那里足以停下他所有的车）作为临时中转。因此车不必依次移动，每辆车也可以多次移动。但请注意：所有移动结束之后，每个车位最多只能停一辆车。

4.和任务一相同的是：仍不许动其他人的车，且每辆车在移动之前和所有移动结束后所在的车位仍必须属于不同好友。特别地，不许最终把一辆车停到用于中转的那个空地上。

请帮助小明获得最大的总金额。

输入格式

第1行包含一个整数T，即任务编号（T=1或2）。

第2行包含两个整数N、K，分别表示小明的好友数和每个好友的车位数。以下N行每行有一个包含K个字符的字符串，描述每个好友当前车位的状态。其中‘#’表示该车位停放的是小明的车；‘*’表示该车位停放的是其它人的车；‘.’表示该车位是空车位。

如果T=1，输入到此结束；否则接下来的N行每行包含K个不超过100的整数，分别表示每个车位对应的金额。

输入据至少有一辆小明的车。

输出格式

如果T=1，输出任意可行的移车方案。假如有M个步骤，则第一行输出M，紧接着M行表示M步的具体内容。格式为：(x1,y1)->(x2,y2)，表示把第x1个好友第y1个车位上的车移到第x2个好友的第y2个车位。如果无解，输出-1。

输入T=2，输出一个数字，表示最多的金额总数。

样例输入1

1

34

##*.

.#**

****

样例输出1

3

(0,0)->(1,0)

(1,1)->(0,3)

(0,1)->(1,1)

样例输入2

1

34

##*#

.#**

****

样例输出2

-1

样例输入3

2

22

#*

#*

21

12

样例输出3

3

测试数据

共20个测试点，基本参数如下表：

测试点编号	T	N	K
1	1	3	6
2	1	10	10
3	1	10	10
4	1	3	4
5	1	100	100
6	1	10	100
7	1	10	100
8	1	10000	100
9	1	100000	100
10	1	100000	100
11	2	2	4
12	2	10	4
13	2	5	5
14	2	3	4
15	2	20	4
16	2	50	10
17	2	50	10
18	2	10	10
19	2	50	10
20	2	50	10

4. 葫芦娃 （350分）

题目描述

蝎子精和蛇精为祸人间，葫芦七兄弟准备与之决一死战。不幸的是，七弟不慎被两只妖精抓住，困在了蛇蝎山的囚笼里，其余六兄弟必须尽快去营救。二娃使用千里眼，查看到七弟被囚的位置，但蛇蝎山地势复杂，机关遍布，如何才能又快又安全的把七弟救出来呢？于是，六兄弟请您来帮忙了。

在二娃的帮助下，大家先绘制了一张蛇蝎山的地图，并把能安全停留的地方以点标记。你很快就发现，这些安全点组成了一个六邻接图——每个点都与左上、左、左下、右下、右、右上六个点等距。于是，你以其中两条坐标轴：“左——右”和“左上——右下”，给各点设置坐标（见图1）。只要把囚笼的六个邻接点都占了，然后六兄弟一起施法，就能把七弟营救出来。

图1. 六邻接图及坐标

虽然已经有了地图，但怎样走才能最快的把七弟救出来呢？葫芦兄弟告诉你，他们有两种移动方式：

1、跑步。可在一单位时间移动一单位距离，即从一个点移动到某个邻接点（见图2）。

图2. 跑步移动示意图

2、翻跟头。可在一单位时间沿着一个坐标轴方向移动多个单位距离，但其飞过的每个点上都必须有葫芦兄弟站在那里施法。例如，在点 (0,0)和点(1,1)都有葫芦娃，那么位于点(2,2)的葫芦娃便可在兄弟的帮助下，沿着“左下——右上”坐标轴直接翻跟头到点(-1,-1)（见图 3）。

图3. 翻跟斗移动示意图

另外，为了不引起妖精的注意，每一单位时间最多只有一个葫芦娃能移动，且每个点上只能站一个葫芦娃。由于葫芦兄弟心灵相通，被囚的七弟也能为兄弟施法。

六个葫芦娃的出发位置为(0,0)，(1,0)，(2,0)，(1,1)，(2,1)，(2,2)。如果按照最快的方案，六兄弟需要多长时间才能救出七弟呢？

输入格式

输入仅包含一行，包含两个整数X, Y，表示囚禁七弟的位置。只要把此点的六个邻接点都占了，就能把七弟救出来。 (X,Y)不会和上述六个出发点重合。0 <= X, Y < 7

输出格式

输出一行，包含一个整数，即营救的最短时间。

样例输入1

3 1

样例输出1

4

样例输入2

3 4

样例输出2

8

样例输入3

0 5

样例输出3

14

测试数据

共30组数据，输出结果近似在[0,16]内均匀分布。

注意事项

•请不要把离线计算的结果保存在源代码中（例如，直接把答案保存在ans[X][Y]中，读取输入后直接输出），否则本题得0分.

•请不要特判/猜测/随机打印结果，否则本题得0分。

•今年新增比赛规则: 公布所有选手的源代码。关于运行时限: 每题均有两个时限T1/T2。如果程序输出正确，且程序运行时间为T，则T<=T1时，该测试点得分为100%, T>=T2时，该测试点得分为0%。T1<T<T2时，该测试点得分为(T2-T)/(T2-T1) * 100%。 T1根据参考程序的运行速度和题目难度设定，T2通常取T1的4倍到8倍之间。 具体的T1,T2不公布。