铺砖

对于一个2行N列的走道。现在用1*2,2*2的砖去铺满。问有多少种不同的方式。

时间限制：3000

内存限制：131072

输入

整个测试有多组数据，请做到文件底结束。每行给出一个数字N，0 <= n <= 250

输出

如题

样例输入

2
8
12
100
200

样例输出

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

质数的和与积

两个质数的和是S，它们的积最大是多少？

时间限制：10000

内存限制：65536

输入

一个不大于10000的正整数S，为两个质数的和。

输出

一个整数，为两个质数的最大乘积。数据保证有解。

样例输入

50

样例输出

589

吃糖果2

现有n(50 > n > 0)个糖果,每天只能吃2个或者3个，请计算共有多少种不同的吃法吃完糖果。

时间限制：1000

内存限制：65536

输入

输入的每一行包括一组测试数据，即为糖果数n。最后一行为0，表示测试结束。

输出

每一行输出对应一行输入的结果，即为吃法的数目。

样例输入

1
2
3
4
12
0

样例输出

0
1
1
1
12

因子问题

任给两个正整数N、M，求一个最小的正整数a，使得a和(M-a)都是N的因子。

时间限制：10000

内存限制：65536

输入

包括两个整数N、M。N不超过1,000,000。

输出

输出一个整数a，表示结果。如果某个案例中满足条件的正整数不存在，则在对应行输出-1

样例输入

35 10

样例输出

5

扩号匹配问题

在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.

时间限制：3000

内存限制：65536

输入

输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100

输出

对每组输出数据，输出两行，第一行包含原始输入字符，第二行由"$","?"和空格组成，"$"和"?"表示与之对应的左括号和右括号不能匹配。

样例输入

((ABCD(x)
)(rttyy())sss)(

样例输出

((ABCD(x)
$$
)(rttyy())sss)(
?            ?$