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

HSNU Online Judge

• Index
• User
• Problem
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 278 - Many Prizes

Problem Statistics

Solved Member: 16　　Submission: 40　　User Tried: 16

Problem：

瀚瀚國準備辦一個有2^N個隊伍的競賽，並準備了P份獎品要給Rank 0..P-1的隊伍。

這些隊伍由0至2^N-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，表示有2^N個隊伍，以及獎品數有P個。

限制：
1 ≤ T ≤ 100.
1 ≤ P ≤ 2^N
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：

Test	Time	Memory	Score
0	150ms	65536kb
1	150ms	65536kb	1
2	150ms	65536kb	1
3	150ms	65536kb	1
4	150ms	65536kb	1
5	150ms	65536kb	1
6	150ms	65536kb	1
7	150ms	65536kb	1
8	150ms	65536kb	1
9	150ms	65536kb	1
10	150ms	65536kb	1
11	150ms	65536kb	1
12	150ms	65536kb	1
13	150ms	65536kb	1
14	150ms	65536kb	1
15	150ms	65536kb	1
16	150ms	65536kb	1
17	150ms	65536kb	1
18	150ms	65536kb	1
19	150ms	65536kb	1
20	150ms	65536kb	1
21	150ms	65536kb	1
22	150ms	65536kb	1
23	150ms	65536kb	1
24	150ms	65536kb	1
25	150ms	65536kb	1
26	150ms	65536kb	1
27	150ms	65536kb	1
28	150ms	65536kb	1
29	150ms	65536kb	1
30	150ms	65536kb	1
31	150ms	65536kb	1
32	150ms	65536kb	1
33	150ms	65536kb	1
34	150ms	65536kb	1
35	150ms	65536kb	1
36	150ms	65536kb	1
37	150ms	65536kb	1
38	150ms	65536kb	1
39	150ms	65536kb	1
40	150ms	65536kb	1
41	150ms	65536kb	1
42	150ms	65536kb	1
43	150ms	65536kb	1
44	150ms	65536kb	1
45	150ms	65536kb	1
46	150ms	65536kb	1
47	150ms	65536kb	1
48	150ms	65536kb	1
49	150ms	65536kb	1
50	150ms	65536kb	1
51	1000ms	65536kb	50

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2808 秒，使用記憶體: 2.87MB 。