/ C++党 / 题库 /

[noip1999]导弹拦截

[noip1999]导弹拦截

时间限制:1s 空间限制:1024KiB


题目来源

本题是1999年提高组的第一题(难度:普及-),希望你能把它做出来,加油!!!^_^

题目描述

小Q的爸爸是国防部部长,有一天他愁眉苦脸地对小Q说,这一天雷达捕捉到敌国的导弹来袭,虽然国防部为了防御敌国的导弹击,发明出一种导弹拦截系统。但是这种导弹拦截系统有一个很中重大的缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
现在,小Q知道了导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),请你告诉小Q这套系统最多能拦截多少导弹以及如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出格式

输入格式:

给出一组数据,表示导弹依次飞来的高度,注意有多少枚导弹是不知道的。

输出格式:

第1行请输出一个整数,表示1套系统最多能拦截的导弹数;
第2行请再输出一个整数,表示要拦截所有导弹最少要配备的系统数。

输入输出样例

Input #1

389 207 155 300 299 170 158 65 

Output #1

6
2

时间和空间限制

每个测试点时间1s,空间1024KiB。

数据范围约定

100%的数据保证导弹的数量小于20,每一枚导弹的高度小于30000。

提供者

Vijos 梁忆炎