TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

80.0% (12/15)

Submission's AC Ratio

40.9% (56/137)

Tags

Description

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

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

Input Format

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

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

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

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

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