6938: 爆破VS凤凰

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:7 通过:4

题目描述

Er-pang又跟生哥去网吧打LOL(英雄联盟),er-pang还是用他最爱的爆破鬼才-吉格斯,生哥还是用他花重金买下的冰晶凤凰-艾尼维亚。每次生哥都被虐的很惨。

生哥终于忍不住了,他居然开挂了!

开了挂后的凤凰越飞越高,居然还出现了n-1个幻象(逆天了),加上本尊一共n个凤凰在天上乱飞。由于爆破鬼才的视力极好,可以在瞬间扔出炸弹并炸死凤凰或是幻象。所以我们可以看做三维立体空间中有n个不动的凤凰,每个凤凰有一个坐标(xyz)。爆破鬼才的炸弹爆炸后不会消失,而且还会跳跃,但仅能跳到更高的地方。即如果炸弹当前处在(x1y1z1),当且仅当x2>x1y2>y1z2>z1时,它会跳到(x2y2z2)。

举个例子:凤凰在(000) (110) (111) (222)时

一个合法的炸弹弹跳序列是{1,3,4}

一个不合法的炸弹弹跳序列是{1,2,4}

现在告诉你n个凤凰的精确位置,问你两个问题:

1.  爆破鬼才扔出一个炸弹最少能炸死多少凤凰

2.  爆破鬼才至少需要扔出多少个炸弹才能将凤凰全部炸死


输入格式

第一行一个整数为n,表示天空中有n个凤凰。

接下来的n行每行有三个非负整数xiyizi表示凤凰的位置,保证任意两个凤凰不会出现在同一位置。

输出格式

输出文件有且仅有两行。

第一行输出一个整数表示一个炸弹最多能炸死多少个凤凰

第二行输出一个整数表示至少需要多少个炸弹才能炸死全部的凤凰

输入样例 复制

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

输出样例 复制

3
2

数据范围与提示

所有坐标都是0~1000000的整数

30% n<=30

50% n<=100

100% n<=1000