北京时间2015年3月28日晚上9:00到12:00参加了一个由Bucknell University举办的编程比赛。在三个小时的过程中，我们队伍一共做出了8道题中的3道，得到Expert组第二名的好成绩。比赛的题目总体上不是很难，比较考验对算法的熟练程度和英文的阅读理解能力。很感谢有两位队友(沈多，仇晓逢)在比赛中的精彩发挥。
Gnash your Teeth while opening safes!
You are deep in the lair of guitar-loving Master Villain Guattery, better known as The Ax, and you’ve reached a chamber full of 16 safes. You’ve heard rumors that the plans to conquer the world with guitar playing robots that lull people to sleep before taking over the world are found in these safes. Each safe has a different number of buttons on the front numbered 1 thru n. In a dusty back corner of the room you find a note left by The Ax reminding himself that the combos are prime rings.
A prime ring is a circular sequence of all numbers between 1 and n (where n is an even number) where each pair of consecutive numbers add up to a prime. This means that the first and the last number of the sequence must also add up to a prime. Each number between 1 and n appears exactly once in the sequence. All sequences start with the number 1.
For example, if n is 6, 1+4 is prime and 1+6 is prime so the answer has 2 sequences. The first starts with 1 4 and the second starts with 1 6. For the first sequence 4+3 is prime then 3+2 is prime then 2+5 is prime then 5+6 is prime. We are out of numbers and 1+6 is also prime so the full sequence is 1 4 3 2 5 6. For the second sequence, 6+5 is prime then 5+2 is prime then 2+3 is prime then 3+4 is prime. We are out of numbers and 1+4 is also prime so the full sequence is 1 6 5 2 3 4.
Odd numbers have no prime rings so you’ll have to find a different way to open the safes with an odd number of buttons.
Your task is to figure out the safe combinations quickly before The Ax finds you. The safes with an even number of buttons may each have several prime rings but its faster than trying every possible combination.
Input
Each line of input will contain a value for n (1 < n ≤ 16). The last line of input will contain the number 0. This last line should not be processed.
Output
The output of your program should list all prime ring sequences starting with 1 for the current value of n in ascending order. The output should be formatted as in the sample below. If there are no prime rings for an input then don't print anything. (9 has no prime rings).
Sample Input
6
8
9
0
Output for Sample Input
1 4 3 2 5 6
1 6 5 2 3 4
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
题目本身就是一个回溯，但是题目的结论很有意思。也很明显，[1..n]，如果n为奇数的话，并不能找到一个序列，让任意两个相邻的数之和为质数；而如果n为偶数的话，一定存在这样的一个序列，并且不唯一。
再看代码本身，很久不写这种需要自己输入输出饿题目了，一开始写也是各种不适应。输入是一个n，需要输出所有符合条件的[1..n]的序列。
回溯是最容易想到的方法，实现起来应该也非常的容易。犹豫每次选择的范围是变小的。所以，我们要维护一个可以选择的区域。我使用了vector
在做这道题的时候，出现了一个很奇怪的问题。在本机调试的时候，编译和运行均没有问题，但是在对方的服务器上编译的时候就总是出现编译错误。最后通过对方给出的行号，定位到了居然是一个质数表的初始化错误。结果是发现对方方的的gcc还是C++98标准的，没有加入大括号的初始化标准。最后通过简单的修改，这道题就通过了，这时比赛已经进行了1个小时。
Follow your Nose while sleuthing!
Your Spy Ring has gone on a trip to rebuild the computer systems in your 20 Secret Bases worldwide. When you reach a Base, you can then contemplate which Base to visit next.
Each base has between 1 and 19 easy connections to other Secret Bases. (Depending on train routes, underwater passages etc.). Director King (in charge of Headquarters) wants you to complete the entire trip as quickly as possible. He will be monitoring your progress via analysis of Twitter Feeds.
Input
Input to your program will consist of a set of Base configurations for the 20 Secret Bases and a set of Base pairs which are possible start and destination Bases.
A configuration contains 19 lines describing which Bases can be reached from which other Bases. The representation avoids listing every Base interconnect twice by only listing the fact that Base x is connected to Base y when x < y. Thus, the xth line contains an integer z indicating how many "higher-numbered" Bases are connected to Base x, then z distinct integers y (greater than x) describing all the Bases that Base x connects to.
Line 20 contains a single integer N (1 ≤ N ≤ 100) indicating the number of Base pairs that follow. The next N lines each contain exactly two integers A and B (1 ≤ A and B ≤ 20 and A!=B) indicating the starting and ending Bases for a possible voyage. All the Bases are interconnected so that you can travel from each Base to each other Base eventually. (If a Base x is only connected to lower numbered Bases, line x will contains only a 0).
Output
Print the minimum number of Bases that have to be visited to get from the starting Base to the destination Base for the Base pair A and B in the input. Each line will have the form
S to D: M
where S is the starting Base, D is the destination Base, and M is the number of Bases that need to be visited in between. There is a space after the colon. Include the trip to Base D in your count so if S and D are neighboring Bases, M would be 1. Print the output for the Base pairs in the same order they were inputted.
Sample Input
A sample Secret Base map can be seen in with a line drawn between all neighboring Bases.
1 3
2 3 4
3 4 5 6
1 6
1 7
2 12 13
1 8
2 9 10
1 11
1 11
2 12 17
1 14
2 14 15
2 15 16
1 16
1 19
2 18 19
1 20
1 20
5
1 20
2 9
19 5
18 19
16 20
In this data, Base 1 connects to one Base (3) and Base 4 connects to 1 higher numbered Base (6). 4's connections to 2 and 3 are seen on the 2nd and 3rd lines. There are 5 Base pairs to consider.
Output for Sample Input
1 to 20: 7
2 to 9: 5
19 to 5: 6
18 to 19: 2
16 to 20: 2
The minimum trip from Base 16 to Base 20 requires 2 trips; 16 to 19 and 19 to 20.
这么长的一道题，其实就是想表达这是一道让你求最短路径的题。然后，感觉题目已经明显到让你感觉到这是用Floyd算法了。所以直接代码敲起就好，唯一需要注意的地方就是他的输入输出格式。
Floyd算法本身的代码量很少，所以我么大概就只用了20分钟敲完，然后花了10分钟检查之后就交了。期间犯了一个很傻的错误，就是我把所有不联通的路径的值都初始化为了INT_MAX，在算法进行的过程中就产生了越界的问题。其实这样的途中，如果每条边的长度都为1的话，只要默认长度大于20即可。
Floyd算法的基本流程如下：
for(int k = 1; k <= 20; ++k)
for(int i = 1; i <= 20; ++i)
for(int j = 1; j <= 20; ++j)
if(d[i][k] + d[k][j] < d[i][j])
d[i][j] = d[i][k] + d[k][j];
最后我们就得到了一张多源的表，之后我们就可以根据题目的输入需求找到相应的两点，根据响应的条件输出即可。
Watch you don't scratch a fellow spy with your Poison Nail!
The Spy Academy has made an offer for a lottery that will choose some number (X) of lucky people to return to the states for a recruiting tour. Your Spy Ring has been working hard and desperately wants this easy duty. The lottery is run by lining up all the Spy Rings and eliminating Rings by counting off the Rings from 1 to N where N is a number chosen by pulling cards off of the top of a deck. Every time N is reached, that Spy Ring falls out of the line, and counting begins again at 1 with the next Spy Ring in line. When the end of the line has been reached (with whatever number that may be), the next card on the top of the deck will be taken, and counting starts again at 1 with the first Spy Ring in the remaining line. The last X Spy Rings in line get to go home.
Your Spy Ring has found a way to trade a stacked deck with the real deck just before the selection process begins. However, you will not know how many people will show up for the selection until the last minute. Your job is to write a program that will use the deck you supply and the number of Spy Rings in line that you count just before the selection process begins and know what position(s) in the line to get in to assure your Spy Ring of a trip home. You are assured that your deck will get the job done by the time the 20th card is used.
A simple example with 10 Spy Rings, 2 lucky spots, and the numbers from cards 3, 5, 4, 3, 2 would show that you should get in positions 1 or 8 to go home.
Input
For each selection, you will be given a line of 22 integers. The first integer (1 <= N <= 50) tells how many Spy Rings will participate in the lottery. The second integer (1 <= X <= N) is how many lucky "home" positions will be selected. The next 20 integers are the values of the first 20 cards in the deck. Card values are interpreted to integer values between 1 and 11 inclusive. There will be a 0 on the last line to indicate the end of the input.
Output
For each input line, you are to print a list of "lucky" positions that your Spy Ring should attempt to get into.
Sample Input
10 2 3 5 4 3 2 9 6 10 10 6 2 6 7 3 4 7 4 5 3 2 4
47 6 11 2 7 3 4 8 5 10 7 8 3 7 4 2 3 9 10 2 5 3 0
Output for Sample Input
1 8
1 3 16 23 31 47
题目的意思不是很复杂，是一道模拟。每次的输入是一行数字，一共有22个。然后第一个数字n代表[1..n]的集合，之后数字m代表最后可以剩余的数字数量。之后的20个数字表示每次删除数字的间隔。
比如以第一个测试用例的第一趟删除为例：
start: 1 2 3 4 5 6 7 8 9 10
when the removal interval == 3;
after delete: 1 2 4 5 7 8 10
然后每次超过最后一个的情况下，都需要去取20个数中的下一个数。对删除后的序列再次进行操作，直到删除的结果只剩下m个为止。
通过vector的erase，删除掉响应的元素，这题需要注意的地方是，如果再删除的过程中，还没有遇到最后一个的情况下，我们仍需要监控数量大于m的这个条件，不然就可能会多删掉元素。