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:
\[
2^0\cdot d_0+2^1\cdot d_1+\cdots+2^{\ell-1}\cdot d_{\ell-1}.
\]
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à:
\[
2^0\cdot r[i][0]+2^1\cdot r[i][1]+\cdots+2^{b-1}\cdot r[i][b-1].
\]
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:
C++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:
C++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:
C++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:
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:
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:
Nếu \(s=1\), đầu ra cho mỗi bộ dữ liệu có định dạng:
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
| Nhóm |
Điểm |
Ràng buộc bổ sung |
| 1 |
10 |
\(s=0\), \(n=2\), \(k\le 2\), \(q=1000\). |
| 2 |
11 |
\(s=0\), \(n=2\), \(k\le 2\), \(q=20\). |
| 3 |
12 |
\(s=0\), \(q=4000\). |
| 4 |
25 |
\(s=0\), \(q=150\). |
| 5 |
13 |
\(s=1\), \(n\le 10\), \(q=4000\). |
| 6 |
29 |
\(s=1\), \(q=4000\). |
Ví dụ
Ví dụ 1
Giải thích
Giả sử \(s=0\), \(n=2\), \(k=1\), \(q=1000\). Có hai số nguyên đầu vào \(a[0]\) và \(a[1]\), mỗi số có \(k=1\) bit. Trước khi chương trình được thực thi, \(r[0][0]=a[0]\) và \(r[0][1]=a[1]\). Tất cả các bit khác trong bộ vi xử lý đều bằng \(0\). Sau khi thực thi tất cả các lệnh, cần có \(c[0]=r[0][0]=\min(a[0],a[1])\), là giá trị nhỏ nhất của \(a[0]\) và \(a[1]\).
Chỉ có \(4\) đầu vào có thể có:
- Trường hợp \(1\): \(a[0]=0\), \(a[1]=0\).
- Trường hợp \(2\): \(a[0]=0\), \(a[1]=1\).
- Trường hợp \(3\): \(a[0]=1\), \(a[1]=0\).
- Trường hợp \(4\): \(a[0]=1\), \(a[1]=1\).
Trong cả \(4\) trường hợp, \(\min(a[0],a[1])\) bằng phép AND theo từng bit giữa \(a[0]\) và \(a[1]\). Vì vậy, có thể xây dựng chương trình bằng các lời gọi sau:
append_move(1, 0): thêm lệnh sao chép \(r[0]\) sang \(r[1]\).append_right(1, 1, 1): thêm lệnh dịch tất cả các bit trong \(r[1]\) sang phải \(1\) bit, rồi lưu kết quả trở lại \(r[1]\). Vì mỗi số nguyên có độ dài \(1\) bit, sau lệnh này \(r[1][0]\) bằng \(a[1]\).append_and(0, 0, 1): thêm lệnh lấy phép AND theo từng bit giữa \(r[0]\) và \(r[1]\), rồi lưu kết quả vào \(r[0]\). Sau lệnh này, \(r[0][0]\) được gán bằng phép AND theo từng bit giữa \(r[0][0]\) và \(r[1][0]\), tức là phép AND theo từng bit giữa \(a[0]\) và \(a[1]\), đúng như yêu cầu.
Ví dụ 2
Giải thích
Giả sử \(s=1\), \(n=2\), \(k=1\), \(q=1000\). Như ví dụ trước, chỉ có \(4\) đầu vào có thể có. Trong cả \(4\) trường hợp, \(\min(a[0],a[1])\) là phép AND theo từng bit giữa \(a[0]\) và \(a[1]\), còn \(\max(a[0],a[1])\) là phép OR theo từng bit giữa \(a[0]\) và \(a[1]\). Có thể thực hiện các lời gọi sau, theo thứ tự:
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)
Sau khi thực thi các lệnh này, \(c[0]=r[0][0]\) chứa \(\min(a[0],a[1])\), còn \(c[1]=r[0][1]\) chứa \(\max(a[0],a[1])\), nên đầu vào đã được sắp xếp.
Nguồn
IOI 2021, Ngày 2 — Bit Shift Registers (registers).
