鸟语求翻译……

yangff

GoogleCodeJam的题目……表示没玩过这个游戏看不懂题目求翻译……

Introduction

Magicka™ is an action-adventure game developed by Arrowhead Game Studios. In Magicka you play a wizard, invoking and combining elements to create Magicks. This problem has a similar idea, but it does not assume that you have played Magicka.

Note: "invoke" means "call on." For this problem, it is a technical term and you don't need to know its normal English meaning.

Problem

As a wizard, you can invoke eight elements, which are the "base" elements. Each base element is a single character from {Q, W, E, R, A, S, D, F}. When you invoke an element, it gets appended to your element list. For example: if you invoke W and then invoke A, (we'll call that "invoking WA" for short) then your element list will be [W, A].

We will specify pairs of base elements that combine to form non-base elements (the other 18 capital letters). For example, Q and F might combine to form T. If the two elements from a pair appear at the end of the element list, then both elements of the pair will be immediately removed, and they will be replaced by the element they form. In the example above, if the element list looks like [A, Q, F] or [A, F, Q] at any point, it will become [A, T].

We will specify pairs of base elements that are opposed to each other. After you invoke an element, if it isn't immediately combined to form another element, and it is opposed to something in your element list, then your element list will be cleared.

For example, suppose Q and F combine to make T. R and F are opposed to each other. Then invoking the following things (in order, from left to right) will have the following results:

QF → [T] (Q and F combine to form T)
QEF → [Q, E, F] (Q and F can't combine because they were never at the end of the element list together)
RFE → [E] (F and R are opposed, so the list is cleared; then E is invoked)
REF → [] (F and R are opposed, so the list is cleared)
RQF → [R, T] (QF combine to make T, so the list is not cleared)
RFQ → [Q] (F and R are opposed, so the list is cleared)
Given a list of elements to invoke, what will be in the element list when you're done?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line, containing the following space-separated elements in order:

First an integer C, followed by C strings, each containing three characters: two base elements followed by a non-base element. This indicates that the two base elements combine to form the non-base element. Next will come an integer D, followed by D strings, each containing two characters: two base elements that are opposed to each other. Finally there will be an integer N, followed by a single string containing N characters: the series of base elements you are to invoke. You will invoke them in the order they appear in the string (leftmost character first, and so on).

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is a list in the format "[e0, e1, ...]" where ei is the ith element of the final element list. Please see the sample output for examples.

Limits

1 ≤ T ≤ 100.
Each pair of base elements may only appear together in one combination, though they may appear in a combination and also be opposed to each other.
No base element may be opposed to itself.
Unlike in the computer game Magicka, there is no limit to the length of the element list.

Small dataset

0 ≤ C ≤ 1.
0 ≤ D ≤ 1.
1 ≤ N ≤ 10.
Large dataset

0 ≤ C ≤ 36.
0 ≤ D ≤ 28.
1 ≤ N ≤ 100.
Sample


Input
       
Output

5
0 0 2 EA
1 QRI 0 4 RRQR
1 QFT 1 QF 7 FAQFDFQ
1 EEZ 1 QE 7 QEEEERA
0 1 QW 2 QW
Case #1: [E, A]
Case #2: [R, I, R]
Case #3: [F, D, T]
Case #4: [Z, E, R, A]
Case #5: []
Magicka™ is a trademark of Paradox Interactive AB. Paradox Interactive AB does not endorse and has no involvement with Google Code Jam.

and

1. Small input
   
2. 10 points       
   
3. Solve D-small
   
4. You may try multiple times, with penalties for wrong submissions.
   
5. Large input
   
6. 20 points       
   
7. You must solve the small input first.
   
8. You will have 8 minutes to solve 1 input file. (Judged after contest.)
   
9. Problem
   
10. 
    
11. Goro has 4 arms. Goro is very strong. You don't mess with Goro. Goro needs to sort an array of N different integers. Algorithms are not Goro's strength; strength is Goro's strength. Goro's plan is to use the fingers on two of his hands to hold down several elements of the array and hit the table with his third and fourth fists as hard as possible. This will make the unsecured elements of the array fly up into the air, get shuffled randomly, and fall back down into the empty array locations.
    
12. 
    
13. Goro wants to sort the array as quickly as possible. How many hits will it take Goro to sort the given array, on average, if he acts intelligently when choosing which elements of the array to hold down before each hit of the table?
    
14. 
    
15. More precisely, before each hit, Goro may choose any subset of the elements of the array to freeze in place. He may choose differently depending on the outcomes of previous hits. Each hit permutes the unfrozen elements uniformly at random. Each permutation is equally likely.
    
16. 
    
17. Input
    
18. 
    
19. The first line of the input gives the number of test cases, T. T test cases follow. Each one will consist of two lines. The first line will give the number N. The second line will list the N elements of the array in their initial order.
    
20. 
    
21. Output
    
22. 
    
23. For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the expected number of hit-the-table operations when following the best hold-down strategy. Answers with an absolute or relative error of at most 10-6 will be considered correct.
    
24. 
    
25. Limits
    
26. 
    
27. 1 ≤ T ≤ 100;
    
28. The second line of each test case will contain a permutation of the N smallest positive integers.
    
29. Goro has more than N fingers on each hand.
    
30. 
    
31. Small dataset
    
32. 
    
33. 1 ≤ N ≤ 10;
    
34. 
    
35. Large dataset
    
36. 
    
37. 1 ≤ N ≤ 1000;
    
38. 
    
39. Sample
    
40. 
    
41. 
    
42. Input
    
43.        
    
44. Output
    
45. 
    
46. 3
    
47. 2
    
48. 2 1
    
49. 3
    
50. 1 3 2
    
51. 4
    
52. 2 1 4 3
    
53. Case #1: 2.000000
    
54. Case #2: 2.000000
    
55. Case #3: 4.000000
    
56. 
    
57. Explanation
    
58. 
    
59. In test case #3, one possible strategy is to hold down the two leftmost elements first. Elements 3 and 4 will be free to move. After a table hit, they will land in the correct order [3, 4] with probability 1/2 and in the wrong order [4, 3] with probability 1/2. Therefore, on average it will take 2 hits to arrange them in the correct order. After that, Goro can hold down elements 3 and 4 and hit the table until 1 and 2 land in the correct order, which will take another 2 hits, on average. The total is then 2 + 2 = 4 hits.

复制代码

IamI

清空全列表。= =b QFE那组让我眼花了……

yangff

禾西 发表于 2011-5-8 04:51
回复 yangff 的帖子

列表中有互斥元素就會清空列表。兩個元素可合成先合成。合成反應先于互斥反應。 ...

郁闷了……我就是这样写的……
# Let combo_list contain all the combinations as 3-letter strs.
# Let opposed_list contain all the opposed elements as 2-letter strs.
# Let invoke be a str containing the elements to invoke.
combos = dict()
opposed = dict()
for x in combo_list:
  combos[x[0] + x[1]] = x[2]
  combos[x[1] + x[0]] = x[2]
for x in opposed_list:
  opposed.add(x[0] + x[1])
  opposed.add(x[1] + x[0])
# Now combos contains a mapping from each pair to the thing it
# creates.  If one of the combinations was "ABC", then
# combos["AB"] = "C" and combos["BA"] = "C".
# opposed is filled in a similar way.

element_list = []
for element in invoke:
  # If element_list isn't empty, the last element might combine
  # with the element being invoked.
  if element_list:
    last_two = element_list[-1] + element
    if last_two in combos:
      element_list[-1] = combos[last_two]
    continue

  # Now we iterate through element_list to see if anything there
  # is opposed to the element being invoked.
  wipe_list = False
  for e in element_list:
    if (e + element) in opposed:
      wipe_list = True
  if wipe_list:
    element_list = []
    continue

  # There was no combination and no erasing: just append the
  # element to the list.
  element_list.append(element)
妈的……无责任标程……

漫画朱古力

浏览器上应该有“翻译”那个图标吧{:nm_4:}


漫画朱古力于2011-5-8 08:27补充以下内容：
GoogleCodeJam的题目... ...表示没玩过这个游戏看不懂题目求翻译... ...
Introduction简介

Magicka™ is an action-adventure game developed by Arrowhead Game Studios. Magicka™是一款动作冒险游戏的游戏工作室开发的箭头。 In Magicka you play a wizard, invoking and combining elements to create Magicks.在Magicka你玩了一个向导，调用和组合元素，创造Magicks。 This problem has a similar idea, but it does not assume that you have played Magicka.这个问题也有类似的想法，但是它不会认为你发挥Magicka。

Note: "invoke" means "call on."注：“调用”的意思是“呼吁”。 For this problem, it is a technical term and you don't need to know its normal English meaning.对于这个问题，它是一个技术术语，你不需要知道它的正常英语的意思。

Problem问题

As a wizard, you can invoke eight elements, which are the "base" elements.作为一个向导，您可以调用八素，这是“基地”分子。 Each base element is a single character from {Q, W, E, R, A, S, D, F}.每个基地元素是一个从{强，瓦，é，俄，阿，硫，丁，己}单个字符。 When you invoke an element, it gets appended to your element list.当你调用一个元素，它就会被添加到你的元素列表。 For example: if you invoke W and then invoke A, (we'll call that "invoking WA" for short) then your element list will be [W, A].例如：如果你调用W和然后调用，（我们称之为“援引WA”的简称），那么你的元素名单将于[W时，]。

We will specify pairs of base elements that combine to form non-base elements (the other 18 capital letters).我们将指定相应的元素结合形成非基本元素（其他18个大写字母）对。 For example, Q and F might combine to form T. If the two elements from a pair appear at the end of the element list, then both elements of the pair will be immediately removed, and they will be replaced by the element they form.例如，Q和F可能结合起来，形成如果从一对的两个要素吨出现在元素列表的末尾，则无论对中的元素将被立即删除，它们将被替换的元素就形成。 In the example above, if the element list looks like [A, Q, F] or [A, F, Q] at any point, it will become [A, T].在上面的例子，如果元素列表，如[阿，问，f]或[一，男，问]看起来在任何时候，它会变成[其A，T]。

We will specify pairs of base elements that are opposed to each other.我们将指定的基础，是反对对方的元素对。 After you invoke an element, if it isn't immediately combined to form another element, and it is opposed to something in your element list, then your element list will be cleared.当你调用一个元素，如果它不会立即结合成另一种元素，它是反对你的元素列表中的东西，那么你的元素的列表将被清除。

For example, suppose Q and F combine to make T. R and F are opposed to each other.例如，假设Q和F相结合，使吨R和F反对对方。 Then invoking the following things (in order, from left to right) will have the following results:然后调用下面的事情（按顺序，由左到右）将有以下的结果：

QF → [T] (Q and F combine to form T)资历架构→[T]的（问及F相结合，形式为T）
QEF → [Q, E, F] (Q and F can't combine because they were never at the end of the element list together)优质教育基金→[问，E，F型]（Q和F可以不合并，因为他们在该元素的列表一起结束不要）
RFE → [E] (F and R are opposed, so the list is cleared; then E is invoked)的RFE→[英]（F和R分别是反对的，所以名单被清除，然后E是调用）
REF → [] (F and R are opposed, so the list is cleared)文献→[]（F和R分别是反对的，所以名单被清除）
RQF → [R, T] (QF combine to make T, so the list is not cleared) RQF→[001吨]（资历架构相结合，使笔，所以列表不清除）
RFQ → [Q] (F and R are opposed, so the list is cleared)询价→[问]（F和R分别是反对的，所以名单被清除）
Given a list of elements to invoke, what will be in the element list when you're done?鉴于一个元素列表来调用，究竟会在元素列表，当你正在做什么？

Input输入

The first line of the input gives the number of test cases, T. T test cases follow.输入的第一行给出了测试的个案数目，T检验例，随访吨。 Each test case consists of a single line, containing the following space-separated elements in order:每个测试案例包括一行，包含下列空间分隔，以便元素：

First an integer C, followed by C strings, each containing three characters: two base elements followed by a non-base element.首先是整数C，由C字符串，每个包含三个字符如下：两个基地由一个非基本元素之后的元素。 This indicates that the two base elements combine to form the non-base element.这表明，两个基本要素结合，形成了非基本元素。 Next will come an integer D, followed by D strings, each containing two characters: two base elements that are opposed to each other.下一步会附带一个整数d，由D弦，每个都包含两个字符如下：两个基础，是反对对方的元素。 Finally there will be an integer N, followed by a single string containing N characters: the series of base elements you are to invoke.最后将有一个整数N，由单一的含N个字符的字符串如下：你的基本元素是调用系列。 You will invoke them in the order they appear in the string (leftmost character first, and so on).您将在调用字符串中的顺序（最左边的字符的第一个，依此类推）似乎他们。

Output输出

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is a list in the format "[e0, e1, ...]" where ei is the ith element of the final element list.对于每一个测试案例，输出一行含有“案例＃谢：Y”型，其中X为案件编号（从1开始）和Y是在格式列表“[的E0，E1和...]"其中EI是在最后的第i个元素的列表元素。 Please see the sample output for examples.有关示例，请参阅示例输出。

Limits限制

1 ≤ T ≤ 100. 1≤温度：T≤100。
Each pair of base elements may only appear together in one combination, though they may appear in a combination and also be opposed to each other.对每个基本元素只能出现在一个组合在一起，尽管他们可能会出现在一个组合，也可以反对对方。
No base element may be opposed to itself.没有基础的元素可能会反对自己。
Unlike in the computer game Magicka, there is no limit to the length of the element list.不像在电脑游戏Magicka，有没有元素列表​​的长度的限制。

Small dataset小样本

0 ≤ C ≤ 1. 0≤ç≤1。
0 ≤ D ≤ 1. ð≤0≤1。
1 ≤ N ≤ 10. 1≤n时≤10。
Large dataset大型数据集

0 ≤ C ≤ 36. 0≤36≤ç。
0 ≤ D ≤ 28. ð≤0≤28。
1 ≤ N ≤ 100. 1≤n时≤100。
Sample样本


Input输入

Output输出

5 5
0 0 2 EA电针0 0 2
1 QRI 0 4 RRQR 1 0 4 RRQR QRI
1 QFT 1 QF 7 FAQFDFQ资历架构的QFT 1 1 7 FAQFDFQ
1 EEZ 1 QE 7 QEEEERA 1专属经济区1 7 QEEEERA量化宽松
0 1 QW 2 QW 0 1 2量子阱量子阱
Case #1: [E, A]案例一：[E的]
Case #2: [R, I, R]案例2：[001，我ř]
Case #3: [F, D, T]案例3：[的F，D，T]上
Case #4: [Z, E, R, A]案例4：为[Z，电子，俄，阿]
Case #5: []案例5：[]
Magicka™ is a trademark of Paradox Interactive AB. Magicka™是一个悖论的互动AB的商标。 Paradox Interactive AB does not endorse and has no involvement with Google Code Jam.悖论互动AB的不认可，也没有与谷歌编程挑战赛的参与。


and和

Small input小投入

10 points 10分

Solve D-small解决的D -小

You may try multiple times, with penalties for wrong submissions.你可以尝试多次，与错误的意见处罚。

Large input大的输入

20 points 20分

You must solve the small input first.您必须先解决小的输入。

You will have 8 minutes to solve 1 input file.您将有8分钟解决一输入文件。 (Judged after contest.) （看后比赛。）

Problem问题



Goro has 4 arms.五郎有4个武器。 Goro is very strong.五郎是很强的。 You don't mess with Goro.你不与戈罗混乱。 Goro needs to sort an array of N different integers.戈罗需要解决的N个不同的整数数组。 Algorithms are not Goro's strength; strength is Goro's strength.算法不五郎的强度，强度是五郎的力量。 Goro's plan is to use the fingers on two of his hands to hold down several elements of the array and hit the table with his third and fourth fists as hard as possible.戈罗的计划是使用他的手两个手指按住数组的元素和一些遭受的打击，他的表第三和第四个拳头越好。 This will make the unsecured elements of the array fly up into the air, get shuffled randomly, and fall back down into the empty array locations.这将使该数组的不安全因素飞入空中，得到随机洗牌，并回落到空数组位置了。



Goro wants to sort the array as quickly as possible.戈罗要排序的数组尽快。 How many hits will it take Goro to sort the given array, on average, if he acts intelligently when choosing which elements of the array to hold down before each hit of the table?多少会采取戈罗点击排序，平均给定的数组，如果他的行为是明智的选择时，数组元素之前举行表的每一击呢？



More precisely, before each hit, Goro may choose any subset of the elements of the array to freeze in place.更确切地说，在每一击，五郎可以选择任何数组的元素的子集，冻结到位。 He may choose differently depending on the outcomes of previous hits.他可以选择不同的命中根据以往的成果。 Each hit permutes the unfrozen elements uniformly at random.每一击permutes解冻元素的均匀随机的。 Each permutation is equally likely.每个排列也同样可能的。



Input输入



The first line of the input gives the number of test cases, T. T test cases follow.输入的第一行给出了测试的个案数目，T检验例，随访吨。 Each one will consist of two lines.每个人将包括两行。 The first line will give the number N. The second line will list the N elements of the array in their initial order.第一行将会给数n第二行会列出其初始顺序数组的n个元素。



Output输出



For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the expected number of hit-the-table operations when following the best hold-down strategy.对于每一个测试案例，输出一行含有“案例＃谢：Y”型，其中X为案件编号（从1开始），y是交通肇事的台操作时数后，预期最好压紧战略。 Answers with an absolute or relative error of at most 10-6 will be considered correct.在最具有绝对或相对误差10-6将被认为是正确答案。



Limits限制



1 ≤ T ≤ 100; 1≤温度：T≤100;

The second line of each test case will contain a permutation of the N smallest positive integers.每个测试案例第二行包含了N最小的正整数置换。

Goro has more than N fingers on each hand.五郎比每个手指的手，不更。



Small dataset小样本



1 ≤ N ≤ 10; 1≤n时≤10;



Large dataset大型数据集



1 ≤ N ≤ 1000; 1≤n时≤1000;



Sample样本





Input输入



Output输出



3三

2 2

2 1 2 1

3三

1 3 2 1 3 2

4 4

2 1 4 3 2 1 4 3

Case #1: 2.000000案例1：2.000000

Case #2: 2.000000案例二：2.000000

Case #3: 4.000000案例3：4.000000



Explanation解释



In test case #3, one possible strategy is to hold down the two leftmost elements first.在测试案例＃3，一个可能的策略是按住两个最左边的第一要素。 Elements 3 and 4 will be free to move.要素3和4将可自由移动。 After a table hit, they will land in the correct order [3, 4] with probability 1/2 and in the wrong order [4, 3] with probability 1/2.打表后，他们将土地以正确的顺序[3，4]的概率为1 / 2，在错误的顺序[4,3]的概率为1 / 2。 Therefore, on average it will take 2 hits to arrange them in the correct order.因此，它需要2平均命中安排在正确的顺序。 After that, Goro can hold down elements 3 and 4 and hit the table until 1 and 2 land in the correct order, which will take another 2 hits, on average.在此之后，五郎可以按住元素3和第4击，直到1表和2在正确的顺序，将采取平均另外2安打，土地。 The total is then 2 + 2 = 4 hits.然后总2 + 2 = 4命中。

镇魂夜

四月的大软好像有这个介绍
不过书不在这边家里||||||||

LZ可以自行百度嘛，搜魔法对抗就好了

禾西

回复 yangff 的帖子

列表中有互斥元素就會清空列表。兩個元素可合成先合成。合成反應先于互斥反應。

tamashii

介绍

Magicka 是一款由Arrowhead Game Studios设计的动作AVG。

就能看懂前两句，以上 - -

yangff

IamI 发表于 2011-5-7 19:51
八种基本元素，两两相邻出现在开头或末尾就生成新元素，两两相斥就把连带中间全数清空，现给出元素列表和配 ...

是把中间的清空还是整个list清空〉？？？

j12345678905022

简介

Magicka™是一款动作冒险游戏的游戏工作室开发的箭头。 在Magicka你玩了一个向导，调用和组合元素，创造Magicks。 这个问题也有类似的想法，但是它不会认为你发挥Magicka。

全部的翻译...
注：“调用”的意思是“呼吁”。 对于这个问题，它是一个技术术语，你不需要知道它的正常英语的意思。

问题

作为一个向导，您可以调用八素，这是“基地”分子。 每个基地元素是一个从{强，瓦，é，俄，阿，硫，丁，己}单个字符。 当你调用一个元素，它就会被添加到你的元素列表。 例如：如果你调用W和然后调用，（我们称之为“援引WA”的简称），那么你的元素名单将于[W时，]。

我们将指定相应的元素结合形成非基本元素（其他18个大写字母）对。 例如，Q和F可能结合起来，形成如果从一对的两个要素吨出现在元素列表的末尾，则无论对中的元素将被立即删除，它们将被替换的元素就形成。 在上面的例子，如果元素列表，如[阿，问，f]或[一，男，问]看起来在任何时候，它会变成[其A，T]。

我们将指定的基础，是反对对方的元素对。 当你调用一个元素，如果它不会立即结合成另一种元素，它是反对你的元素列表中的东西，那么你的元素的列表将被清除。

例如，假设Q和F相结合，使吨R和F反对对方。 然后调用下面的事情（按顺序，由左到右）将有以下的结果：

资历架构→[T]的（问及F相结合，形式为T）
优质教育基金→[问，E，F型]（Q和F可以不合并，因为他们在该元素的列表一起结束不要）
的RFE→[英]（F和R分别是反对的，所以名单被清除，然后E是调用）
文献→[]（F和R分别是反对的，所以名单被清除）
RQF→[001吨]（资历架构相结合，使笔，所以列表不清除）
询价→[问]（F和R分别是反对的，所以名单被清除）
鉴于一个元素列表来调用，究竟会在元素列表，当你正在做什么？

输入

输入的第一行给出了测试的个案数目，T检验例，随访吨。 每个测试案例包括一行，包含下列空间分隔，以便元素：

首先是整数C，由C字符串，每个包含三个字符如下：两个基地由一个非基本元素之后的元素。 这表明，两个基本要素结合，形成了非基本元素。 下一步会附带一个整数d，由D弦，每个都包含两个字符如下：两个基础，是反对对方的元素。 最后将有一个整数N，由单一的含N个字符的字符串如下：你的基本元素是调用系列。 您将在调用字符串中的顺序（最左边的字符的第一个，依此类推）似乎他们。

输出

对于每一个测试案例，输出一行含有“案例＃谢：Y”型，其中X为案件编号（从1开始）和Y是在格式列表“[的E0，E1和...]"其中EI是在最后的第i个元素的列表元素。 有关示例，请参阅示例输出。

限制

1≤温度：T≤100。
对每个基本元素只能出现在一个组合在一起，尽管他们可能会出现在一个组合，也可以反对对方。
没有基础的元素可能会反对自己。
不像在电脑游戏Magicka，有没有元素列表​​的长度的限制。

小样本

0≤ç≤1。
ð≤0≤1。
1≤n时≤10。
大型数据集

0≤36≤ç。
ð≤0≤28。
1≤n时≤100。
样本


输入
        
输出

5
电针0 0 2
1 0 4 RRQR QRI
资历架构的QFT 1 1 7 FAQFDFQ
1专属经济区1 7 QEEEERA量化宽松
0 1 2量子阱量子阱
案例一：[E的]
案例2：[001，我ř]
案例3：[的F，D，T]上
案例4：为[Z，电子，俄，阿]
案例5：[]
Magicka™是一个悖论的互动AB的商标。 悖论互动AB的不认可，也没有与谷歌编程挑战赛的参与。

于是偶总结性地翻译一下：Magicka是个好游戏（大雾）