网上找的一些综合材料专题magic

1、题目来源：IPSC 2001 Problem H - Magic推荐者： 王知昆情况： 可以用二分图完备匹配的算法做，标准解答也是这样做的。推荐理由： 感觉可以用构造法，但是没有想出来，希望和大家讨论。毕竟，用二分图匹配的算法复杂度较高，只能做较小的数。Internet Problem Solving ContestIPSC 2001Problem H - MagicA famous magician enters the stage, followed by a beautiful assistant. He starts his show by pulling several hares

2、from his magic hat, then he finds a bouquet of flowers in the assistants scarf, and finally he locks the assistant in a seemingly empty mirror box. And then comes the audiences turn. The magician shows them a deck of N cards (all the cards are different, N is odd). A volunteer comes to the stage and

3、 selects (N+1)/2 cards. The rest of the cards is lost forever in the magicians hat. After waving his hands above the selected cards, the magician picks up one of the cards and gives it to the volunteer who shows it to the audience and subsequently hides it in his pocket. The assistant, after being r

4、eleased from the mirror box, comes to the deck of the remaining (N+1)/2-1 cards. She waves her hands above it for a while and then she describes the one card hidden in the volunteers pocket. How could this happen? Magic? A clever trick? Given N, find an algorithm (if it exists) for the magician and

5、his assistant. FAQIs the assistant an extraterrestrial or someone practicing telepathy? No, she is a normal, albeit beautiful, human being. How did the assistant get out of the mirror box? By magic, of course. Can the assistant see through the mirror box or pockets? Obviously not, see answer to Q. #

6、1. Input file specificationGiven is odd N, the number of cards. Output file specificationLets assume that the cards are numbered 1,2,.,N. In the output file, list all possible subsets of 1,2,.,N of size (N+1)/2, every subset on a separate line. Every subset S is followed by - and by a number c from

7、S. The number c is the one card that the magician should give to the volunteer. This describes the magicians algorithm. The assistant has to be able to find the unique c, after seeing the set S-c. Therefore, in no two lines S-c can be the same. If this holds, assistant can use the reversed magicians

8、 algorithm to identify the correct c. (Both of them have to memorize your output file.) Every two consecutive numbers in S, the number c and - are separated by single spaces. If no algorithm exists, output a single word MAGIC. ExampleInput file: 3Output file (one out of several possible): 1 2 - 21 3

9、 - 12 3 - 3魔术一位著名的魔术师走上舞台，后面跟着他漂亮的助手。魔术师开始他的表演，先从他的魔术帽中拖出一些野兔，接着从他助手的围巾里找出一些鲜花，最后，他把他的助手锁在一个盒子里。然后，他拿出一副有n张的牌（每张牌都不同，n是个奇数）。一个志愿者上台选出（n+1）/2张牌，其余的牌被扔掉。魔术师在牌上挥挥手，然后取出一张牌，由这名志愿者展示给观众，接着志愿者将这张牌收到口袋里。魔术师的助手被放出来，看了剩下的(n+1)/2-1张牌后，在牌上挥挥手，接着，她就可以描述出被志愿者收起来的那张牌。这是怎么回事呢？魔法？还是一个聪明的骗局？给出n，请你为魔术师和他的助手寻找一种算法。FAQ：1、这个助手是天外来客？或者和谁有心灵感应？ 不！她虽然很漂亮，但还是一个普通人。2、助手是怎么从盒子里出来的？ 依靠魔法3、助手能从盒子里往外看或者看到志愿者口袋里的牌吗？ 当然不行输入文件： 输入一个奇数n。输出文件： 假设牌按1n编号，在输出文件中，列出所有大小为(n