TopCoder

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

User's AC Ratio

69.6% (16/23)

Submission's AC Ratio

20.5% (56/273)

Tags

Description

你聽過「斯克兒悠斯」嗎?對,就是傳說中的天平秤。

據說天平秤出現於遠古時代。那時盤古開天闢地,上帝創造人類,魔法少女小向剛拿到IMO(International Magic Olympiad)的金牌。
那時,周逸讀完周易後不小心把天空周異(JE)了,於是女媧只好去找石頭來補天空。

可是問題來了,他不知道怎麼找石頭來補,因為他沒辦法比較那些石頭的重量。要知道,能補天的石頭不是一般的地磅可以量的出來的。
於是女媧前往重量之神CBD的神廟前尋求重量之神CBD的協助,因為傳說中重量之神可以精確地量出任何東西的重量。

女媧找到CBD後,和CBD說明了事情經過,CBD於是決定幫助她,拿出了傳家之寶—天平秤。

啊不對,是這個。

這個天平秤很厲害,不管多重的東西都可量。
天平秤有4個平台A、B、C、D,其中ABC3個平台,你只要把東西放上去,就可以量出誰最重、誰在中間、誰最輕,而要是在D上面擺東西的話,他還會告訴你ABC中比D重的那些裡最輕的那個是哪個,當然如果ABC都比D輕,那他會告訴你ABC誰最輕。

但是問題來了,這個天平秤必須用魔法指令來操作,但是女媧只會補天不會寫魔法指令,他只好找了你,天龍國立天龍大學魔法工程系的高才生,來幫忙編寫魔法指令,事後他會送你一顆補天用剩的石頭給你,你可以拿去壓泡菜。

Input Format

這題不需要輸入,如果你輸入了任何東西,你將得到一個WA

天平秤提供了你以下幾個魔法函數,請#include "lib1885.h"之後,依照規定呼叫這些函數。

int Init();:請在一開始呼叫,將回傳一個整數T,代表共有T個天空要補,每個天空都有6顆石頭,編號為1到6。
void orderCoins();:對於每個要補的天空,請在一開始呼叫這個函數,之後才可以呼叫以下函數。
void answer(int[]);:在呼叫上面的函數後,請在完成女媧的要求後呼叫這個函數,並傳入一個大小為6的陣列,依序代表最輕到最重的石頭編號。
以下4個函數,可以讓你查詢編號1到6的石頭的大小順序,其中A,B,C,D代表石頭的編號,不可以相同。
getHeaviest(A, B, C):回傳ABC中最重的石頭編號。
getLightest(A, B, C):回傳ABC中最輕的石頭編號。
getMedian(A, B, C):回傳ABC中第2重的石頭編號。
getNextLightest(A, B, C, D):如果ABC都比D輕,回傳ABC最輕的石頭編號,如果ABC之中有石頭比D重,回傳比D重的石頭中最輕的石頭編號。

Output Format

這題不需要輸出,如果你輸出了任何東西,你將得到一個WA

請按照規定呼叫給定的函數,呼叫最後4個比較函數getLightest(), getHeaviest(), getMedian() 和 getNextLightest()的總次數不可以超過Q次,否則你會得到一個WA(Q是對任何序列,用最佳策略排序所需要的次數)。

Hints

假設石頭從最輕到最重的編號是 3 4 6 2 1 5。

  • getMedian(4, 5, 6) return 6,6是三者中第2重的。
  • getHeaviest(3, 1, 2) return 1,1是三者中最重的。
  • getNextLightest(2, 3, 4, 5) return 3,234都比5輕,所以回傳當中最輕的3。
  • getNextLightest(1, 6, 3, 4) return 6,1跟6比4重,1和6中最輕的是6。
  • getHeaviest(3, 5, 6) return 5,5是三者中最重的。
  • getMedian(1, 5, 6) return 1,1是三者中第2重的。
  • getMedian(2, 4, 6) return 6,6是三者中第2重的。
  • answer([3, 4, 6, 2, 1, 5]),你成功的排序了這6顆石頭。

後記:於是天空就被補起來了,而CBD決定去吃早餐,這又是另外一個故事了。

Problem Source

IOI 2015 Day 1
Problem set / Description by 果茶

Subtasks

No. Testdata Range Score
1 0 2
2 1 3
3 2 2
4 3 3
5 4 2
6 5 3
7 6 2
8 7 3
9 8 2
10 9 3
11 10 2
12 11 3
13 12 2
14 13 3
15 14 2
16 15 3
17 16 2
18 17 3
19 18 2
20 19 3
21 20 2
22 21 3
23 22 2
24 23 3
25 24 2
26 25 3
27 26 2
28 27 3
29 28 2
30 29 3
31 30 2
32 31 3
33 32 2
34 33 3
35 34 2
36 35 3
37 36 2
38 37 3
39 38 2
40 39 3

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10
10 1000 65536 262144 11
11 1000 65536 262144 12
12 1000 65536 262144 13
13 1000 65536 262144 14
14 1000 65536 262144 15
15 1000 65536 262144 16
16 1000 65536 262144 17
17 1000 65536 262144 18
18 1000 65536 262144 19
19 1000 65536 262144 20
20 1000 65536 262144 21
21 1000 65536 262144 22
22 1000 65536 262144 23
23 1000 65536 262144 24
24 1000 65536 262144 25
25 1000 65536 262144 26
26 1000 65536 262144 27
27 1000 65536 262144 28
28 1000 65536 262144 29
29 1000 65536 262144 30
30 1000 65536 262144 31
31 1000 65536 262144 32
32 1000 65536 262144 33
33 1000 65536 262144 34
34 1000 65536 262144 35
35 1000 65536 262144 36
36 1000 65536 262144 37
37 1000 65536 262144 38
38 1000 65536 262144 39
39 1000 65536 262144 40