NOIP 2012模拟练习赛
整理于：安徽大学ACM集训队
Problem A
采蘑菇的小女孩
问题描述：
小女孩打算在5座山里采蘑菇。她带了5个背包，分别收集来自5座山的蘑菇。每个背包最多能装下2012个蘑菇。女孩已经收集了来自于n(0<=n<=5)座山的蘑菇。在第i座山里，她收集了wi (0<=wi<=2012) 个蘑菇。现在她还会继续收集其余（5-n）山的蘑菇。
小女孩采完蘑菇后就会回家。回家的路上她会穿过一片森林。在森林的入口，住着她的三位好朋友，Sunny, Lunar ,Star . 她必须分别赠送给这三位朋友一个背包的蘑菇，且这3个背包蘑菇总个数为 1024的整数倍（0，1024，2048.。。。）。 如果她做不到，她必须留下5个背包的蘑菇给朋友，这将意味着她将空手而归。
快到家门口时，小女孩还要经受她邻居的考验。即如果女孩此时包里的蘑菇总数大于1024，邻居则会不断拿走1024个蘑菇，直到女孩背包蘑菇总数不大于1024.
给你女孩当前的采集情况，问最后女孩经过朋友、邻居两关考验后最终能获得多少个蘑菇？
输入格式： 多组测试数据，循环输入。
第一行：一个整数 N，代表小女孩已经采了N座山。之后会继续采，直到采完5座山。
第二行：N个整数，分别代表每座山女孩已采的蘑菇数（每座山只采一次）。
输出格式： 女孩最终能获得的蘑菇数。
输入样例：
1 9 4
512 512 512 512 5
100 200 300 400 500 5
208 308 508 708 1108
输出样例：
1024 1024 0 792
注释：第一组数据9代表女孩从第一座山里采了9个蘑菇，之后4座山，每座山她可随机采一定数
量（0~2012）的蘑菇.
Problem B
遗址
【题目描述】
很久很久以前有一座寺庙，从上往下看寺庙的形状正好是一个正方形，在4个角上竖立着圆柱搭建而成。现在圆柱都倒塌了，只在地上留下圆形的痕迹，可是现在地上有很多这样的痕迹，专家说一定是最大的那个。
写一个程序，给出圆柱的坐标，找出由4个圆柱构成的最大的正方形，因为这就是寺庙的位置，要求计算出最大的面积。注意正方形的边不一定平行于坐标轴。
例如下图有10根柱子，其中(4,2),(5,2),(5,3),(4,3)可以形成一个正方形，(1,1),(4,0),(5,3),(2,4)也可以，后者是其中最大的，面积为10。
【输入格式】
第一行包含一个N(1<=N<=3000)，表示柱子的数量。
接下来N行，每行有两个空格隔开的整数表示柱子的坐标(坐标值在0.到5000之间)，柱子的位
置互不相同。 【输出格式】
如果存在正方形，输出最大的面积，否则输出0。 【样例输入输出】 Ruin.in Ruin.out 10 10 9 4 4 3 1 1 4 2 2 4 5 8 4 0 5 3 0 5 5 2 【数据范围】
30% 1<=N<=100 60% 1<=N<=500。
Problem C
对撞机
在2312年，宇宙中发现了n台巨型对撞机，这些对撞机分别用1-n的自然数标识。科学家们不知道启动这些对撞机会发生什么危险事故，所以这些机器，刚开始都是处于关闭状态。
随着科学家们的研究发现，第i台对撞机启动是安全的，如果其他已经启动的对撞机的标识数都跟这台对撞机标志数互质。（例如假设前面启动的是j,如果i能启动，那么(I,j)互为质数，也就是（I,j）的最大公约数为1）!如果两台对撞机不互为质数就启动，那么就会发生爆炸事故。
基于前面的研究，科学家们准备做各种启动和关闭对撞机的实验，为了确保科学家的生命安全。你要设计一个远程遥控的软件。
刚开始，所有的对撞机都是关闭状态。你的程序将会收到许多询问，格式为“启动/关闭第i台对撞机”。这程序应该能处理这些询问（根据收到询问的先后顺序处理）。这程序应该按照如下的格式输出处理结果。
如果询问是”+ i”（表示第i台对撞机启动），这程序应该按照下面三种的情况之一输出结果。
（1）”Success”，如果启动第i台是安全的
（2）”Already on”,如果第i在这个询问之前就已经启动了。
（3）”Conflict with j”，如果第i台跟前面启动了的第j台冲突，就不能启动第I，如果前面有多台跟i冲突，那么只要输出其中任何一台就可以。
如果询问是”-i”（表示关闭第i台对撞机）,这程序应该按照下面两种的情况之一输出结果。
（1）”Success”,表示关闭第i台对撞机
（2）”Already off”，表示第i台对撞机在询问之前就已经关闭了。
输入格式
第一行输入两个空格隔开的整数n和m（1≤n,m≤10^5）分别表示对撞机的数量和询问数。 接下来m行表示询问，每行要么为”+ i”，要么为”- i”（不含引号）（1≤i≤n）
输出格式
输出m行，输出结果按照上面题目给定格式输出。
输入样例 (collider.in) 10 10 + 6 + 10 + 5 - 10 - 5 - 6 + 10 + 3 + 6 + 3
输出样例 (collider.out) Success
Conflict with 6 Success
Already off Success Success Success
Success
Conflict with 10 Already on
Problem D
摘苹果
问题描述：
很少有人知道奶牛们都很喜欢吃苹果。农场主John，拥有两颗（标记为1,2）苹果树。有趣的是，每分钟，就会有一个香甜的苹果从某棵树上掉下来（同一分钟不会有两棵树掉苹果）。这时，奶牛们就可以去接了。
奶牛们都很懒，一分钟内只会从一棵树移动到另外一棵树，并默认接苹果这个动作是不耗费时间的。某一天，奶牛Bessie来接苹果。0时刻她站在树1下，由于她不经常运动，所以她最多愿意移动W次。
现在给你知道苹果树会掉落T（1<=T<=1,000）分钟，Bessie最多移动W（1<=W<=30）次。并给你每分钟（1~T）,哪棵树会掉下苹果。开始时她站在树1下。
输入格式： 第一行：两个整数 T，W
第二行至T+1行：1或者2，代表当前分钟掉落苹果的树。
输出格式： Bessie能得到的最大苹果数
输入样例： 7 2 2 1 1 2 2 1 1
输出样例： 6
注释：总共7个苹果掉落。第一个苹果从2号树掉，第二个从1号树掉„„ 前三分钟，奶牛在一号树下不移动，可接到2个苹果。然后跳到2号树。 4,5分钟奶牛在2号树下，能接到2个苹果。然后跳到1号树。 6,7分钟奶牛在1号树下，能接到2个苹果。
