一開始有ㄧ數列$A_1$，對於數列$A_1$中，長度為$N$，$A_{1,j}$的值為$j(1\le j \le N)$
假設數列$A_i$有$K$項，你需要對其重複且依序的執行以下操作:
1.將$A_i$反轉，即對於$1 \le j \le \frac{K}{2}$，$A_{i,j}$與$A_{i,K-j+1}$交換
2.將$A_i$切分成一半，產生兩新數列$A_{i*2}$為$\{A_{i,1},A_{i,2}\ ...\ A_{i,\frac{K}{2}}\}$，$A_{i*2+1}$為$\{A_{i,\frac{K}{2}+1},A_{i,\frac{K}{2}+2}\ ...\ A_{i,K}\}$
若$A_{N},A_{N+1}\ ...\ A_{2*N-1}$皆只有一項數字，上述操作將停止
最後，令一數列$B$，數列內數字為$\{A_{N,1},A_{N+1,1}\ ...\ A_{2*N-1,1}\}$
第一行有兩數$T,N$，分別代表詢問次數與$A_1$長度
之後$T$行，每行有一數$x$，代表詢問的數字
對於每筆詢問輸出數字$x$位於數列$B$中的第幾項後換行
8 8 1 2 3 4 5 6 7 8
6 5 8 7 2 1 4 3
範例測資解釋:
$A_1$為$\{1,2,3,4,5,6,7,8\}$
反轉後為$\{8,7,6,5,4,3,2,1\}$
之後使$A_2$為$\{8,7,6,5\}$，$A_3$為$\{4,3,2,1\}$
將$A_2$與$A_3$反轉，$A_2$為$\{5,6,7,8\}$，$A_3$為$\{1,2,3,4\}$
使$A_4$為$\{5,6\}$，$A_5$為$\{7,8\}$，使$A_6$為$\{1,2\}$，$A_7$為$\{3,4\}$
反轉後$A_4$為$\{6,5\}$，$A_5$為$\{8,7\}$，使$A_6$為$\{2,1\}$，$A_7$為$\{4,3\}$
使$A_8$為$\{6\}$，$A_9$為$\{5\}$，$A_{10}$為$\{8\}$，$A_{11}$為$\{7\}$，$A_{12}$為$\{2\}$，$A_{13}$為$\{1\}$，$A_{14}$為$\{4\}$，$A_{15}$為$\{3\}$
反轉後$A_8$為$\{6\}$，$A_9$為$\{5\}$，$A_{10}$為$\{8\}$，$A_{11}$為$\{7\}$，$A_{12}$為$\{2\}$，$A_{13}$為$\{1\}$，$A_{14}$為$\{4\}$，$A_{15}$為$\{3\}$
操作結束，$B$為$\{6,5,8,7,2,1,4,3\}$
測資限制
$30\%$
$1 \le T \le 100$
$1 \le N \le 2^7$
$1 \le x \le N$
$70\%$
$1 \le T \le 1000$
$1 \le N \le 2^{10}$
$1 \le x \le N$
$100\%$
$1 \le T \le 2*10^5$
$1 \le N \le 2^{60}$
$1 \le x \le N$
保證$N$為$2$的冪次
保證所有輸入數字皆為正整數
5/6 18:32 題序修改
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||