``` markdown
1（必做） 二维极大点问题 *
Score 100
在一个二维平面上，如果有两个点(x1,y1)和(x2,y2)，有比较关系x1>x2且y1>y2，则称点(x1,y1)支配了(x2,y2)，(x1,y1)是极大点。
当比较关系修改为x1≥x2且y1≥y2时，支配关系会产生有趣的变化，下面考虑这种情况。对于给定n个点的集合，编程找出所有的极大点，按照x坐标由小到大，输出极大点的坐标。

输入格式:
输入包括两行，第一行是正整数n，表示是点的个数，第二行包含n个点的坐标，坐标值都是整数，x坐标和y坐标范围从0到1000，且输入数据中不存在坐标相同的点。

输出格式:
按x轴坐标最小到大的顺序输出所有极大点。
输出格式为:(x1,y1)(x2,y2)...(xk,yk)

输入样例:
5
1 2 2 2 3 1 2 3 1 4
输出样例:
(1,4)(2,3)(3,1)
Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB
Stack size limit
8192 KB
```

---

``` markdown
2 递归算法解决自然数拆分问题
Score 100

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和，试求n的所有拆分。

输入格式:
输入大于1的自然数n。

输出格式:
输出包含多行，每行为自然数n的一种拆分，表示为加法式的形式，以拆分数非递减的次序输出。

输入样例1:
5
输出样例1:
1+4
1+1+3
1+1+1+2
1+1+1+1+1
1+2+2
2+3
输入样例2:
7
输出样例2:
1+6
1+1+5
1+1+1+4
1+1+1+1+3
1+1+1+1+1+2
1+1+1+1+1+1+1
1+1+1+2+2
1+1+2+3
1+2+4
1+2+2+2
1+3+3
2+5
2+2+3
3+4
Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB
Stack size limit
8192 KB
---

``` markdown
3 诚实人调查问题
Score 100
有N个人，其中某些人是诚实的其他人可能会说谎。现在需要进行一项调查，该调查由一系列测试构成，每次测试如下进行：选2个人，然后提问：对方是否诚实？每个人的回答只能是“是”或者“否”。假定在这些人中，所有诚实的人回答都是正确的，而其他人的回答则不能肯定是否正确。如果诚实的人数>N/2，试设计一个调查算法，以最小的测试次数从其中找出一个诚实的人。

输入格式:
第一行为一个不超过100的正整数N，表示参与调查的总人数；接下来的N行，每行或者是1或者是0（其中1代表诚实的人，0代表会说谎的人，注意1的个数>N/2）。

输出格式:
正整数K，表示第K个人是诚实的。
(若有多个答案，请输出最小的一个,如输入样例的对应答案11，12，15，16均满足，其中最小的为11)

输入样例:
在这里给出一组输入。例如：

16
1
0
1
0
1
1
0
0
1
0
1
1
1
0
1
1
输出样例:
在这里给出相应的输出。例如：

11
Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB
Stack size limit
8192 KB
```

``` markdown
4（必做） 带有期限的作业调度问题 *
Score 100
带有期限的作业调度问题要解决的是操作系统中单机、无资源约束且每个作业可在等量时间内完成的作业调度问题，形式化描述为：

只能在一台机器上处理 n 个作业，每个作业 i=1,...,n 均可在单位时间内完成。
每个作业 i 都有一个期限值 d 
i
​
 >0，（ d 
i
​
  是整数）。
当且仅当作业 i 在它的截止期限前被完成时获得 p 
i
​
 >0 的效益；
问题的可行解是这 n 个作业的一个子集合。集合中的每个作业都能在各自的截止期限之前完成，产生一个作业效益之和 ∑p 
i
​
  。具有最大效益值的可行解就是最优解。
输入格式:
第一行为一个正整数n，表示作业的个数；
接下来的 n 行，每行两个正整数（中间用空格隔开），表示每个作业 i 的截止期限 d 
i
​
  和按期完成产生的效益p 
i
​
 。
输出格式:
一行一个整数，给出最优解的效益值。
输入样例1:
4
1 20
2 15
2 100
1 10
输出样例1:
120
输入样例2:
6
2 25
3 20
3 15
2 10
4 1
4 5 
输出样例2:
65
数据范围
d 
i
​
 ≤n≤10 
6
 ,p 
i
​
 ≤10 
9
 

Code Size Limit
16 KB
Time Limit
1000 ms
Memory Limit
512 MB
Stack size limit
8192 KB
```

``` markdown
5 买股票问题
Score 100
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
对该股票可以进行多次买卖操作，请设计一个算法,来计算所能获取的最大利润。注意，在对该股票买卖操作过程中,要求在再次购买前,出售掉之前的股票。

输入格式:
第 1 行1个整数n, 表示数组元素数。

第2行n个整数，表示股票价格。

输出格式:
一个整数，表示所能获得的最大利润。

输入样例1:
6
7 1 5 3 6 4
输出样例1:
7
解释：在第 2 天买入，在第 3 天卖出, 获得利润 = 5-1 = 4 。随后，在第 4 天买入，在第 5 天卖出, 获得利润 = 6-3 = 3 。

输入样例2:
5
1 2 3 4 5
输出样例2:
4
Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB
Stack size limit
8192 KB
```


``` markdown
6 集合问题
Score 100
给定n个集合A1，A2，…，An，每个集合都由连续的正整数构成，即
Ai={x| ai<= x<= bi}， i=1,2,...,n
设计一个算法求最小的集合S，使得对每个i=1,2,...,n，|S ∩Ai|≠∅,即每个Ai至少含有S中的一个数。

输入格式:
第1行是n，表示集合的个数；
第2行到第n+1行分别是这n个集合的最小正整数和最大正整数。

输出格式:
第1行是集合S，按照从小到大的顺序。

输入样例1:
5
1 6
3 4
2 8
4 10
3 7
输出样例1:
4
输入样例2:
5
1 7
7 9
5 8
2 6
9 10
输出样例2:
6 9
Code Size Limit
16 KB
Time Limit
100 ms
Memory Limit
64 MB
Stack size limit
8192 KB

```