trang chủ / đề bài / icpcwf07_g

Mạng chuyển mạch gói

Đề bài

Mô tả

Mạng chuyển mạch gói xử lý thông tin theo từng đơn vị nhỏ: các thông điệp dài được chia thành nhiều gói tin trước khi định tuyến. Mỗi gói có thể đi theo một đường khác nhau, và các gói của cùng một thông điệp có thể đến vào những thời điểm khác nhau hoặc sai thứ tự, nhưng máy nhận vẫn ghép lại đúng thông điệp ban đầu.

Máy nhận dùng một bộ nhớ đệm để giữ các gói đến sai thứ tự. Hãy viết chương trình tính kích thước bộ nhớ đệm nhỏ nhất (tính bằng byte) cần để ghép lại các thông điệp đến, khi biết số thông điệp (N), số gói tin (M), phần thông điệp chứa trong mỗi gói, kích thước mỗi thông điệp và thứ tự đến của các gói.

Khi một gói đến, nó có thể được đặt vào bộ nhớ đệm hoặc được chuyển thẳng ra vùng xuất. Mọi gói đang nằm trong bộ nhớ đệm đều có thể được chuyển ra vùng xuất vào bất kỳ lúc nào. Một gói được gọi là "đi qua bộ nhớ đệm" khi nó được chuyển ra vùng xuất. Một thông điệp được gọi là "đi qua bộ nhớ đệm" khi mọi gói của nó đã đi qua bộ nhớ đệm.

Các gói của một thông điệp phải đi qua bộ nhớ đệm theo đúng thứ tự dữ liệu. Ví dụ, gói chứa các byte từ 3 đến 5 của một thông điệp phải đi qua bộ nhớ đệm trước gói chứa các byte từ 6 đến 10 của cùng thông điệp đó. Các thông điệp có thể đi qua bộ nhớ đệm theo thứ tự bất kỳ, nhưng mọi gói của một thông điệp phải đi qua bộ nhớ đệm liên tiếp nhau và đúng thứ tự (nhưng không nhất thiết cùng lúc). Lưu ý rằng, khác với hệ thống đệm thực tế, quá trình trong bài này có thể nhìn trước toàn bộ các gói sẽ đến để đưa ra quyết định.

Mỗi gói gồm dữ liệu và phần đầu. Phần đầu chứa ba số: số hiệu thông điệp, số thứ tự byte đầu tiên và số thứ tự byte cuối cùng của dữ liệu trong gói. Byte đầu tiên của mỗi thông điệp có số thứ tự 1.

Ví dụ, hình dưới đây cho ba thông điệp (kích thước 10, 20 và 5 byte) và năm gói tin. Kích thước bộ nhớ đệm nhỏ nhất cho ví dụ này là 10 byte. Khi đến, gói #1 và gói #2 được lưu vào bộ nhớ đệm, chiếm 10 byte. Sau đó gói #3 đi thẳng qua bộ nhớ đệm. Gói #4 đi thẳng qua bộ nhớ đệm, rồi gói #2 rời bộ nhớ đệm. Cuối cùng, gói #5 đi thẳng qua bộ nhớ đệm và gói #1 rời bộ nhớ đệm.

Ba thông điệp (kích thước 10, 20 và 5 byte) và năm gói tin; gói #1 đến đầu tiên.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên của mỗi bộ test chứa hai số nguyên N và M. Dòng thứ hai chứa N số nguyên là kích thước các thông điệp tính bằng byte: số thứ nhất là kích thước thông điệp #1, số thứ hai là kích thước thông điệp #2, v.v. Mỗi dòng trong M dòng tiếp theo mô tả một gói tin theo thứ tự đến, gồm ba số nguyên: số hiệu thông điệp, số thứ tự byte đầu tiên và byte cuối cùng của dữ liệu trong gói. Không gói nào chứa quá 64 byte dữ liệu.

Sau bộ test cuối cùng là một dòng chứa hai số 0.

Dữ liệu ra

Với mỗi bộ test, in một dòng gồm số thứ tự của bộ test (bắt đầu từ 1) và kích thước bộ nhớ đệm nhỏ nhất tính bằng byte cần để ghép lại các thông điệp ban đầu. In một dòng trống sau kết quả của mỗi bộ test. Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • 1≤N≤5, 1≤M≤1000.
  • Mỗi gói chứa từ 1 đến 64 byte dữ liệu.
  • Các gói của mỗi thông điệp chia thông điệp đó thành các đoạn byte rời nhau phủ kín từ byte 1 đến byte cuối cùng (mỗi byte nằm trong đúng một gói).
  • Mỗi file có không quá 100 bộ test.

Ví dụ

Input Output Giải thích
3 3
5 5 5
1 1 5
2 1 5
3 1 5
3 5
10 20 5
2 16 20
1 6 10
3 1 5
1 1 5
2 1 15
0 0
Case 1: 0

Case 2: 10

Bộ 1: mỗi gói là một thông điệp trọn vẹn và đi thẳng qua bộ nhớ đệm. Bộ 2: là ví dụ trong hình.
1 3
10
1 7 10
1 4 6
1 1 3
2 4
3 6
2 1 4
1 2 3
2 5 6
1 1 1
2 3
64 2
2 2 2
1 1 64
2 1 1
0 0
Case 1: 7

Case 2: 2

Case 3: 1

Bộ 1: hai gói đầu phải chờ (4+3=7 byte) đến khi gói chứa byte 1..3 tới. Bộ 2: cho thông điệp #2 đi trước, chỉ gói 1 2 3 phải chờ; nếu thông điệp #1 đi trước thì cần 8 byte. Bộ 3: cho thông điệp #1 đi trước, chỉ gói 2 2 2 phải chờ; gói 64 byte đi thẳng qua bộ nhớ đệm.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0