鸟语求翻译……

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.

复制代码

54酱

翻译什么的...
要自食其力...
话说这工程量也太大了吧....

IamI

八种基本元素，两两相邻出现在开头或末尾就生成新元素，两两相斥就把连带中间全数清空，现给出元素列表和配对关系，求最后结果

Anson

Magicka™是一款动作冒险游戏由亚罗海德游戏工作室开发。

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

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的不认可，也没有与谷歌编程挑战赛的参与。

yangff

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

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

tamashii

介绍

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

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

禾西

回复 yangff 的帖子

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

镇魂夜

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

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