我在心中想了一個 1 到 N 的排列 p1,p2,...,pN,你有辦法猜到這個排列是多少嗎?每當你猜了一個序列,我可以告訴你猜的序列是不是這個排列的子序列。但你最多只能猜
⌈N log2 N⌉ + 1 次,所以你要好好選擇你猜的序列。
「1 到 N 的排列 p1,p2,...,pN」是指 p1,p2,...,pN 兩兩互不相同,1 到 N 每個數字都恰好在 pi 出現一次。
我們說一個序列 a1,a2,...,ak 是排列 p1,p2,...,pN 的子序列,若且唯若存在 1 ≤ i1 < i2 < ··· < ik ≤ N 使得 aj = pij。例如,排列 [2,4,1,3,5] 的子序列有 [2]、[2,3]、[4,3,5]、
[2,4,1,5]、[2,1,3] 等等,而 [3,3,3]、[1,3,2,1,1]、[3,4,5]、[2,1,5,4]、[1,3,3]、[4,3,1] 等等則不是 [2,4,1,3,5] 的子序列。
你的標準輸入第一行會有一個正整數 N 代表我想的排列的長度。
當你的程式打算要猜一個長度 K 的序列時,輸出一行且包含 K + 1 個整數,以空白隔開。第一個整數是 K 代表你要猜的序列的長度,接下來 K 個整數 a1,a2,...,aK 是你要猜的序列的內容。你的猜測必須符合 1 ≤ K ≤ N 且 ∀1 ≤ i ≤ K,1 ≤ ai ≤ N,否則你可能會得到 Wrong
Answer。當你猜完序列後,記得要清空 (flush) 標準輸出 (standard out)。
當我們收到你的猜測後,會把你猜的結果回覆到你的標準輸入 (standard in)。回覆會是下列三種:
當你猜到了正確排列後,你的程式必須立刻結束 (exit)。如果你在限制次數內都沒有猜對,你的程式將會被強制中止。
以下是 C++ 程式 flush 的範例:
#include <iostream> int main() { std::cout << "5 1 2 3 4 5\n"; std::cout << std::flush; } |
1 2 3 4 5
以下是 C 程式 flush 的範例:
#include <stdio.h> int main() { printf("5 1 2 3 4 5\n"); fflush(stdout); } |
1 2 3 4 5
你可以用以下的程式碼來得到每個 N 相對應的次數限制。
#include <iostream> #include <cmath> int main() { int N; std::cin >> N; int X = ceil(N * log2l(N)) + 1; std::cout << X << std::endl; } |
1 2 3 4 5 6 7
8
#include <stdio.h> #include <math.h> int main() { int N; scanf("%d", &N); int X = ceil(N * log2l(N)) + 1; printf("%d\n", X); } |
5 Nie Tak Nie Nie Tak Gotowe
3 1 2 3 3 2 1 3 3 3 3 3 5 1 3 2 1 1 3 4 3 5 5 2 4 1 3 5
左側表示評測系統的輸出(你可以用標準輸入 (standard in) 讀入),右側則代表你一種合法的詢問。在範例測資中,我心裡所想的祕密排列是 [2,4,1,3,5]。評測系統首先輸出 5 表示這個排列的長度是 5。接著你依序向評測系統猜了 [1,2,3]、[2,1,3]、[3,3,3]、
[1,3,2,1,1]、[4,3,5],並依序得到Nie、Tak、Nie、Nie、Tak的回覆。最後,花了一次猜測來猜中正確的排列,即 [2,4,1,3,5]。
在你得到Gotowe的回覆,即你得知你猜中正確答案後,你的程式必須立即結束。
補充來說,你至少會需要花費一次 K = N 的猜測來猜出正確答案。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |