比赛场次 | 232 |
---|---|
比赛名称 | 20140421 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2014-04-21 08:00:00 |
结束时间 | 2014-04-21 11:30:00 |
开放分组 | 全部用户 |
注释介绍 |
题目名称 | 导弹拦截 |
---|---|
输入输出 | bomba.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
GDFRWMY | AAAAAAEAEA | 0.183 s | 5.20 MiB | 80 |
cstdio | AWWWWWAAWW | 0.060 s | 0.36 MiB | 30 |
Dijkstra | WWWWWWAAWW | 0.011 s | 0.33 MiB | 20 |
隨風巽 | WWWWWWAAWW | 0.025 s | 0.35 MiB | 20 |
digital-T | WWWWWWWAWA | 0.328 s | 0.31 MiB | 20 |
超级傲娇的AC酱 | WWWWWWAAWW | 0.618 s | 0.32 MiB | 20 |
Cirno | C | 0.000 s | 0.00 MiB | 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,表示至少需要的拦截导弹数目。
【数据约定】
所有的坐标都是[0,10^6]的整数
对于30%的数据满足N < 31
对于50%的数据满足N < 101
对于100%的数据满足N < 1001
【样例】
输入样例1
4
0 0 0
1 1 0
1 1 1
2 2 2
输出样例1
3
2
输入样例2
4
0 0 0
1 0 0
0 1 0
0 0 1
输出样例2
1
4