TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

80.0% (12/15)

Submission's AC Ratio

40.9% (56/137)

Tags

Description

拉密(Rummikub)是一個四個人玩的遊戲。某天盩僰麌發現支援N人同時遊玩的擴展拉密(ExtRummikub)推出了,於是他興高采烈的找了$N-1$個人跟他一起玩。可是有些人覺得他們坐的位子風水很不好,導致自己會一直輸,所以他們每個人都選了一個自己想坐的位子編號(從0編號到$N-1$),而剛好他們沒有兩個人想坐同一個位子。
但是愛搞怪的盩僰麌不想要直接就換過去,決定叫大家玩一個遊戲,要贏得這個遊戲才能換位置:拿出N張拉密牌,從0編號到$N-1$(因為是ExtRummikub,所以不用擔心牌的數字有上界),洗牌之後放在一個房間裡,由左到右排成一直列。因為牌是蓋起來的,所以看不出來每張牌的編號,除非把它翻開。
接著,每個人輪流進到房間中,他可以看從左數來第$i$張牌的編號,最多重複$R\times N$次($0<R\leq 1$)。如果每個人都能在這$R\times N$次之內找到編號等於他們想去位置的那張牌,就算贏得了這場遊戲。

因為每個人都想換到自己的位子,所以他們可以在進去房間之前討論進去房間之後的策略。當然,為了避免第一個人進去就把牌按照順序擺好或者把所有牌的位置記住,盩僰麌規定每個人(包括他自己)進去的時候都不能動牌堆的順序。而每個人從房間中出來之後,盩僰麌會以一種特殊的方式洗牌:隨機決定一個0到$N-1$的排列$p_0,p_1,\cdots,p_{N-1}$,對於洗牌前從左數來第$i$張牌,如果它的編號是$a_i$,則洗牌之後,編號$p_{a_i}$的牌會是從左數來第$p_i$張牌。
請你寫一個程式幫助這些人,讓他們有最高的機率可以成功贏得這場遊戲。

Input Format

本題沒有輸入,如果你輸入了任何東西,可能會導致各種不可預期的結果。

請記得#include "lib2056.h"。以下是幾個你可以使用的函式:

int Testcase():請在程式開始時呼叫,這個函式會回傳該筆測資的回合數$T$。
int Init():請於每個回合開始前呼叫,這個函式會回傳$N$,代表這回合有$N$個人在玩擴展拉密。
接著你必須照編號$0$到$N - 1$的順序,對於每個人$i$使用下面兩個函式來詢問並猜測第幾張拉密的編號是那個人想要的位置編號。
int Query(int p):你可以呼叫這個函式來得到從左數來第$p$張拉密的編號,注意若對於任何一人你使用超過$N \times R$的int Query(int),不論你最後有沒有回報正確的答案,你都會輸掉這回合(但是你還是得照常完成這個回合)。
void Answer(int q):當你確定從左數來第$q$張牌的編號等於第$i$個人的位子時,請呼叫此函式。若猜錯,你將輸掉這回合(但是你還是得照常完成這個回合)。
呼叫完此函式後程式會自動進行到下一個人的階段。當$N$個人的階段都結束之後,程式會自動執行到下一回合。如果在這個回合中,每一個人的階段都有正確回報位置,且詢問次數沒有超過限制,你就贏得了這回合。

如果在一筆測資的$T$回合中,你贏得了至少$P\times T$回合,你會獲得一個AC。
對於全部測資,$T \leq 3000$。

Output Format

本題沒有輸出。

Hints

以下是一個保證格式正確(不會CE也不會REMLE)但只能讓你獲得1分的範例程式:

#include "lib2056.h"

int main() {
  int t = Testcase();
  while (t--) {
    int n = Init();
    for (int i = 0; i < n; ++i) {
      int p = Query(i);
      Answer(i);
    }
  }
}

Problem Source

Problem Set by WeaK, waynetuinfor
Description by Yihda Yol

Subtasks

No. Testdata Range Constraints Score
1 0 $N=1,R=1,P=1$ 1
2 1~3 $N=50,R=1,P=1$ 8
3 4~6 $N=100,R=0.7,P=0.3$ 37
4 7~9 $N=100,R=0.5,P=0.25$ 54

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 950 65536 262144 1
1 950 65536 262144 2
2 950 65536 262144 2
3 950 65536 262144 2
4 950 65536 262144 3
5 950 65536 262144 3
6 950 65536 262144 3
7 950 65536 262144 4
8 950 65536 262144 4
9 950 65536 262144 4