Câu hỏi 6
Một hãng hàng không có lịch bay ngày 16 tháng 10 năm 2010 như trong bảng sau.
| Số chuyến | Sân bay đi | Sân bay đến | Giờ khởi hành | Giờ đến | Thời gian bay (giờ) |
|---:|---|---|---|---|---:|
| 1 | A | B | 5:00 | 7:00 | 2 |
| 2 | A | C | 7:30 | 9:00 | 1.5 |
| 3 | C | A | 9:45 | 11:15 | 1.5 |
| 4 | C | B | 10:30 | 11:30 | 1 |
| 5 | A | C | 12:00 | 13:30 | 1.5 |
| 6 | B | C | 12:15 | 13:15 | 1 |
| 7 | B | A | 12:30 | 14:30 | 2 |
| 8 | C | A | 14:15 | 15:45 | 1.5 |
| 9 | A | D | 16:30 | 17:15 | 0.75 |
| 10 | D | A | 18:00 | 18:45 | 0.75 |
Một dãy các chuyến bay không chồng lấn thời gian, xuất phát từ sân bay A rồi quay về A, trong đó sân bay đến của mỗi chuyến trùng với sân bay đi của chuyến tiếp theo, được gọi là một chuỗi bay. Một chuỗi bay phải thỏa mãn các quy định lao động sau:
1. Tổng thời gian bay trong một ngày không quá 9 giờ.
2. Thời gian làm nhiệm vụ trong một ngày không quá 12 giờ.
Thời gian làm nhiệm vụ là khoảng thời gian gồm thời gian bay của chuyến thứ nhất, thời gian chờ nối chuyến 1, thời gian bay của chuyến thứ hai, thời gian chờ nối chuyến 2, thời gian bay của chuyến thứ ba, ..., thời gian bay của chuyến thứ $n$ $(n\ge2)$.
Thời gian chờ nối chuyến giữa hai chuyến liên tiếp $x$ và $y$ không chồng lấn là khoảng thời gian từ lúc chuyến $x$ đến đến lúc chuyến $y$ khởi hành.
Bảng dưới cho một ví dụ về chuỗi bay.
| Các chuyến bay | Tổng thời gian bay (giờ) | Thời gian làm nhiệm vụ (giờ) |
|---|---|---|
| 2-3-5-8 | $1.5+1.5+1.5+1.5=6$ | $1.5+0.75$ (chờ nối chuyến 1) $+1.5+0.75$ (chờ nối chuyến 2) $+1.5+0.75$ (chờ nối chuyến 3) $+1.5=8.25$ |
Dãy chuyến bay $1-6$ không phải một chuỗi bay vì không quay về sân bay A. Dãy $6-8$ không phải một chuỗi bay vì không xuất phát từ sân bay A. Dãy $1-7-9-10$ cũng không phải một chuỗi bay vì thời gian làm nhiệm vụ vượt quá 12 giờ. Hãy tìm tất cả các chuỗi bay có thể có trong ngày 16 tháng 10 năm 2010.
| Số chuyến | Sân bay đi | Sân bay đến | Giờ khởi hành | Giờ đến | Thời gian bay (giờ) |
|---:|---|---|---|---|---:|
| 1 | A | B | 5:00 | 7:00 | 2 |
| 2 | A | C | 7:30 | 9:00 | 1.5 |
| 3 | C | A | 9:45 | 11:15 | 1.5 |
| 4 | C | B | 10:30 | 11:30 | 1 |
| 5 | A | C | 12:00 | 13:30 | 1.5 |
| 6 | B | C | 12:15 | 13:15 | 1 |
| 7 | B | A | 12:30 | 14:30 | 2 |
| 8 | C | A | 14:15 | 15:45 | 1.5 |
| 9 | A | D | 16:30 | 17:15 | 0.75 |
| 10 | D | A | 18:00 | 18:45 | 0.75 |
Một dãy các chuyến bay không chồng lấn thời gian, xuất phát từ sân bay A rồi quay về A, trong đó sân bay đến của mỗi chuyến trùng với sân bay đi của chuyến tiếp theo, được gọi là một chuỗi bay. Một chuỗi bay phải thỏa mãn các quy định lao động sau:
1. Tổng thời gian bay trong một ngày không quá 9 giờ.
2. Thời gian làm nhiệm vụ trong một ngày không quá 12 giờ.
Thời gian làm nhiệm vụ là khoảng thời gian gồm thời gian bay của chuyến thứ nhất, thời gian chờ nối chuyến 1, thời gian bay của chuyến thứ hai, thời gian chờ nối chuyến 2, thời gian bay của chuyến thứ ba, ..., thời gian bay của chuyến thứ $n$ $(n\ge2)$.
Thời gian chờ nối chuyến giữa hai chuyến liên tiếp $x$ và $y$ không chồng lấn là khoảng thời gian từ lúc chuyến $x$ đến đến lúc chuyến $y$ khởi hành.
Bảng dưới cho một ví dụ về chuỗi bay.
| Các chuyến bay | Tổng thời gian bay (giờ) | Thời gian làm nhiệm vụ (giờ) |
|---|---|---|
| 2-3-5-8 | $1.5+1.5+1.5+1.5=6$ | $1.5+0.75$ (chờ nối chuyến 1) $+1.5+0.75$ (chờ nối chuyến 2) $+1.5+0.75$ (chờ nối chuyến 3) $+1.5=8.25$ |
Dãy chuyến bay $1-6$ không phải một chuỗi bay vì không quay về sân bay A. Dãy $6-8$ không phải một chuỗi bay vì không xuất phát từ sân bay A. Dãy $1-7-9-10$ cũng không phải một chuỗi bay vì thời gian làm nhiệm vụ vượt quá 12 giờ. Hãy tìm tất cả các chuỗi bay có thể có trong ngày 16 tháng 10 năm 2010.