Christopher là một kỹ sư đang làm việc trên một loại bộ vi xử lý mới.

Bộ vi xử lý có thể truy cập \(m\) ô nhớ khác nhau, mỗi ô gồm \(b\) bit (với \(m=100\) và \(b=2000\)). Các ô nhớ này được gọi là thanh ghi, được đánh số từ \(0\) đến \(m-1\) và ký hiệu là \(r[0],r[1],\ldots,r[m-1]\). Mỗi thanh ghi là một mảng \(b\) bit, được đánh số từ \(0\) (bit ngoài cùng bên phải) đến \(b-1\) (bit ngoài cùng bên trái). Với mỗi \(i\) (\(0\le i\le m-1\)) và mỗi \(j\) (\(0\le j\le b-1\)), ký hiệu bit thứ \(j\) của thanh ghi \(i\) là \(r[i][j]\).

Với một dãy bit \(d_0,d_1,\ldots,d_{\ell-1}\) có độ dài \(\ell\) bất kỳ, giá trị số nguyên của dãy bằng:

Giá trị số nguyên được lưu trong thanh ghi \(i\) là giá trị số nguyên của dãy bit của thanh ghi đó, tức là:

Bộ vi xử lý có \(9\) loại lệnh dùng để thay đổi các bit trong các thanh ghi. Mỗi lệnh thao tác trên một hoặc nhiều thanh ghi và lưu kết quả vào một thanh ghi. Sau đây, ký hiệu \(x:=y\) chỉ thao tác thay đổi giá trị của \(x\) thành \(y\). Các loại lệnh được mô tả như sau:

• move(t, y): sao chép mảng bit trong thanh ghi \(y\) sang thanh ghi \(t\). Với mỗi \(j\) (\(0\le j\le b-1\)), gán \(r[t][j]:=r[y][j]\).
• store(t, v): đặt thanh ghi \(t\) bằng \(v\), trong đó \(v\) là một mảng \(b\) bit. Với mỗi \(j\) (\(0\le j\le b-1\)), gán \(r[t][j]:=v[j]\).
• and(t, x, y): thực hiện phép AND theo từng bit giữa thanh ghi \(x\) và thanh ghi \(y\), rồi lưu kết quả vào thanh ghi \(t\). Với mỗi \(j\) (\(0\le j\le b-1\)), gán \(r[t][j]:=1\) nếu cả \(r[x][j]\) và \(r[y][j]\) đều bằng \(1\); ngược lại, gán \(r[t][j]:=0\).
• or(t, x, y): thực hiện phép OR theo từng bit giữa thanh ghi \(x\) và thanh ghi \(y\), rồi lưu kết quả vào thanh ghi \(t\). Với mỗi \(j\) (\(0\le j\le b-1\)), gán \(r[t][j]:=1\) nếu ít nhất một trong hai bit \(r[x][j]\) và \(r[y][j]\) bằng \(1\); ngược lại, gán \(r[t][j]:=0\).
• xor(t, x, y): thực hiện phép XOR theo từng bit giữa thanh ghi \(x\) và thanh ghi \(y\), rồi lưu kết quả vào thanh ghi \(t\). Với mỗi \(j\) (\(0\le j\le b-1\)), gán \(r[t][j]:=1\) nếu đúng một trong hai bit \(r[x][j]\) và \(r[y][j]\) bằng \(1\); ngược lại, gán \(r[t][j]:=0\).
• not(t, x): thực hiện phép NOT theo từng bit của thanh ghi \(x\), rồi lưu kết quả vào thanh ghi \(t\). Với mỗi \(j\) (\(0\le j\le b-1\)), gán \(r[t][j]:=1-r[x][j]\).
• left(t, x, p): dịch tất cả các bit của thanh ghi \(x\) sang trái \(p\) vị trí và lưu kết quả vào thanh ghi \(t\). Kết quả dịch là một mảng \(v\) gồm \(b\) bit. Với mỗi \(j\) (\(0\le j\le b-1\)), \(v[j]=r[x][j-p]\) nếu \(j\ge p\), và \(v[j]=0\) trong trường hợp còn lại. Với mỗi \(j\) (\(0\le j\le b-1\)), gán \(r[t][j]:=v[j]\).
• right(t, x, p): dịch tất cả các bit của thanh ghi \(x\) sang phải \(p\) vị trí và lưu kết quả vào thanh ghi \(t\). Kết quả dịch là một mảng \(v\) gồm \(b\) bit. Với mỗi \(j\) (\(0\le j\le b-1\)), \(v[j]=r[x][j+p]\) nếu \(j\le b-1-p\), và \(v[j]=0\) trong trường hợp còn lại. Với mỗi \(j\) (\(0\le j\le b-1\)), gán \(r[t][j]:=v[j]\).
• add(t, x, y): cộng giá trị số nguyên trong thanh ghi \(x\) và thanh ghi \(y\), rồi lưu kết quả vào thanh ghi \(t\). Phép cộng được thực hiện theo modulo \(2^b\). Cụ thể, gọi \(X\) và \(Y\) lần lượt là các giá trị số nguyên trong thanh ghi \(x\) và thanh ghi \(y\) trước thao tác, và \(T\) là giá trị số nguyên trong thanh ghi \(t\) sau thao tác. Nếu \(X+Y<2^b\), đặt các bit của \(t\) sao cho \(T=X+Y\). Ngược lại, đặt các bit của \(t\) sao cho \(T=X+Y-2^b\).

Christopher muốn bạn giải hai loại bài toán bằng bộ vi xử lý mới. Loại bài toán được biểu thị bằng số nguyên \(s\). Với cả hai loại, bạn cần tạo một chương trình, tức là một dãy các lệnh được định nghĩa ở trên.

Dữ liệu đầu vào của chương trình gồm \(n\) số nguyên \(a[0],a[1],\ldots,a[n-1]\), mỗi số có \(k\) bit, tức là \(a[i]<2^k\) (\(0\le i\le n-1\)). Trước khi chương trình được thực thi, tất cả các số đầu vào được lưu liên tiếp trong thanh ghi \(0\), sao cho với mỗi \(i\) (\(0\le i\le n-1\)), giá trị số nguyên của dãy \(k\) bit \(r[0][i\cdot k],r[0][i\cdot k+1],\ldots,r[0][(i+1)\cdot k-1]\) bằng \(a[i]\). Lưu ý rằng \(n\cdot k\le b\). Tất cả các bit còn lại trong thanh ghi \(0\) (có chỉ số từ \(n\cdot k\) đến \(b-1\), bao gồm cả hai đầu mút) và tất cả các bit trong các thanh ghi khác đều được khởi tạo bằng \(0\).

Chạy một chương trình nghĩa là thực thi các lệnh của nó theo thứ tự. Sau khi thực thi lệnh cuối cùng, đầu ra của chương trình được tính từ giá trị cuối cùng của các bit trong thanh ghi \(0\). Cụ thể, đầu ra là một dãy \(n\) số nguyên \(c[0],c[1],\ldots,c[n-1]\), trong đó với mỗi \(i\) (\(0\le i\le n-1\)), \(c[i]\) là giá trị số nguyên của dãy bit từ vị trí \(i\cdot k\) đến \((i+1)\cdot k-1\) trong thanh ghi \(0\). Sau khi chạy chương trình, các bit còn lại của thanh ghi \(0\) (có chỉ số ít nhất là \(n\cdot k\)) và tất cả các bit trong các thanh ghi khác có thể có giá trị bất kỳ.

• Loại bài toán thứ nhất (\(s=0\)) là tìm số nguyên nhỏ nhất trong các số đầu vào \(a[0],a[1],\ldots,a[n-1]\). Cụ thể, \(c[0]\) phải bằng giá trị nhỏ nhất của \(a[0],a[1],\ldots,a[n-1]\). Các giá trị \(c[1],c[2],\ldots,c[n-1]\) có thể tùy ý.
• Loại bài toán thứ hai (\(s=1\)) là sắp xếp các số nguyên đầu vào \(a[0],a[1],\ldots,a[n-1]\) theo thứ tự không giảm. Cụ thể, với mỗi \(i\) (\(0\le i\le n-1\)), \(c[i]\) phải bằng số nguyên nhỏ thứ \(1+i\) trong \(a[0],a[1],\ldots,a[n-1]\) (tức là \(c[0]\) là số nguyên nhỏ nhất trong các số đầu vào).

Hãy cung cấp cho Christopher các chương trình giải được những bài toán này, mỗi chương trình gồm không quá \(q\) lệnh.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

void construct_instructions(int s, int n, int k, int q);

• s: loại bài toán.
• n: số lượng số nguyên đầu vào.
• k: số bit của mỗi số nguyên đầu vào.
• q: số lệnh tối đa được phép sử dụng.
• Hàm được gọi đúng một lần và cần xây dựng một dãy lệnh thực hiện yêu cầu của bài toán.

Hàm này cần gọi một hoặc nhiều hàm dưới đây để xây dựng dãy lệnh:

void append_move(int t, int x);
void append_store(int t, std::vector<bool> v);
void append_and(int t, int x, int y);
void append_or(int t, int x, int y);
void append_xor(int t, int x, int y);
void append_not(int t, int x);
void append_left(int t, int x, int s);
void append_right(int t, int x, int s);
void append_add(int t, int x, int y);

• Các hàm lần lượt thêm lệnh move(t, y), store(t, v), and(t, x, y), or(t, x, y), xor(t, x, y), not(t, x), left(t, x, p), right(t, x, p) hoặc add(t, x, y) tương ứng vào cuối chương trình.
• Với mọi lệnh có các tham số tương ứng, \(t,x,y\) phải nằm trong đoạn từ \(0\) đến \(m-1\).
• Các chỉ số \(t,x,y\) không nhất thiết phải đôi một khác nhau.
• Với các lệnh left và right, \(p\) phải nằm trong đoạn từ \(0\) đến \(b\), bao gồm cả hai đầu mút.
• Với lệnh store, độ dài của \(v\) phải bằng \(b\).

Bạn cũng có thể gọi hàm sau để hỗ trợ kiểm thử lời giải:

void append_print(int t);

• Mọi lời gọi hàm này đều bị bỏ qua khi chấm bài.
• Trong trình chấm mẫu, hàm thêm một thao tác print(t) vào cuối chương trình.
• Khi gặp thao tác print(t) trong quá trình thực thi chương trình, trình chấm mẫu in \(n\) số nguyên \(k\) bit được tạo bởi \(n\cdot k\) bit đầu tiên của thanh ghi \(t\) (xem định dạng ở phần Dữ liệu ra).
• \(t\) phải thỏa mãn \(0\le t\le m-1\).
• Lời gọi hàm này không làm tăng số lệnh đã xây dựng.

Sau khi thêm lệnh cuối cùng, hàm construct_instructions cần kết thúc. Chương trình sau đó được đánh giá trên một số bộ dữ liệu, mỗi bộ gồm \(n\) số nguyên \(k\) bit \(a[0],a[1],\ldots,a[n-1]\). Lời giải vượt qua một bộ dữ liệu nếu đầu ra \(c[0],c[1],\ldots,c[n-1]\) của chương trình trên đầu vào đó thỏa mãn:

• Nếu \(s=0\), \(c[0]\) phải là giá trị nhỏ nhất trong \(a[0],a[1],\ldots,a[n-1]\).
• Nếu \(s=1\), với mỗi \(i\) (\(0\le i\le n-1\)), \(c[i]\) phải bằng số nguyên nhỏ thứ \(1+i\) trong \(a[0],a[1],\ldots,a[n-1]\).

Quá trình chấm có thể đưa ra một trong các thông báo lỗi sau:

• Invalid index: một chỉ số thanh ghi không hợp lệ (có thể âm) được truyền làm tham số t, x hoặc y trong một lời gọi hàm.
• Value to store is not b bits long: độ dài của v truyền cho append_store không bằng \(b\).
• Invalid shift value: giá trị p truyền cho append_left hoặc append_right không nằm trong đoạn từ \(0\) đến \(b\), bao gồm cả hai đầu mút.
• Too many instructions: hàm của bạn đã cố thêm quá \(q\) lệnh.

Dữ liệu vào

Trình chấm mẫu đọc dòng đầu tiên theo định dạng:

s n k q

Tiếp theo là một số dòng, mỗi dòng mô tả một bộ dữ liệu theo định dạng:

a[0] a[1] … a[n − 1]

Mỗi bộ dữ liệu gồm \(n\) số nguyên đầu vào \(a[0],a[1],\ldots,a[n-1]\). Sau tất cả các bộ dữ liệu là một dòng chỉ chứa số \(-1\).

Dữ liệu ra

Đầu tiên, trình chấm mẫu gọi construct_instructions(s, n, k, q). Nếu lời gọi vi phạm một ràng buộc trong đề bài, trình chấm mẫu in một trong các thông báo lỗi ở cuối phần Chi tiết cài đặt rồi kết thúc. Ngược lại, trình chấm mẫu trước tiên in từng lệnh do construct_instructions(s, n, k, q) thêm vào, theo đúng thứ tự. Với lệnh store, \(v\) được in theo thứ tự chỉ số từ \(0\) đến \(b-1\).

Sau đó, trình chấm mẫu xử lý các bộ dữ liệu theo thứ tự. Với mỗi bộ dữ liệu, trình chấm chạy chương trình đã xây dựng trên đầu vào của bộ dữ liệu đó.

Với mỗi thao tác print(t), gọi \(d[0],d[1],\ldots,d[n-1]\) là dãy số nguyên sao cho với mỗi \(i\) (\(0\le i\le n-1\)), \(d[i]\) là giá trị số nguyên của dãy bit từ \(i\cdot k\) đến \((i+1)\cdot k-1\) trong thanh ghi \(t\) tại thời điểm thực hiện thao tác. Trình chấm in dãy này theo định dạng:

register t: d[0] d[1] … d[n − 1]

Sau khi thực thi tất cả các lệnh, trình chấm mẫu in đầu ra của chương trình. Nếu \(s=0\), đầu ra cho mỗi bộ dữ liệu có định dạng:

c[0]

Nếu \(s=1\), đầu ra cho mỗi bộ dữ liệu có định dạng:

c[0] c[1] … c[n − 1]

Sau khi thực thi tất cả các bộ dữ liệu, trình chấm in:

number of instructions: X

Trong đó \(X\) là số lệnh trong chương trình của bạn.

Ràng buộc

• \(m=100\).
• \(b=2000\).
• \(0\le s\le 1\).
• \(2\le n\le 100\).
• \(1\le k\le 10\).
• \(q\le 4000\).
• \(0\le a[i]\le 2^k-1\) với mọi \(0\le i\le n-1\).

Phân nhóm

Ví dụ

append_move(1,0)
append_right(1,1,1)
append_and(2,0,1)
append_or(3,0,1)
append_left(3,3,1)
append_or(0,2,3)

Nguồn

IOI 2021, Ngày 2 — Bit Shift Registers (registers).