TopCoder

User's AC Ratio

66.7% (4/6)

Submission's AC Ratio

40.0% (6/15)

Tags

Description

本題為互動題,限用 C++ 作答。

小菫跟小薺是感情很好的一對姐妹,她們想要在學校的文化體育祭上擺設猜餅乾的攤位!

為了擺設攤位,小菫跟小薺打算到小橘開設的「黑色薔薇」烘焙坊購買一些手工餅乾。黑色薔薇烘焙坊一共販售 $N$ 種不同口味的餅乾,每一種口味依序以 $1$ 到 $N$ 的正整數編號。在猜餅乾的活動中,她們準備了一個盒子,並且選擇 $N$ 塊餅乾排成一列放入盒中。假設由左到右第 $i$ 塊餅乾的口味為 $a_i$,這 $N$ 塊餅乾的口味會以非嚴格遞增的方式排列,也就是說,對於所有的 $1 \le i < N$,皆滿足 $a_i \le a_{i+1}$。在決定好餅乾的順序後,她們會把盒子蓋起來,不讓客人看到裡面的餅乾口味。

當一位客人來到攤位時,猜餅乾的遊戲就正式開始了!首先,小菫跟小薺會先告訴客人餅乾的數量 $N$,接下來就輪到客人開始猜測盒子裡面的餅乾依序是哪些口味了。每次猜測時,客人必須猜測盒子裡的餅乾依序是哪幾種口味,猜測時這 $N$ 塊餅乾的口味也要以非嚴格遞增的方式排序。也就是說,假設客人猜測由左到右第 $i$ 塊餅乾的口味為 $b_i$,則對於所有的 $1 \le i < N$,也必須滿足 $b_i \le b_{i+1}$。

在客人猜完餅乾的種類後,小菫跟小薺會在盒子上貼上一些不同顏色的標籤給客人一些提示。首先,對於每一塊餅乾,假設客人猜測的口味與盒子中的口味相同,則她們會在那個位置貼上綠色的標籤。接下來,對於每一種不同的口味,她們會計算該種口味在盒子裡出現的次數 $x$ 以及客人的猜測中該種口味出現的次數 $y$。如果 $y>x$,則她們會由右向左將前 $y-x$ 塊放著該種口味的餅乾且尚未被貼上綠色標籤的位置貼上灰色標籤。而對於剩下的位置,她們會貼上黃色的標籤。

舉例來說,如果餅乾口味的數量 $N=7$,並且盒子裡放著的餅乾口味 $a$ 為 $[2, 3, 3, 3, 5, 5, 7]$,則一些可能的猜測及這個猜測會被貼上的標籤如下圖所示。每一個橫行表示一次客人的猜測,方格中的數字表示猜測的口味,方格的顏色表示被貼上的標籤顏色。

小夜是小菫和小薺的粉絲,為了吸引她們的注意,她希望在 $5$ 次猜測以內正確得出所有餅乾的口味。你可以寫一支程式幫助她嗎?

以下是一些可以幫助到你的函式,首先請在你的程式碼第一行引入標頭檔 lib0023.h,就可以使用以下的函式:

  • int Init():請在程式的一開始呼叫,系統會回傳一個正整數代表餅乾口味的數量。
  • string Query(vector<int> vec):每次呼叫可以猜測餅乾的口味,vec 的每一項依序表示要猜測的每片餅乾的口味,系統會回傳一個長度為 $N$ 的字串 $s$,其中第 $i$ 個字元 $s_i$ 表示第 $i$ 個位置被貼上的標籤顏色。其中,字元「A」表示綠色,「B」表示黃色,「C」表示灰色。
  • void Answer(vector<int> vec):請呼叫此函數將你認為的正確答案 vec 傳送給系統,在呼叫此函式後,系統會自動結束你的程式。

Input Format

本題沒有輸入,隨意輸入將會得到不可預期的結果。

  • $1 \leq N \leq 5 \times 10^ 5$

Output Format

本題沒有輸出,隨意輸出將會得到不可預期的結果。

Hints

以下為一個不會 CE 但也不會 AC 的範例程式:

#include <bits/stdc++.h>
#include "lib0023.h"
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int N = Init();
    vector <int> vec(N);
    for (int i = 0; i < N; ++i) {
        vec[i] = i + 1;
    }
    string res = Query(vec);
    Answer(vec);
}

Problem Source

2023 NPSC 高中組決賽

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~23 無特別限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1
1 1000 524288 65536 1
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2