Ma trận bit
Đề bài
Cho một ma trận vuông mà mỗi phần tử là một bit bất kỳ. Mỗi hàng tính từ trái qua phải, mỗi cột tính từ trên xuống dưới và hai đường chéo chính, phụ là các dãy bit có độ dài bằng nhau và đều có thể tạo thành một số nhị phân có nghĩa.
Yêu cầu: hãy tìm trong chúng số nhị phân có giá trị lớn nhất.
Dữ liệu vào: tập tin văn bản MTBIT.INP chỉ gồm $N$ hàng, trên mỗi hàng ghi một dãy bit có độ dài là $N$ bit $(N \le 256)$.
Kết quả: tập tin văn bản MTBIT.OUT gồm có một dòng duy nhất ghi số nhị phân lớn nhất tìm được.
Subtask:
- 20% số test đầu tiên có $N \le 20$;
- 20% số test tiếp theo có $N \le 50$;
- 20% số test tiếp theo có $N \le 100$;
- 40% số test còn lại không có điều kiện gì thêm.
Lưu ý (trên CLUE OJ): bài này đọc dữ liệu từ file MTBIT.INP và ghi ra file MTBIT.OUT với tên file y như trong đề thi, không nhập xuất chuẩn từ bàn phím/màn hình. Bài chỉ được nộp 1 lần duy nhất nên hãy kiểm tra thật kỹ trước khi nộp.
010
101
001101Lời mở đầu
Bài thi HSG lớp 9 này nhìn qua rất đơn giản: duyệt $N$ hàng, $N$ cột, 2 đường chéo, đổi ra số rồi lấy lớn nhất. Cái bẫy nằm ở con số $N \le 256$: một số nhị phân 256 bit thì không kiểu số nguyên nào của C++ chứa nổi. Mình sẽ đi từ cách đổi ra long long (ăn được 2 subtask đầu) tới cách so sánh trực tiếp trên xâu – vừa ngắn hơn vừa ăn trọn 100%.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Subtask | Các test | $N$ thực tế | Cách 1 (long long) | Cách 2 (xâu) |
|---|---|---|---|---|
| 1: $N \le 20$ | 1 – 20 | 2 … 19 | 20/20 | 20/20 |
| 2: $N \le 50$ | 21 – 40 | 21 … 50 | 20/20 | 20/20 |
| 3: $N \le 100$ | 41 – 60 | 51 … 100 | 3/20 | 20/20 |
| 4: $N \le 256$ | 61 – 100 | 101 … 256 | 0/40 | 40/40 |
Bộ test 100 test, chia đúng như đề: test 1–20 có $N \le 20$ (nhỏ nhất $N = 2$), test 21–40 có $N \le 50$, test 41–60 có $N \le 100$, test 61–100 lớn tới $N = 256$ (10 test cuối đều đúng $N = 256$). Một vài điều đáng để ý:
- Test 2 là ma trận $2 \times 2$ có đáp án
01– bắt đầu bằng số 0, phải in đủ $N$ bit. - Đáp án nằm ở đường chéo chính (và không hàng/cột nào bằng) ở đúng 2 test: test 5 và test 40. Đường chéo phụ không bao giờ là đáp án duy nhất, nên đọc chéo phụ từ trên xuống hay từ dưới lên đều qua.
- Ở các test lớn, đáp án gần như luôn là một hàng hoặc cột có rất nhiều bit 1 ở đầu.
Ý tưởngCác dãy cùng độ dài: so sánh xâu chính là so sánh số
Có tất cả $2N + 2$ dãy bit: $N$ hàng, $N$ cột, đường chéo chính (từ góc trên trái xuống góc dưới phải) và đường chéo phụ (từ góc trên phải xuống góc dưới trái). Mỗi dãy dài đúng $N$ bit.
Với hai số nhị phân cùng số chữ số (kể cả các số 0 ở đầu), so sánh chúng giống như tra từ điển: nhìn từ trái sang, tại vị trí đầu tiên hai dãy khác nhau, dãy nào có bit 1 thì lớn hơn. Ví dụ $1\underline{0}11 < 1\underline{1}00$ vì ở bit thứ 2, dãy sau có 1. Các bit phía sau không còn quan trọng nữa, vì bit thứ 2 có giá trị $2^2 = 4$, lớn hơn tổng tất cả các bit sau $2^1 + 2^0 = 3$.
< của C++ (thứ tự từ điển, '0' < '1') cho kết quả đúng bằng so sánh số nhị phân – không cần đổi ra số, nên $N = 256$ hay lớn hơn nữa cũng không sao.Kết quả in ra cũng phải giữ đủ $N$ bit: bộ test có trường hợp đáp án là 01 (bắt đầu bằng số 0).
Em nhập ma trận rồi bấm Tiếp để xem máy lần lượt lấy từng hàng, cột, đường chéo ra và so với số lớn nhất hiện tại (ô vàng là vị trí đầu tiên hai dãy khác nhau):
Cách 1Đổi ra long long – subtask 1 và 2
Cách tự nhiên nhất: đổi mỗi dãy bit ra số nguyên bằng công thức Horner x = x * 2 + bit, lấy max, cuối cùng đổi số lớn nhất ngược lại thành $N$ bit để in. Kiểu long long chứa được số không âm tới $2^{63} - 1$, tức là tối đa 63 bit, nên cách này chỉ đúng khi $N \le 63$.
while(cin >> s)đọc đến hết file; số dòng đọc được chính là $N$ (đề không cho sẵn $N$).- Hàm
doisođọc bit từ trái sang phải: mỗi bước nhân đôi giá trị cũ rồi cộng bit mới. - Vòng in cuối lấy bit thấp nhất
best & 1ghép vào đầu xâu kết quả, lặp đúng $n$ lần nên giữ được các số 0 ở đầu. - Khi $N > 63$, phép
x * 2bị tràn số và cho kết quả sai mà không báo lỗi gì.
Kết quả chạy thật: bản C++ đúng 43/100 test: trọn 40 test của subtask 1 và 2 ($N \le 50$), cộng thêm 3 test ở subtask 3 có $N \le 63$ (test 42, 52, 57); các test còn lại sai do tràn số. Riêng bản Python của cách này lại đúng 100/100 (chậm nhất 0.38 giây) vì số nguyên của Python không giới hạn độ lớn – int(x, 2) đổi được cả xâu 256 bit.
Cách 2So sánh trực tiếp trên xâu – 100%
Áp dụng ý tưởng ở trên: không đổi ra số nữa, cứ để nguyên các xâu độ dài $N$ và dùng max của string. Code còn ngắn hơn Cách 1, và in thẳng xâu lớn nhất ra là xong.
max(best, a[i])với haistringdùng phép so sánh từ điển. Vì mọi xâu đều dài đúng $N$ nên thứ tự từ điển trùng với thứ tự số.- Chú ý: nếu các xâu khác độ dài thì không được so sánh kiểu này (ví dụ
"9" > "10"theo từ điển). Bài này may mắn mọi dãy đều dài $N$. - Đường chéo phụ
a[i][n - 1 - i]đọc từ góc trên phải xuống góc dưới trái. Trên bộ test, đọc theo chiều ngược lại (từ dưới lên) cũng cho cùng đáp án, nên các bạn hiểu theo chiều nào cũng được.
Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0.07 giây; bản Python đúng 100/100 test, chậm nhất 0.32 giây.
Lỗi hay gặpQuên đường chéo, in mất số 0 ở đầu
00 / 01, đáp án 01) sẽ in ra 1 và bị sai. Đáp án yêu cầu đúng dãy bit $N$ ký tự.long long) đạt 43/100 test – qua subtask 1, 2; Cách 2 (C++ và Python) và bản Python của Cách 1 đều đạt 100/100 test, mỗi test dưới 0.4 giây. Bài học rút ra: khi số quá lớn mà ta chỉ cần so sánh, hãy nghĩ tới việc so sánh trên xâu.
Nhận xét
Đăng nhận xét