Juniper Networks
Đề bài
Mô tả
Juniper Networks, Inc. là một tập đoàn đa quốc gia của Mỹ có trụ sở tại Sunnyvale, California. Công ty phát triển và kinh doanh các sản phẩm mạng, gồm bộ định tuyến (router), bộ chuyển mạch, phần mềm quản lý mạng, sản phẩm bảo mật mạng và công nghệ mạng định nghĩa bằng phần mềm.
Aston Martin Lagonda, một trong những thương hiệu xe thể thao danh tiếng nhất của Anh, đã triển khai mạng Juniper tại trụ sở và trên khắp thế giới, giúp các nhà thiết kế và kỹ sư ô tô chế tạo những mẫu xe Anh mang tính biểu tượng mới. Hạ tầng mạng thống nhất đáp ứng nhiều nhu cầu khác nhau tại văn phòng, nhà máy, trung tâm kỹ thuật và trung tâm hiệu năng. Sự đơn giản của Juniper giúp đội IT vận hành theo kịp tốc độ kinh doanh.
Công ty mạng này vừa phát triển một hệ thống định tuyến mới gồm router đánh số từ đến . Router thứ được bảo vệ bởi hai khóa và . Để khởi động hệ thống, máy trạm phải gửi các gói tin để mở khóa các router lần lượt theo thứ tự chỉ số. Mỗi lần máy trạm gửi một gói tin chứa hai giá trị khóa; gói tin đó mở khóa được bao nhiêu router còn lại cũng được, miễn là mỗi router đó khớp với ít nhất một giá trị khóa của gói tin. Vì các router được mở lần lượt, một gói tin mở các router tiếp theo chưa mở theo thứ tự chỉ số và dừng ở router đầu tiên không khớp.
Là một nhà khoa học máy tính chuyên nghiệp, bạn được yêu cầu giảm thiểu lưu lượng mạng của hệ thống. Cho các khóa trên từng router, hãy xác định số gói tin ít nhất cần gửi để khởi động hệ thống.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên , số router.
- Dòng thứ trong dòng tiếp theo chứa hai số nguyên và cách nhau bởi dấu cách: các giá trị khóa của router thứ .
Dữ liệu ra
In ra một số nguyên duy nhất: số gói tin ít nhất cần gửi để khởi động hệ thống.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 1 2 3 4 5 6 7 8 1 2 |
3 | Ví dụ gói tin với khóa mở router ; gói tin với khóa mở router ; gói tin thứ ba mở router . Router không thể mở cùng router vì phải mở lần lượt theo thứ tự. |
| 5 1 2 3 4 2 6 4 5 2 4 |
1 | Gói tin với khóa mở được cả router. |
Bình luận