2016年2月25日 星期四

[HOJ 278][GCJ 2013 2]Many Prizes (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 278 - Many Prizes

Problem Statistics
Solved Member: 16  Submission: 40  User Tried: 16
Problem:
瀚瀚國準備辦一個有2N個隊伍的競賽,並準備了P份獎品要給Rank 0..P-1的隊伍。

這些隊伍由0至2N-1編號,當i與j會競賽的時候,隊伍i會勝利僅當i < j。

一開始這些這些隊伍會以一種排列的方式顯示於競賽名單上,而競賽名單會影響到競賽的結果。

你的任務是找一個可能獲得獎品且編號最大的隊伍。

競賽將會經過N個回合,每個隊伍將會有一個競賽紀錄,以W表示勝利,以L表示失敗,若有一個隊伍第一場獲勝,第二場失敗,第三場獲勝,則他的競賽紀錄會顯示為[W, L, W],而一個隊伍若還沒有比過任何一場競賽則會顯示為[ ]。

對於每個回合,每個隊伍會與跟自己競賽紀錄相同的隊伍競賽,在相同競賽紀錄的隊伍中,第一個隊伍會與第二個隊伍競賽,第三個隊伍會與第四個隊伍競賽,以此類推(順序為List順序)。

N個回合過後,隊伍的Rank會以競賽紀錄的最大字典序來排序,字典序越大Rank越小。例如:[W, W, W] > [W, W, L] > [W, L, W] > ... > [L, L, L]。

以下給一範例,當競賽名單為[2, 4, 5, 3, 6, 7, 1, 0],則每個回合與競賽紀錄如下:



如果此時P=4,則隊伍0,2,3,6皆會獲得獎品。

這個例子顯示了隊伍1並不一定會獲得獎品,而隊伍0無論如何都會拿到獎品。
Input:
第一行是數字T,表示接下來有T筆測試資料。

每筆測試資料給定兩個數字N P,表示有2N個隊伍,以及獎品數有P個。

限制:
1 ≤ T ≤ 100.
1 ≤ P ≤ 2N
1 ≤ N ≤ 50

保證50%的分數1 ≤ N ≤ 10。
Output:
對於每筆測試資料輸出兩個以空白隔開的數字x y,其中x表示一定會獲得獎品的最大編號的隊伍編號,y表示可能獲得獎品的最大編號的隊伍編號。
Sample Input:
3
3 4
3 5
3 3
Sample Output:
0 6
2 6
0 4
Source:
Google Code Jam 2013 2
Problem Setter
Nekosyndrome
Testdata:
TestTimeMemoryScore
0150ms65536kb
1150ms65536kb1
2150ms65536kb1
3150ms65536kb1
4150ms65536kb1
5150ms65536kb1
6150ms65536kb1
7150ms65536kb1
8150ms65536kb1
9150ms65536kb1
10150ms65536kb1
11150ms65536kb1
12150ms65536kb1
13150ms65536kb1
14150ms65536kb1
15150ms65536kb1
16150ms65536kb1
17150ms65536kb1
18150ms65536kb1
19150ms65536kb1
20150ms65536kb1
21150ms65536kb1
22150ms65536kb1
23150ms65536kb1
24150ms65536kb1
25150ms65536kb1
26150ms65536kb1
27150ms65536kb1
28150ms65536kb1
29150ms65536kb1
30150ms65536kb1
31150ms65536kb1
32150ms65536kb1
33150ms65536kb1
34150ms65536kb1
35150ms65536kb1
36150ms65536kb1
37150ms65536kb1
38150ms65536kb1
39150ms65536kb1
40150ms65536kb1
41150ms65536kb1
42150ms65536kb1
43150ms65536kb1
44150ms65536kb1
45150ms65536kb1
46150ms65536kb1
47150ms65536kb1
48150ms65536kb1
49150ms65536kb1
50150ms65536kb1
511000ms65536kb50

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原