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)
0 2000 262144
1 2000 262144
2 2000 262144
3 2000 262144
4 2000 262144
5 2000 262144
6 2000 262144
7 2000 262144
8 2000 262144
9 2000 262144
10 2000 262144
11 2000 262144
12 2000 262144
13 2000 262144
14 2000 262144
15 2000 262144
16 2000 262144