普及组模拟题

啊哈磊

第一题：模拟开关
题目描述：有N盏电灯排成一行，依次编号为1，2，3，…,N，各有一个开关，开始灯都亮着的。现在还有N个人，第1人走过来依次把1和1的倍数电灯的开关都拉一下。第2个人走过来依次把2和2的倍数的开关都拉一下，第3个人走过来依次把3和3的倍数的开关都拉一下，……问最后都有哪些灯是关着的？
[输入文件] 文件名：moni.in
文件中只有一行，包含1个整数N(其中5≤N≤10000)
[输出文件] 文件名：moni.out
文件共一行，分别为那些关着的灯泡的编号，如果没有灯泡关着，就输出0。
[样例输入]：moni.in的内容为：
10
[样例输出]：moni.out的内容为：
1 4 9

第二题：矩阵中心

题目描述：一个整型矩阵的中心（x，y）是这样确定的：使第x行上边元素的总和与第x行下边元素的总和之差的绝对值最小，而且第y列左边元素的总和与第y列右边元素的总和之差的绝对值最小。现在有一个整型矩阵，请你找出它的中心（x，y）。如果只有一个中心，则输出中心位置；如果存在多个中心，则输出中心的个数。
输入格式：
m+1行。第一行有两个整数m、n，分别表示矩阵的行和列。以下m行，每行有n个不超过200的正整数。其中：2 输出格式：
一行。如果这有一个中心，则输出（x，y）；否则输出一个整数，表示中心的个数。
输入样例一：
5 5
2 3 2 3 2
2 3 4 2 2
3 4 2 2 4
5 2 2 2 3
3 3 4 4 2
输出样例一：
（2，2）
输入样例二：
3 4
2 2 2 2
2 4 4 2
2 2 2 2
输出样例二：
2
输出样例二解释：存在两个中心（2,2）（2,3）

第三题：加法等式
题目描述：判断n个数中是否存在3个数a，b，c满足a+b=c？
[输入文件] 文件名：add.in
第一行：整数n（1 第二行：输入n个整数（每个数x都满足：1= [输出文件] 文件名：add.out
输出：根据判断准则，输出YES或NO
[样例输入]：add.in的内容为：
3
1 4 9
[样例输出]：add.out的内容为：
NO
第四题： NBA总冠军
题目描述：又要考试了，Ljw决定放松一下，就打开电视，看见了篮球赛，他立即想到了每年的NBA总冠军队伍。由于复习紧张，他只记起了一部分，记忆的内容是正确的，可能不是按时间顺序排列的，记忆的内容可能有重复。现在请求学过编程的你帮助Ljw，按时间顺序依次输出总冠军的球队（不能重复）。
（NBA从1947A.D到2009A.D）
【输入】
输入文件nba.in的第一行是一个整数n(0 接下来的n行，每行先是城市名（由大小写字母、空格组成），后是时间（由数字组成）。二者间用空格隔开。
【输出】
输出文件nba.out共n行，即排序后的NBA总冠军队伍。每行先是时间，后是城市名。
【输入输出样例】
nba.in
nba.out
3
Boston 1963
Boston 1959
Philly 1947
1947 Philly
1959 Boston
1963 Boston

第五题：买票

题目描述：周末Ztc想去剧场看演出，但他没有票。这时，救世主wzj出现了，他慷慨的愿意卖给ztc一些票。Wzj手上共有n张票，但每张票的费用都不一样，贪心的ztc想要得到尽可能多的票，但又想花费最少，慷慨的wzj愿意给连续的m张票。Ztc希望你能帮助他在花钱范围内取得最大的票数。

【输入】

输入文件tickets.in的第一行是2个整数n，f。其中（2<=N<=1000000），表示票的数目, ( 10 <= f <=10000 ),表示ztc身上的钱。

接下来的1行，有n个整数a（1<=a<=30），表示每一张票的票价。

【输出】

输出文件tickets.out仅一行整数m，表示ztc能得连续的最大票数。

【输入输出样例】

tickets.in	tickets.out
5 102 3 1 6 7	3

【限制】

50%的数据满足： 2<=n<=10000

100%的数据满足： 2<=n<=1000000

第六题：排队打水问题

题目描述：有N个人排队到M个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数，应如何安排他们的打水顺序才能使他们花费的总时间最少？

[输入格式]：

第一行：两个整数n, m; m表示水龙头的个数，n表示人的个数。

接下来的n行，每行1个整数，分别表示n个人装水的时间；

数据规模： M<=n/3 n<=1000； t<3000

[输出格式]：

一行，一个整数，表示总花费的最少时间。

样例:

INPUT

6 2

5

4

6

2

1

7

OUTPUT

40

第七题：逛街

题目描述：某天，ZCL在街上闲逛。他在超市里看到促销广告：商品大降价。于是他很高兴地拿着篮子购物去了。

　 已知商场内有n种商品。每种商品的重量为w千克，价格为v。此种商品每件可收获的满意值为t，此种商品有h件。注意。此商场有一个奇怪的规定。每种物品要么不买，要么买1件或h件。ZCL带了y元。ZCL最多能扛x千克的物品。

请帮ZCL求出他最多能获得的满意值。（不允许抢劫）

【输入】

输入文件shop.in的第一行有3个用空格隔开的整数n、x和y。

接下来的n行，每行有4个数据，分别为w、v、t和h。

【输出】

输出文件shop.out共一行，表示ZCL最多能获得的满意值。

【输入输出样例】

shop.in	shop.out
2 8 10 5 3 7 1 3 7 10 1	17

【限制】

100%的数据满足：0<=n<=300，0<=x<=100，0<=y<=100，0<=h<=10

第八题：取数方案

题目描述：规则：自然数1到N，按顺序列成一排，你可以从中取走任意个数字，但是相邻的两个不可以同时被取走。请你算一算，一共有多少种取法？（时间限制： 1s ）

[输入格式]： 仅包含一个数n（1< n < 1000）。

[输出格式]： 仅包含一个数———你的答案。

样例：

输入：1         输出：2