| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P148PROD - ROUND 8D - Gán tần số |
Trong mạng viễn thông di động, người ta lắp đặt các trạm chuyển tiếp sóng BTS. Để tránh xuyên nhiễu, người ta sẽ gán cho hai trạm gần nhau hai tần số khác xa nhau. Trong bài toán này, giả sử các tần số là các số nguyên dương. Hai trạm gần nhau cần được gán tần số cách nhau ít nhất 2 đơn vị. Ví dụ trong hình sau là mô tả hai nhóm các trạm BTS:
Và cách sắp xếp tần số cho hai vùng đó có thể như sau:
Ta thấy, cách sắp xếp như trong hình bên phải là chưa tối ưu vì ta có thể thay trạm có giá trị 5 bằng giá trị 1. Và số tần số phải dùng chỉ là 2.
Giả sử các điểm đặt BTS là các tọa độ trong không gian 2 chiều. Hai trạm được coi là gần nhau nếu khoảng cách giữa chúng không quá 20. Hãy viết chương trình tính số lượng tần số ít nhất cần dùng để gán cho tất cả các trạm.
Input
Mỗi bộ test gồm 2 dòng:
- Dòng đầu tiên ghi số nguyên dương N là số trạm
- Dòng tiếp theo ghi 2*n số thực lần lượt là tọa độ của N trạm cần gán tần số
Input kết thúc khi N=0. Chú ý, có không quá 12 trạm BTS trong mỗi bộ test, và mỗi trạm có không quá 4 trạm gần với nó.
Output
Với mỗi bộ test, tính ra số lượng tần số nhỏ nhất cần dùng (f) và ghi kết quả theo khuôn dạng:
The towers in case n can be covered in f frequencies.
Example
Input: 5
0 0 5 7.5 1 -3 10.75 -20.1 12.01 -22
6
0 1 19 0 38 1 38 21 19 22 0 21
0 Output: The towers in case 1 can be covered in 3 frequencies.
The towers in case 2 can be covered in 2 frequencies.
| Được gửi lên bởi: | adm |
| Ngày: | 2014-03-23 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
