a212: B. 猜排列
標籤 : 2022國中組初賽
通過比率 : 3人/7人 ( 43% ) [非即時]
評分方式:
Strictly

最近更新 : 2023-08-09 13:03

內容

2022 網際網路程式設計全國大賽 國中組初賽

我在心中想了一個 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)。回覆會是下列三種:

  • “Nie” 如果你猜的序列不是任何是我想的排列的子序列
  • “Tak” 如果你猜的序列是我想的排列的子序列
  • “Gotowe” 如果你猜到了

當你猜到了正確排列後,你的程式必須立刻結束 (exit)。如果你在限制次數內都沒有猜對,你的程式將會被強制中止。

  • 1 ≤ N ≤ 500

以下是 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
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (1%): 1.0s , <1K
公開 測資點#1 (1%): 1.0s , <1K
公開 測資點#2 (1%): 1.0s , <1K
公開 測資點#3 (1%): 1.0s , <1K
公開 測資點#4 (1%): 1.0s , <1K
公開 測資點#5 (1%): 1.0s , <1K
公開 測資點#6 (1%): 1.0s , <1K
公開 測資點#7 (1%): 1.0s , <1K
公開 測資點#8 (1%): 1.0s , <1K
公開 測資點#9 (1%): 1.0s , <1K
公開 測資點#10 (1%): 1.0s , <1K
公開 測資點#11 (1%): 1.0s , <1K
公開 測資點#12 (1%): 1.0s , <1K
公開 測資點#13 (1%): 1.0s , <1K
公開 測資點#14 (1%): 1.0s , <1K
公開 測資點#15 (1%): 1.0s , <1K
公開 測資點#16 (1%): 1.0s , <1K
公開 測資點#17 (1%): 1.0s , <1K
公開 測資點#18 (1%): 1.0s , <1K
公開 測資點#19 (1%): 1.0s , <1K
公開 測資點#20 (1%): 1.0s , <1K
公開 測資點#21 (1%): 1.0s , <1K
公開 測資點#22 (1%): 1.0s , <1K
公開 測資點#23 (1%): 1.0s , <1K
公開 測資點#24 (1%): 1.0s , <1K
公開 測資點#25 (1%): 1.0s , <1K
公開 測資點#26 (1%): 1.0s , <1K
公開 測資點#27 (1%): 1.0s , <1K
公開 測資點#28 (1%): 1.0s , <1K
公開 測資點#29 (1%): 1.0s , <1K
公開 測資點#30 (1%): 1.0s , <1K
公開 測資點#31 (1%): 1.0s , <1K
公開 測資點#32 (1%): 1.0s , <1K
公開 測資點#33 (1%): 1.0s , <1K
公開 測資點#34 (1%): 1.0s , <1K
公開 測資點#35 (1%): 1.0s , <1K
公開 測資點#36 (1%): 1.0s , <1K
公開 測資點#37 (1%): 1.0s , <1K
公開 測資點#38 (1%): 1.0s , <1K
公開 測資點#39 (1%): 1.0s , <1K
公開 測資點#40 (1%): 1.0s , <1K
公開 測資點#41 (1%): 1.0s , <1K
公開 測資點#42 (1%): 1.0s , <1K
公開 測資點#43 (1%): 1.0s , <1K
公開 測資點#44 (1%): 1.0s , <1K
公開 測資點#45 (1%): 1.0s , <1K
公開 測資點#46 (2%): 1.0s , <1K
公開 測資點#47 (2%): 1.0s , <1K
公開 測資點#48 (2%): 1.0s , <1K
公開 測資點#49 (2%): 1.0s , <1K
公開 測資點#50 (2%): 1.0s , <1K
公開 測資點#51 (2%): 1.0s , <1K
公開 測資點#52 (2%): 1.0s , <1K
公開 測資點#53 (2%): 1.0s , <1K
公開 測資點#54 (2%): 1.0s , <1K
公開 測資點#55 (2%): 1.0s , <1K
公開 測資點#56 (2%): 1.0s , <1K
公開 測資點#57 (2%): 1.0s , <1K
公開 測資點#58 (2%): 1.0s , <1K
公開 測資點#59 (2%): 1.0s , <1K
公開 測資點#60 (2%): 1.0s , <1K
公開 測資點#61 (2%): 1.0s , <1K
公開 測資點#62 (2%): 1.0s , <1K
公開 測資點#63 (2%): 1.0s , <1K
公開 測資點#64 (2%): 1.0s , <1K
公開 測資點#65 (2%): 1.0s , <1K
公開 測資點#66 (2%): 1.0s , <1K
公開 測資點#67 (2%): 1.0s , <1K
公開 測資點#68 (2%): 1.0s , <1K
公開 測資點#69 (2%): 1.0s , <1K
公開 測資點#70 (2%): 1.0s , <1K
公開 測資點#71 (2%): 1.0s , <1K
公開 測資點#72 (2%): 1.0s , <1K
提示 :

左側表示評測系統的輸出(你可以用標準輸入 (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 的猜測來猜出正確答案。

標籤:
2022國中組初賽
出處:
NPSC [管理者:
zero (管理員)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」