1339 問(wèn)題 I: 三維導(dǎo)彈攔截
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 23 解決: 0
題目描述
一場(chǎng)戰(zhàn)爭(zhēng)正在A國(guó)與B國(guó)之間如火如荼的展開(kāi)。
B國(guó)憑借其強(qiáng)大的經(jīng)濟(jì)實(shí)力開(kāi)發(fā)出了無(wú)數(shù)的遠(yuǎn)程攻擊導(dǎo)彈，B國(guó)的領(lǐng)導(dǎo)人希望，通過(guò)這些導(dǎo)彈直接毀滅A國(guó)的指揮部，從而取得戰(zhàn)斗的勝利！當(dāng)然，A國(guó)人民不會(huì)允許這樣的事情發(fā)生，所以這個(gè)世界上還存在攔截導(dǎo)彈。
現(xiàn)在，你是一名A國(guó)負(fù)責(zé)導(dǎo)彈攔截的高級(jí)助理。
B國(guó)的導(dǎo)彈有效的形成了三維立體打擊，我們可以將這些導(dǎo)彈的位置抽象三維中間的點(diǎn)（大小忽略），為了簡(jiǎn)單起見(jiàn)，我們只考慮一個(gè)瞬時(shí)的狀態(tài)，即他們靜止的狀態(tài)。
攔截導(dǎo)彈設(shè)計(jì)非常精良，可以精準(zhǔn)的引爆對(duì)方導(dǎo)彈而不需要自身?yè)p失，但是A國(guó)面臨的一個(gè)技術(shù)難題是，這些導(dǎo)彈只懂得直線上升。精確的說(shuō)，這里的直線上升指xyz三維坐標(biāo)單調(diào)上升。
給所有的B國(guó)導(dǎo)彈按照1至N標(biāo)號(hào)，一枚攔截導(dǎo)彈可以打擊的對(duì)象可以用一個(gè)xyz嚴(yán)格單調(diào)上升的序列來(lái)表示，例如：
B國(guó)導(dǎo)彈位置：(0, 0, 0) (1, 1, 0) (1, 1, 1), (2, 2, 2)
一個(gè)合法的打擊序列為：{1, 3, 4}
一個(gè)不合法的打擊序列為{1, 2, 4}
A國(guó)領(lǐng)導(dǎo)人將一份導(dǎo)彈位置的清單交給你，并且向你提出了兩個(gè)最簡(jiǎn)單不過(guò)的問(wèn)題（假裝它最簡(jiǎn)單吧）：
1．一枚攔截導(dǎo)彈最多可以摧毀多少B國(guó)的導(dǎo)彈？
2．最少使用多少攔截導(dǎo)彈才能摧毀B國(guó)的所有導(dǎo)彈？
不管是為了個(gè)人榮譽(yù)還是國(guó)家容易，更多的是為了飯碗，你，都應(yīng)該好好的把這個(gè)問(wèn)題解決掉！
輸入
第一行一個(gè)整數(shù)N給出B國(guó)導(dǎo)彈的數(shù)目。
接下來(lái)N行每行三個(gè)非負(fù)整數(shù)Xi, Yi, Zi給出一個(gè)導(dǎo)彈的位置，你可以假定任意兩個(gè)導(dǎo)彈不會(huì)出現(xiàn)在同一位置。
輸出
輸出有且僅有兩行。
第一行輸出一個(gè)整數(shù)P，表示一枚攔截導(dǎo)彈之多能夠摧毀的導(dǎo)彈數(shù)。
第二行輸出一個(gè)整數(shù)Q，表示至少需要的攔截導(dǎo)彈數(shù)目。
樣例輸入
4
0 0 0
1 1 0
1 1 1
2 2 2
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情