Ngày
DD
tới, vào giờHH:MM
, toàn quân tổng tiến công!
Đó là quân lệnh từ sở chỉ huy cần được truyền tới tất cả các đơn vị chiến đấu. Tuấn làm việc trong bộ phận phụ trách thiết kế các module đảm bảo thông tin được truyền đi an toàn và chính xác. Thông tin được truyền đi sẽ gồm ba giai đoạn:
- Mã hóa thông tin (encode): từ sở chỉ huy, thông tin (
DD, HH, MM
) sẽ được mã hóa thành một dãy bit; - Truyền tin (transmission): sử dụng những phương tiện thô sơ để truyền dãy bit tới các máy nhận ở các đơn vị;
- Giải mã thông tin (decode): từ dãy bit nhận được, giải mã lại thông tin (
DD, HH, MM
).
Tuấn phụ trách thiết kế module 1 và 3 nhưng gặp rất nhiều khó khăn. Lý do chính là do kĩ thuật truyền tin thô sơ và phụ thuộc vào yếu tố kĩ năng của con người, nên không phải thông tin lúc nào cũng được truyền đi một cách hoàn toàn chính xác. Thông tin truyền đi có thể bị sai sót tối đa 1 bit. Vì vậy, yêu cầu của hệ thống mã hóa này phải có khả năng phát hiện lỗi, và tự sửa chữa sai sót. Nói cách khác, cho dù thông tin truyền đi có thể sai 1 bit nhưng vẫn phải tự khôi phục được.
Yêu cầu: Hãy giúp Tuấn thực hiện được công việc của mình.
Giao tiếp
Bạn cần viết hai hàm sau:
string encode (string message)
Hàm nhận vào một xâu độ dài 8 có dạng
DD HH:MM
trong đóDD
là một số nguyên trong đoạn ~[1,31]~,HH
là một số nguyên trong đoạn ~[0,23]~ vàMM
là một số nguyên trong đoạn ~[0,59]~. Hàm cần trả về một xâu không quá 50 kí tự chỉ gồm các kí tự 0 hoặc 1 là xâu được mã hóa.string decode (string encryptedMessage)
Hàm nhận vào một xâu có độ dài không quá 50 kí tự, chỉ gồm các kí tự 0 hoặc 1. Hàm cần trả ra một xâu có độ dài 8 có định dạng giống xâu đầu vào của hàm
encode
là xâu đã được giải mã.
Làm bài
Các bạn có thể download file attack_public.zip chứa các file hỗ trợ làm bài. Trong đó:
attack.cpp
/attack.java
là file các bạn cần làm việc và viết thuật toán mã hóa.stub.cpp
/stub.java
là file hỗ trợ các chức năng nhập xuất dữ liệu.compile_cpp.sh
/compile_java.sh
là script hỗ trợ việc biên dịch chương trình.
Bạn có thể làm các việc sau:
- Viết thuật toán mã hóa của bạn vào file
attack.cpp
hoặcattack.java
. Các bạn có thể viết thêm các hàm phụ trợ khác. - Biên dịch và thực thi bằng script được cung cấp như sau:
- Vào thư mục chứa file
attack.cpp
hoặcattack.java
, click chuột phải và chọn Open in Terminal. - Biên dịch file mã nguồn ra file thực thi bằng cách chạy lệnh
./compile_cpp.sh
hoặc./compile_java.sh
. - Thực thi bằng cách chạy lệnh
./attack
hoặc./run_java.sh
.
- Vào thư mục chứa file
- File thực thi
attack
nhận dữ liệu vào từ dòng nhập chuẩn (stdin) ở một trong hai dạng:ENCODE DD HH MM
- Ví dụ:
ENCODE 1 12 5
với ý nghĩa gọi hàmencode("01 12:05")
- Ví dụ:
DECODE str
- Ví dụ
DECODE 00011101
với ý nghĩa gọi hàmdecode("00011101")
- Ví dụ
- File thực thi sẽ in ra một xâu là kết quả của hàm tương ứng mà chương trình bạn chạy.
Ngoài ra, trong quá trình làm bài, các bạn có thể tự thay đổi file stub.cpp
/ stub.java
để phục vụ theo cách nhập xuất dự liệu mà bạn muốn.
Nộp bài
Các bạn chỉ nộp file attack.cpp
hoặc attack.java
mà không nộp file nào khác.
Chấm bài
Bài của các bạn sẽ được chấm như sau. Ban giám khảo chuẩn bị một file hệ thống chấm (được gọi là manager).
- Chương trình manager sẽ gọi hàm
encode
của bạn với một bộ dữ liệu (DD, HH, MM
) nào đó và thu được xâuencryptedMessage
. - Chương trình manager sẽ lặp lại các bước sau nhiều lần:
- Sửa một bit hoặc không sửa bit nào tạo thành xâu
receivedMessage
. - Chương trình manager sẽ gọi hàm
decode
của bạn với đầu vào là xâureceivedMessage
và so sánh kết quả thu được với bộ dữ liệu ban đầu.
- Sửa một bit hoặc không sửa bit nào tạo thành xâu
Lưu ý rằng, những lần hàm encode
và decode
của bạn được gọi sẽ được chạy ở các tiến trình độc lập. Vì vậy, nếu hàm encode
có sử dụng và lưu trữ dữ liệu vào các biến toàn cục, các dữ liệu này sẽ không tồn tại khi hàm decode
được thực thi.
Chấm điểm
Với mỗi bộ dữ liệu, bạn sẽ không được điểm nếu:
- Tương tác sai quy cách (dữ liệu trả ra không đúng định dạng)
- Chạy sinh lỗi
- Chạy quá thời gian
- Xâu sau khi giải mã khác với xâu ban đầu
Gọi độ dài xâu mã hóa của bạn là ~L~, bạn sẽ nhận được điểm dựa trên độ tốt của ~L~ như sau:
Độ dài xâu mã hóa của bạn | Điểm của test |
---|---|
~1 \leq L \leq 21~ | ~100\%~ |
~L = 22~ | ~90\%~ |
~L = 23~ | ~80\%~ |
~24 \leq L \leq 25~ | ~60\%~ |
~26 \leq L \leq 30~ | ~40\%~ |
~31 \leq L \leq 35~ | ~30\%~ |
~36 \leq L \leq 40~ | ~20\%~ |
~41 \leq L \leq 50~ | ~10\%~ |
Comments