Bài tập | NEU OJ

Khi truyền một tệp lớn qua mạng (kiểu giao thức rsync), tệp thường được chia thành $n$ khối theo thứ tự. Bên gửi tính trước checksum SHA-256 cho từng khối gốc: $R_1, R_2, \ldots, R_n$ . Sau khi nhận, bên nhận cần xác định những khối nào đã bị hỏng (do lỗi đường truyền) bằng cách so sánh lại checksum.

Cho danh sách checksum tham chiếu $R_1, \ldots, R_n$ (SHA-256, dạng hex) và nội dung $n$ khối thực nhận được $B_1, \ldots, B_n$ (đúng thứ tự tương ứng, mỗi khối là một dòng, có thể là chuỗi rỗng). Với mỗi $i$ , tính $\text{SHA256}(B_i)$ và so sánh với $R_i$ :

Nếu khớp: khối $i$ nguyên vẹn.
Nếu không khớp: khối $i$ được xem là bị hỏng.

Hãy xác định số lượng khối bị hỏng và chỉ số (1-indexed) của chúng theo thứ tự tăng dần.

Ví dụ: $n = 3$ , các khối 1 và 3 khớp checksum, khối 2 không khớp → in ra 1 (số khối hỏng) và dòng tiếp theo 2 (chỉ số khối hỏng).

Định dạng đầu vào:
- Dòng 1: số nguyên $n$ ( $0 \le n \le 1000$ ).
- $n$ dòng tiếp theo: checksum tham chiếu $R_1, \ldots, R_n$ (mỗi dòng một chuỗi hex 64 ký tự).
- $n$ dòng tiếp theo: nội dung khối thực nhận $B_1, \ldots, B_n$ (mỗi khối một dòng, có thể rỗng).
Định dạng đầu ra:
In ra hai dòng:
- Dòng 1: số nguyên $m$ — số lượng khối bị hỏng.
- Dòng 2: danh sách chỉ số (1-indexed, tăng dần) các khối bị hỏng, cách nhau bởi một khoảng trắng; nếu $m = 0$ thì dòng này để rỗng.

solution

Đề bài: [An toàn thông tin] Phát hiện khối dữ liệu bị hỏng qua checksum