Dotcpp  >  编程题库  >  三维导弹拦截
题目 1339:

三维导弹拦截

时间限制: 2s 内存限制: 192MB 提交: 21 解决: 0

题目描述

一场战争正在A国与B国之间如火如荼的展开。 B国凭借其强大的经济实力开发出了无数的远程攻击导弹,B国的领导人希望,通过这些导弹直接毁灭A国的指挥部,从而取得战斗的胜利!当然,A国人民不会允许这样的事情发生,所以这个世界上还存在拦截导弹。 现在,你是一名A国负责导弹拦截的高级助理。 B国的导弹有效的形成了三维立体打击,我们可以将这些导弹的位置抽象三维中间的点(大小忽略),为了简单起见,我们只考虑一个瞬时的状态,即他们静止的状态。 拦截导弹设计非常精良,可以精准的引爆对方导弹而不需要自身损失,但是A国面临的一个技术难题是,这些导弹只懂得直线上升。精确的说,这里的直线上升指xyz三维坐标单调上升。 给所有的B国导弹按照1至N标号,一枚拦截导弹可以打击的对象可以用一个xyz严格单调上升的序列来表示,例如: B国导弹位置:(0,  0,  0)  (1,  1,  0)  (1,  1,  1),  (2,  2,  2) 一个合法的打击序列为:{1,  3,  4} 一个不合法的打击序列为{1,  2,  4} A国领导人将一份导弹位置的清单交给你,并且向你提出了两个最简单不过的问题(假装它最简单吧): 1.一枚拦截导弹最多可以摧毁多少B国的导弹? 2.最少使用多少拦截导弹才能摧毁B国的所有导弹? 不管是为了个人荣誉还是国家容易,更多的是为了饭碗,你,都应该好好的把这个问题解决掉!

输入格式

第一行一个整数N给出B国导弹的数目。 接下来N行每行三个非负整数Xi,  Yi,  Zi给出一个导弹的位置,你可以假定任意两个导弹不会出现在同一位置。

输出格式

输出有且仅有两行。 第一行输出一个整数P,表示一枚拦截导弹之多能够摧毁的导弹数。 第二行输出一个整数Q,表示至少需要的拦截导弹数目。

样例输入

4		
0 0 0	
1 1 0
1 1 1
2 2 2

样例输出

3
2

提示

零基础同学可以先学习视频课程,包含C/C++、Python、百练、蓝桥杯辅导、算法数据结构等课程,提供视频讲解以及配套习题,还有老师答疑,点击这里了解课程详情
标签