TopCoder

User's AC Ratio

88.9% (16/18)

Submission's AC Ratio

40.2% (51/127)

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 1

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

Sample Output 1

dodge
do not dodge

Hints

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

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

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

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3500 65536 262144 1
1 3500 65536 262144 2
2 3500 65536 262144 3
3 3500 65536 262144 4
4 3500 65536 262144 5
5 3500 65536 262144 6