Olympic Sinh Viên 2020 - Siêu cúp - Lệnh tiến công

View as PDF

Submit solution

Points: 1.30 (partial)
Time limit: 0.5s
Memory limit: 256M

Problem source:
Olympic Sinh Viên
Problem type
Allowed languages
C++, Java

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:

  1. 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;
  2. 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ị;
  3. 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:

  1. 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.

  2. 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ặc attack.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ặc attack.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.
  • 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:
    1. ENCODE DD HH MM
      • Ví dụ: ENCODE 1 12 5 với ý nghĩa gọi hàm encode("01 12:05")
    2. DECODE str
      • Ví dụ DECODE 00011101 với ý nghĩa gọi hàm decode("00011101")
    3. 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âu encryptedMessage.
  • 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âu receivedMessage và so sánh kết quả thu được với bộ dữ liệu ban đầu.

Lưu ý rằng, những lần hàm encodedecode 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

Please read the guidelines before commenting.


There are no comments at the moment.