TopCoder

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

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (2/2)

Description

在古老的年代,電腦是以一個一個的記憶單元組成的,指令也不多。現在我們要來模擬這種電腦把兩個2位數相乘的計算過程。

我們假設這個電腦使用$B$進制,以$M$個記憶單元組成,編號為$0$到$M-1$,每個記憶單元可以儲存一個$0$到$B-1$的整數。以下以$P_i$代表第$i$個記憶單元儲存的值。
在程式執行開始之前,電腦會被植入一或兩個函數$f_0(,f_1)$。每個函數$f$接收兩個$0$到$B-1$的整數,輸出一個$0$到$B-1$的整數。這些函數是自訂的,不須符合交換律或結合律,但不能在執行過程中改變。
另外,$P_0$到$P_{B-1}$會依序被初始為$0$到$B-1$;要相乘的兩個2位數數字則會初始化在$P_B$到$P_{B+3}$:第一個數字$X=P_BB+P_{B+1}$、第二個數字$Y=P_{B+2}B+P_{B+3}$。$P_{B+4}$到$P_{M-1}$則全部初始化為0。
下圖舉例$B=3$的情況,當$X=4,Y=6$(三進位表示分別是11和20),記憶單元被初始化的情形如下圖:

這種電腦的指令只有一種:$(a,b,c,d)$,代表將$P_c$的值改變為$f_d(P_a,P_b)$。$a,b,c$可以是任何$0$到$M-1$的整數(可以重覆);如果只有一個函數,那麼$d$將被省略,也就是指令格式為$(a,b,c)$。執行的時候,將會依序執行每一個指令。

現在,你要透過設定電腦的函數$f_i$,以及至多$S$條指令,來實現2位數的乘法。具體來說,對於所有$0\leq X,Y < B^ 2$,在執行完所有的指令之後,必須滿足$P_{B+4}B^ 3+P_{B+5}B^ 2+P_{B+6}B+P_{B+7}=X\times Y$。除了這四個記憶單元以外,其他記憶單元的值都不影響結果的正確與否。
同樣以$B=3,X=4,Y=6$舉例,下圖為其中一種正確的執行結果(24的三進位表示是220):

給定$B$,請寫一個程式輸出正確的函數與指令。

Input Format

本題輸入只有一行,包含一個正整數$B$,代表你要實作$B$進制的乘法自動機。

本題有許多子任務。保證存在單一方法可以完成所有子任務。
以下以$C$代表能使用的函數數量上限。

子任務
(測資)
額外限制 分數
1 (0) $B=3, M=10^ 5, S=10^ 5, C=1$
$X,Y$在三進位下位數只包含0或1
10
2 (1) $B=5, M=10^ 5, S=10^ 5, C=1$
$X,Y< 5$
10
3 (2) $B=3, M=3000, S=3000, C=2$ 10
4 (3) $B=7, M=3000, S=10^ 5, C=2$ 5
5 (4) $B=3, M=10^ 5, S=10^ 5, C=1$ 5
6 (5) $B=5, M=10^ 5, S=10^ 5, C=1$ 5
7 (6) $B=7, M=10^ 5, S=10^ 5, C=1$ 5
8 (7) $B=4, M=10^ 5, S=10^ 5, C=1$ 5
9 (8) $B=6, M=10^ 5, S=10^ 5, C=1$ 5
10 (9) $B=3, M=25, S=2500, C=1$ 5
11 (10) $B=5, M=25, S=2\times 10^ 4, C=1$ 5
12 (11) $B=7, M=25, S=10^ 5, C=1$ 5
13 (12) $B=4, M=25, S=10^ 4, C=1$ 5
14 (13) $B=6, M=25, S=5\times 10^ 4, C=1$ 5
15 (14) $B=8, M=25, S=4\times 10^ 5, C=1$ 5
16 (15) $B=9, M=25, S=4\times 10^ 5, C=1$ 5
17 (16) $B=10, M=25, S=4\times 10^ 5, C=1$ 5

Output Format

第一行請輸出一個正整數$Q\leq 2$,代表你的自動機需要的函數數量。

接下來$Q\times B$行,每行輸出$B$個整數。每$B$行代表一個函數$f_a$,第$i$行第$j$個數字($0\leq i,j<B$)代表$f_a(i,j)$的值。

接下來一行輸出一個數字$K$,代表指令數量。
接下來$K$行,如果$Q=1$,每行輸出三個非負整數$a,b,c$,代表指令為$(a,b,c)$;如果$Q=2$,每行輸出四個非負整數$a,b,c,d$,代表指令為$(a,b,c,d)$。

如果你輸出的格式不對,或值域不符合題目、子任務之限制,你會獲得一個WA。

Sample Input

3

Sample Output

#以下兩個範例輸出是合法的輸出格式,但並非正確解。
#Sample Output 1
1
0 2 1
1 2 2
2 1 1
4
1 2 7
7 7 7
2 8 8
8 7 5
#Sample Output 2
2
0 2 1
1 2 2
2 1 0
1 2 0
2 1 0
1 1 2
3
1 2 4 0
5 5 5 1
4 2 4 1

Hints

以Sample Output 1為例,假設$X=4,Y=6$(三進位的11和20),那麼記憶單元的資訊將會以如下的方式變動:

執行結束後儲存答案的記憶單元(編號7~10)的內容是1200(也就是十進位的45),但是由於$4\times 6\neq 45$,本輸出會得到一個WA。

Problem Source

改編自CodeChef Challange 2017/07
Problem Set / Judge by Yihda Yol

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 5
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 262144 65536
1 2000 262144 65536
2 2000 262144 65536
3 2000 262144 65536
4 2000 262144 65536
5 2000 262144 65536
6 2000 262144 65536
7 2000 262144 65536
8 2000 262144 65536
9 2000 262144 65536
10 2000 262144 65536
11 2000 262144 65536
12 2000 262144 65536
13 2000 262144 65536
14 2000 262144 65536
15 2000 262144 65536
16 2000 262144 65536