Time | Orange | Blue
-----+------------------+-----------------
1 | Move to button 2 | Stay at button 1
2 | Push button 2 | Stay at button 1
3 | Move to button 3 | Push button 1
4 | Move to button 4 | Move to button 2
5 | Stay at button 4 | Push button 2
6 | Push button 4 | Stay at button 2
输入的文件第一行是需要处理的问题总数T，下面跟着的T行，每一行第一个数N表示后面跟着N个按照顺序需要按的按钮。
输出只要显示每行最小的耗费时间即可。
下面是我的程序，所有的异常都考虑到啦，像是一个程序员写的程序，不像算法比赛：
#include
#include
#include
#define LARGE_N 100
int find_next(char **cont, const int num, const int cur)
{
int i;
/* Only 'O' and 'B',find next different color robot */
for (i = cur + 1; i < num; ++i)
if (cont[cur][0] != cont[i][0])
return i;
/* means all the remaining steps are the same robot */
return 0;
}
void proc(char **cont, const int num, int *step, int *minute)
{
/* at least need 2 item to calculate the time */
if (*step >= num - 1)
return;
int cur = *step, next;
int lastpos[2] = {*minute, 1};
for (;;)
{
next = find_next(cont, num, cur);
if (next == 0)
{
while (cur < num - 1)
{
*minute += abs(atoi(&cont[cur+1][1]) - atoi(&cont[cur][1])) + 1;
++cur;
}
break;
}
/* calculate */
int cmptime[2] = {0, 0};
while (cur < next - 1)
{
cmptime[0] += abs(atoi(&cont[cur+1][1]) - atoi(&cont[cur][1])) + 1;
++cur;
}
/* 比较下一个不同颜色移动的时间，和这一个颜色移动的时间。
* 原因是下一个颜色可以在这一个颜色移动的同时移动 */
/* next颜色robot可能向前或向后移动，所以加入abs() */
int diff = abs(atoi(&cont[next][1]) - lastpos[1]) - (cmptime[0] + lastpos[0]);
if (diff <= 0)
cmptime[1] = 1;
else
cmptime[1] = diff + 1;
/* 计算下一个不同颜色的robot的第一个格子耗费时间 */
lastpos[0] = cmptime[1];
/* 计算这个颜色的robot，作为下下个robot时的上一个格子的位置 */
lastpos[1] = atoi(&cont[next-1][1]);
cur = next;
*minute += cmptime[0] + cmptime[1];
}
*step = cur;
return;
}
void free_content(char **cont, int num)
{
if (cont == NULL)
return;
while (num--)
free(cont[num]);
free(cont);
}
int main(int argc, char **argv)
{
FILE *fp = fopen(argv[1], "r");
if (fp == NULL)
{
//printf("bad happen when opening file.\n");
exit(1);
}
char *line = NULL;
size_t len = 0;
ssize_t read;
read = getline(&line, &len, fp);
//printf("len:%d, ret:%d(include '\\n'), val:%s", len, read, line);
int total = atoi(line);
if (total >= 1 && total <= 100)
;//printf("T: %d\n", total);
else
{
//printf("T is not in range: %d\n", total);
free(line);
fclose(fp);
exit(1);
}
char **content = NULL;
content = (char **)malloc(LARGE_N * sizeof(char *));
int i;
for (i = 0; i < LARGE_N; ++i)
content[i] = (char *)malloc(sizeof("O 100") * sizeof(char));
int j;
for (j = 0; j < total; ++j)
{
int num, retbits, totalbits = 0;
getline(&line, &len, fp);
sscanf(line, "%d %n", &num, &retbits);
totalbits += retbits;
//printf("num:%d, totalbits:%d\n", num, totalbits);
for (i = 0; i < num; ++i)
memset(content[i], 0, sizeof("O 100"));
for (i = 0; i < num; ++i)
{
sscanf(line + totalbits, "%c %3[0-9] %n", &content[i][0], &content[i][1], &retbits);
//printf("ret:%d, value:%s\n", retbits, content[i]);
totalbits += retbits;
}
/* core idea,开始想做一个递归函数，所以加入step变量 */
int minute = 0, step = 0;
minute += atoi(&content[0][1]);
proc(content, num, &step, &minute);
printf("Case #%d: %d\n", j + 1, minute);
}
free_content(content, LARGE_N);
free(line);
fclose(fp);
return 0;
}
第二题：Magicka
有若干种基本元素，像是 {Q, W, E, R, A, S, D, F} 字母表中的其他字母表示合成元素。两个基本元素可以合成一个合成元素，比如QF合成T。我们用三个字母的组合QFT，来表示一个字符串中只要出现QF或者FQ就变成一个字母T，这叫combine。
另一种叫做opposed的方式。是当进行完combine之后，整个字符串中还存在两个字母的组合，比如VC，整个当前字符串就消失。比如VBFC 变成空。
输入文件第一行T表示下面有T行需要处理的字符串。每一行第一个数字C表示后面有几个3个字母组成的combine，第二个数字D表示后面有几个2个字母组成的opposed，第三个数字N表示后面要处理的字符串的长度。对长度为N的字符串先用combine规则，再用opposed规则就可以输出结果了。
输出的结果字符串要求是python里面的list的形式。
我很辛苦的写了一个程序，但是没有理解opposed里面整个list都消失了的含义，把问题给搞复杂了，遗憾。本来想python也许更简单，但是有第一题的读文件格式的架子，就用c了，后来发现python狂easy。
下面是官方Contest Analysis 里面对于这个问题的python伪代码：
# 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)
