TopCoder

User's AC Ratio

71.4% (5/7)

Submission's AC Ratio

43.5% (30/69)

Tags

Description

在合體之後,妁艷和楓音的戰鬥力以乘階的數量級上升。

「我渾身感到力量!」妁艷大聲的呼喊著。

「妁艷君你弄痛我了!」楓音叫道,畢竟,兩人現在是合體狀態。

「不管你們用了什麼奇怪的招式,你們都不可能逃走,更不可能前進。」無視兩人的對話,冷漠的敵人說道。

敵人手一揮,一道白光把妁艷和楓音包住,似乎是把他們傳送到了另一個空間,是一個只有黑白相間無限延伸的空間。

「來到這裡,你們只有唯一的辦法可以出去,就是臣服於我。」說完敵人就拿起每秒可以發射20發岩石的武器★Rock Cannon,準備向他們發動攻擊。

數百顆岩石同時向妁艷及楓音襲來,雖然戰鬥力上升了,可是岩石數量太多,他們連閃避都來不及。

「只要能給她一擊就好了,一擊我就能擊敗她了。」妁艷心想。

「小心!妁艷君!」楓音警告,可是為時已晚,一群岩石就要打中他們了。

「咦?沒事。」兩人被擊中竟然沒事,原來有些偽岩石參雜在那群岩石裡。

「呿!被你們發現了,不過如果被真的岩石打中,可不會傷得這麼輕了。」敵人持續射擊著。

楓音發現每個岩石都是一顆滿枝二元石,也就是如果岩石高度是H,它必須有2H+1-1個子節點,而且它們的連結方式都是把節點編號由小到大排序後,由上而下、由左到右填入。

妁艷發現真岩石都是由一個巨大二元石所分裂而來的二元岩石,巨大二元石的根編號是1,每個編號k的節點都有一個編號2k和一個編號2k+1的子節點。如圖:

兩人打算只躲開真岩石,這樣他們才有空檔可以接近敵人,可是他們不知要如何快速分辨真岩石和偽岩石,他們能擊敗敵人嗎?

Input Format

第一行有一個數字t,代表有幾顆岩石飛過來。
每顆岩石有兩行輸入
第一行有一個數字H,代表這顆岩石的高度。
第二行有2H+1-1個數字代表這顆岩石所有子節點編號。
t<=20
0<=H<20
1<=所有編號<18446744073709551616
保證每顆岩石內的子節點編號不會重複

Output Format

如果是真岩石輸出"dodge"(不含雙引號)
否則輸出"do not dodge"(不含雙引號)
並換行

Sample Input

2
2
2 5 4 10 8 11 9
2
2 5 4 10 8 12 9

Sample Output

dodge
do not dodge

Hints

第一筆範例測資
是由巨大二元石分裂而來

第二筆範例測資
在巨大二元石上找不到

另外:
1.如果以O(nlogn)的複雜度AC此題,妁艷可能會被敵人以絕招"加強測資rejudge"攻擊
2.因為輸入資料有點多,妁艷開啟GN做為常駐技能

Problem Source

原TIOJ1769 / 靈感來自單系群
problem setter:fenzhang

Subtasks

For Testdata: 0 ~ 0, Score: 16
For Testdata: 1 ~ 1, Score: 16
For Testdata: 2 ~ 2, Score: 16
For Testdata: 3 ~ 3, Score: 16
For Testdata: 4 ~ 4, Score: 16
For Testdata: 5 ~ 5, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3500 65536 262144
1 3500 65536 262144
2 3500 65536 262144
3 3500 65536 262144
4 3500 65536 262144
5 3500 65536 262144