1640 . 情報偵察活動 [含 problem set pdf檔]
TopCoder
Tags
Description
Skyly & Shik Contest II, Problem Set (Printable Version, PDF Document)
艾斯特王國和班雷納帝國位於安地那地區的二隅，長期以來由於中央綿長的山脈這個天然屏障阻擋，雙方並沒有什麼交集。
直到某一次，為了開墾中央山脈的稀有礦產，雙方之間開始起了爭執，互不相讓。而這個衝突越演越烈，到了現在，戰爭一觸即發！
現在，你是艾斯特王國的大斥侯，為了避免戰爭開始之後對上武力強大的班雷納帝國便馬上趨於劣勢，你決定派出手下的偵察兵潛入敵營中偵察情報！
你在事前已經知道，班雷納帝國總共有 N 支部隊，每一個部隊有所屬的士兵，而第 i 個部隊的總戰鬥力可以被特化成一個戰鬥值 Ai，Ai 越大表示第 i 個部隊越強。
班雷納帝國有兩支強大的部隊，最強的是皇族親衛隊，第二強的則是 S 部隊，對艾斯特王國而言，當然不想要正面衝突這兩支強大的部隊，
於是便請你想辦法找出這兩支部隊在總共 N 支部隊中的位置（位置編號為 1 到 N ）。
但是，你所擁有的時間不足夠你慢慢的進行偵察行動，況且，偵察的時間花費的越久，被對方發現的機會就愈大！
每一次的偵察行動可以得知被排在位置 i 和位置 j 的部隊哪一個戰鬥值較大（即得知 Ai > Aj 或 Aj > Ai ），
那麼，你究竟至少需要多少次的偵察行動才能保證在最差情況下依然能夠確切的得知皇族親衛隊和 S 部隊在軍隊編排中的位置呢？
Input Format
測試資料有多筆詢問。對於每一筆的詢問，都是以一行且僅有一個整數 N，代表班雷納帝國的部隊數量。
測試資料以 N = -1 作為結尾（你不應該對這一筆詢問作出回答）。
對於所有的測試資料，保證 2 ≤ N ≤ 2×109，且 Ai ≠ Aj , ∀ i ≠ j。
Output Format
對於測試資料中的每一筆的詢問，請輸出 N 和一個整數 P 代表至少要 P 次的偵察行動，並在中間以一個空白字元（ascii值 32）作為間隔。
Sample Input 1
2
3
-1
3
-1
Sample Output 1
2 1
3 3
3 3
Hints
Problem Source
原TIOJ1640 / Skyly & Shik Contest II (Problem A)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |