TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (5/5)

Tags

Description

Petya 是一個很喜歡計算機的人。他平時喜歡買各種不同功能的計算機,順便研究各類計算機的功能。

有一天,Petya 買到了一種特殊的計算機。這種計算機是主要提供寫程式的人使用,因此除了支援平常常見的四則運算之外,還可以做 AND、OR、NOT、XOR、位元左右移等常見的位元運算。另外一個特殊的功能是這款計算機有簡易的儲存和巨集(macro)功能:使用者如果需要做大量重複的計算,可以把常用的運算流程事先儲存成一個巨集,這樣之後在輸入資料之後,只需要按一個鍵,計算機就能執行事先儲存好的運算流程並馬上給出結果。

具體來說,這個計算機有 8 個記憶區(編號為 0 到 7),每個記憶區可以儲存一個介於 $0$ 到 $2^ {32}-1$ 的整數。而一個巨集由 $N$ 個步驟組成,每個步驟都必須是把一個或兩個記憶區的整數取出來做其中一種四則或位元運算,然後把結果放到其中一個記憶區中(並覆蓋掉原本的數字)。使用者一開始可以在記憶區中存入任意的數字,當按下「執行巨集」鍵之後,計算機會依序執行巨集中的 $N$ 個步驟,而執行完後之後使用者就可以查看記憶區中的數字來得出最終的計算結果。

Petya 非常喜歡玩這個計算機的巨集功能。他尤其喜歡先儲存一個巨集,然後不斷的重複按「執行巨集」鍵,看記憶區的數字是如何快速變化的。然而他發現一次又一次地按「執行巨集」鍵實在是太累了,而且還很傷手。因此,Petya 找到了你,希望你可以幫他寫一個模擬這種計算機的程式,讓他可以知道在連續按了 $T$ 次「執行巨集」鍵之後記憶區裡的數字會是多少。

另外,Petya 會給你一部份他寫的巨集供你參考,這些巨集也會出現在測資當中。不過 Petya 不希望你的程式只能套用在他目前寫出來的巨集,因此多數測資中的巨集 Petya 不會讓你知道。然而,這些沒有讓你知道的巨集中,有些可能會與 Petya 給你的巨集有一些相似的特性,所以你如果針對 Petya 給你的巨集中的一些特性做優化的話,很可能可以得到更多的分數。

Input Format

本題沒有輸入,如果你輸入了任何東西,可能會導致各種不可預期的結果。

#include "lib2295.h"之後實作下列兩個函數。

void init_macro(int N, const uint32_t op[][5]);:評測程式在執行的一開始會先呼叫這個函數,代表 Petya 儲存的巨集的內容。在一次執行當中,這個函數只會被呼叫一次,且保證 op 陣列在之後每次呼叫 run_macro 時仍然可以存取。
傳入的參數中,N 即是巨集的步驟數量,而 op 則是一個 $N\times 5$ 的二維陣列,代表巨集的內容。陣列的每一列即是一個步驟,包含五個非負整數 $X,p,d,a,b$。不同的 $X$ 代表不同的運算,意義如下表所示。下表中,$M_i := V$ 代表把 $V$ 這個數字存進第 $i$ 個記憶區中,而在 $:=$ 右手邊的式子中出現的 $M_j$ 即代表第 $j$ 個記憶區在該步驟開始前的值;所有的 $B=\begin{cases}M_b, & \text{if }p=0 \\ b, & \text{if }p=1\end{cases}$;$a\bmod b$ 代表 $a$ 除以 $b$ 的餘數(介於 $0$ 到 $b-1$ 間)。

$X=0$:$M_d:=(M_a+B)\bmod 2^ {32}$
$X=1$:$M_d:=(M_a-B)\bmod 2^ {32}$
$X=2$:$M_d:=(M_a\times B)\bmod 2^ {32}$
$X=3$:$M_d:=\begin{cases}\lfloor M_a/B\rfloor, & \text{if }B\neq 0 \\ 0, & \text{if }B=0\end{cases}$
$X=4$:$M_d:=\begin{cases}M_a\bmod B, & \text{if }B\neq 0 \\ 0, & \text{if }B=0\end{cases}$
$X=5$:$M_d:=M_a \text{ AND } B$
$X=6$:$M_d:=M_a \text{ OR } B$
$X=7$:$M_d:=M_a \text{ XOR } B$
$X=8$:$M_d:=M_a \text{ SHR } (B\bmod 32)$(SHR 為位元右移,相當於 C/C++ 的 >>
$X=9$:$M_d:=M_a \text{ SHL } (B\bmod 32)$(SHL 為位元左移,相當於 C/C++ 的 <<
$X=10$:$M_d:=\text{NOT } B$(保證 $a=0$;NOT 為位元取反,相當於 C/C++ 的 ~

輸入必定滿足:

  • $1\leq N\leq 80$
  • $0\leq X\leq 10$
  • $p\in\{0,1\}$
  • $0\leq a,d<8$
  • 若 $p=0$,則 $0\leq b<8$,否則 $0\leq b<2^ {32}$。

void run_macro(int T, uint32_t memory[8]);:這個函數代表 Petya 想執行巨集。傳入的參數中,T 代表 Petya 希望巨集連續執行的次數,memory 則是 8 個記憶區在一開始儲存的數字。這個函數必須將 Petya 儲存的巨集執行 $T$ 次之後記憶區的值重新寫回 memory 陣列中。

對於所有測資:

  • 一次執行中呼叫 run_macro 的次數不超過 $100$
  • 所有呼叫 run_macro 的 $T$ 加總不超過 $\frac{10^ 9}{N}$。

對於 100 分的測資,所有呼叫的 run_macro 的 $T$ 加總不超過 $\frac{10^ 8}{N}$。

Output Format

本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA

Petya 提供給你的巨集可以在這裡下載,對應的測資各筆測資的敘述。每個檔案中第一行是 $N$,接下來 $N$ 行每行有 5 個空白隔開的數字,即是 op 陣列的內容。這個巨集的格式是為了方便測試標頭檔使用,如果想要更容易閱讀的話,可以使用這個 Python script 將巨集轉換成易懂的格式。請注意這個 script 雖然是以 C/C++ 的運算子符號輸出,但實際的操作須以題目敘述為準,因此可能與 C/C++ 中對應的操作不同(例如一行 3 1 0 1 0 的操作會輸出成 m0 := m1 / 0)。

對於所有測資,若你的程式執行時間為時限的 $x$ 倍($0\leq x\leq 1$),該筆測資的分數為 $A\times (p+qf(x))$,其中 $A$ 為該筆測資標示的分數、$p,q$ 為各測資敘述上標示的常數,並給定常數 $a=1,b=0.15$,

\[f(x)=\left(s(x) \frac{(b x)^ a - b^ a}{(b x)^ a - 1.1x^ a}+\big(1-s(x)\big)\left(1-\frac{x^ 2}{2}\right)\right)\]

\[s(x)=\begin{cases}x, & x\in\{0,1\} \\ \frac{1}{1+\exp\left(\frac{8a}{b}\cot\left(\pi x^ {-\frac{\ln2}{0.1+\ln b}}\right)\right)}, & \text{otherwise}\end{cases}\]

你只需要知道 $f(0)=1,f(1)=0$,且 $f(x)$ 嚴格遞減就可以了。不過如果想要詳細了解這些函數在幹嘛的話,可以參考這個連結

Sample Input 1

注意:本題沒有輸入,本輸入為提供測試標頭檔(參見Hints)使用。
3
0 1 0 1 1
1 1 1 2 1
2 1 2 2 3
2
5 1 2 3 4 5 6 7 8
2 1 2 2 1 1 1 1 1

Sample Output 1

注意:本題沒有輸出,本輸入為提供測試標頭檔(參見Hints)使用。
81 242 729 4 5 6 7 8
2 5 18 1 1 1 1 1

Hints

這裡有一個測試用的標頭檔,可以用來測試。
該標頭檔接受以下輸入,數字間皆以空白分隔:
第一行:$N$
接下來 $N$ 行:$X,p,d,a,b$
(此格式與 Petya 給的巨集格式相同。)
下一行有一個數字 $Q$,代表呼叫 run_macro 的總次數。
接下來 $Q$ 行,每行包含 9 個數字 $T$,memory[0],memory[1], $\cdots$ ,memory[7],意義如題目所示。

程式會對每次呼叫 run_macro 輸出一行包含八個數字,代表執行完 run_macromemory 陣列的內容。

Problem Source

TIOJ 終極壓常數大賽 pD

Subtasks

No. Testdata Range Constraints Score
1 0 $p=1,q=0.2$ 50
2 1 $p=1,q=0.2$ 50
3 2 macro_01.txt; $p=0,q=1$ 8
4 3 macro_02.txt; $p=0,q=1$ 8
5 4 macro_03.txt; $p=0,q=1$ 8
6 5 macro_04.txt; $p=0,q=1$ 8
7 6 macro_05.txt; $p=0,q=1$ 5
8 7 macro_06.txt; $p=0,q=1$ 5
9 8 macro_07.txt; $p=0,q=1$ 5
10 9 $p=0,q=1$ 40
11 10 $p=0,q=1$ 20
12 11 $p=0,q=1$ 40
13 12 $p=0,q=1$ 15
14 13 $p=0,q=1$ 15
15 14 $p=0,q=1$ 20
16 15 $p=0,q=1$ 20
17 16 $p=0,q=1$ 25
18 17 $p=0,q=1$ 12
19 18 $p=0,q=1$ 12
20 19 $p=0,q=1$ 20
21 20 $p=0,q=1$ 25
22 21 $p=0,q=1$ 80
23 22 $p=0,q=1$ 50
24 23 $p=0,q=1$ 80
25 24 $p=0,q=1$ 50
26 25 $p=0,q=1$ 40
27 26 $p=0,q=1$ 10
28 27 $p=0,q=1$ 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 2048 64 1
1 1000 2048 64 2
2 1000 2048 64 3
3 1000 2048 64 4
4 1000 2048 64 5
5 1000 2048 64 6
6 1000 2048 64 7
7 1000 2048 64 8
8 1000 2048 64 9
9 1000 2048 64 10
10 1000 2048 64 11
11 1000 2048 64 12
12 1000 2048 64 13
13 1000 2048 64 14
14 1000 2048 64 15
15 1000 2048 64 16
16 1000 2048 64 17
17 1000 2048 64 18
18 1000 2048 64 19
19 1000 2048 64 20
20 1000 2048 64 21
21 1000 2048 64 22
22 1000 2048 64 23
23 1000 2048 64 24
24 1000 2048 64 25
25 1000 2048 64 26
26 1000 2048 64 27
27 1000 2048 64 28