trang chủ / đề bài / icpcwf05_j

Vùng phủ sóng

Đề bài

Mô tả

Cột điện thoại là một phần của công nghệ đã lỗi thời. Ngày nay điện thoại di động cho phép chúng ta gọi cho bất kỳ ai, ở bất kỳ đâu, không phụ thuộc vào dây dẫn. Chỉ có một vấn đề: nếu không có trạm phát sóng ở gần thì điện thoại di động trở nên vô dụng.

Khi không có đồi núi, một trạm phát sóng phủ sóng một vùng hình tròn. Thay vì lên kế hoạch kéo dây, một công ty điện thoại không dây phải lên kế hoạch xây các trạm phát sóng. Xây các trạm quá xa nhau sẽ tạo ra những lỗ hổng phủ sóng và làm tăng số lời phàn nàn. Xây các trạm quá gần nhau sẽ tạo ra những vùng rộng được nhiều trạm cùng phục vụ, gây dư thừa và lãng phí.

Công ty Điện thoại Di động Quốc tế (ICPC) đang xây dựng chiến lược mạng lưới để xác định vị trí đặt trạm tối ưu. Vì phần lớn khách hàng đã thay điện thoại bàn cũ bằng điện thoại di động, chiến lược đặt trạm là phục vụ được càng nhiều nhà khách hàng càng tốt.

Hình dưới đây cho thấy vùng phục vụ của năm trạm mà phòng chiến lược của ICPC dự định xây trong năm nay. Trạm 5 sẽ phục vụ 24 khách hàng, trong đó 6 người cũng được trạm 4 phục vụ. Các trạm 1, 2 và 3 có một vùng phục vụ chung chứa 3 khách hàng.

Ngay sau khi kế hoạch xây năm trạm này được công bố, ban lãnh đạo cấp cao ra lệnh dừng mọi việc xây trạm. Khách hàng phản đối buộc họ phải nới lỏng quyết định, cho phép xây ba trong năm trạm đã dự định. Tất nhiên ba trạm này phải phục vụ được nhiều khách hàng nhất có thể. Tìm lựa chọn tốt nhất không hề đơn giản (trong ví dụ này lựa chọn tốt nhất là các trạm 2, 4 và 5, phục vụ 68 khách hàng).

Bạn hãy viết chương trình giúp ICPC chọn những trạm cần xây trong các trường hợp như vậy. Nếu nhiều lựa chọn phục vụ cùng số khách hàng thì ưu tiên các lựa chọn có trạm 1. Nếu quy tắc này vẫn còn nhiều hơn một lựa chọn thì ưu tiên các lựa chọn có trạm 2, và cứ thế tiếp tục.

Mỗi vùng phục vụ chung trong dữ liệu gồm những khách hàng được phục vụ bởi đúng các trạm của vùng đó (không trạm nào khác); các vùng chung rời nhau. Chẳng hạn trong hình, 7 khách hàng của vùng chung giữa trạm 1 và trạm 2 không bao gồm 3 khách hàng của vùng chung giữa các trạm 1, 2 và 3. Số khách hàng của một trạm là tổng số khách hàng chỉ do riêng trạm đó phục vụ và số khách hàng của mọi vùng chung chứa trạm đó.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Dòng đầu tiên của mỗi bộ test chứa hai số nguyên dương: số trạm dự định n và số trạm thực sự được xây k. Dòng tiếp theo chứa n số, mỗi số là số khách hàng được một trạm dự định phục vụ (số thứ nhất ứng với trạm thứ nhất, và cứ thế). Dòng tiếp theo chứa số m là số vùng phục vụ chung. Mỗi dòng trong m dòng tiếp theo mô tả một vùng phục vụ chung: dòng bắt đầu bằng số t là số trạm có chung vùng này, tiếp theo là t số hiệu của các trạm đó. Số cuối cùng trên dòng là số khách hàng trong vùng phục vụ chung. Các số trên một dòng cách nhau bởi một hoặc nhiều dấu cách.

Dòng cuối cùng của dữ liệu gồm hai số nguyên 0 0.

Dữ liệu ra

Với mỗi bộ test, in số khách hàng được phục vụ và lựa chọn tốt nhất cho vị trí các trạm (các số hiệu trạm theo thứ tự tăng dần). Theo đúng định dạng trong ví dụ.

Ràng buộc

  • 1≤k≤n≤20.
  • Số khách hàng của mỗi trạm là số nguyên từ 0 đến 106.
  • 0≤m≤10; với mỗi vùng chung, 2≤t≤n, các số hiệu trạm khác nhau và nằm trong [1,n], số khách hàng là số nguyên không âm; hai vùng chung khác nhau có tập trạm khác nhau.
  • Dữ liệu nhất quán: với mỗi trạm, tổng số khách hàng của các vùng chung chứa trạm đó không vượt quá số khách hàng của trạm.
  • Mỗi file có không quá 20 bộ test.

Ví dụ

Input Output Giải thích
5 3
15 20 25 30 24
5
2 1 2 7
3 1 2 3 3
2 2 3 2
2 3 4 5
2 4 5 6
5 3
25 25 25 25 25
4
2 1 2 5
2 2 3 5
2 3 4 5
2 4 5 5
5 3
25 25 25 25 25
0
0 0
Case Number 1
Number of Customers: 68
Locations recommended: 2 4 5
Case Number 2
Number of Customers: 75
Locations recommended: 1 3 5
Case Number 3
Number of Customers: 75
Locations recommended: 1 2 3
Bộ test 1 là hình trên: các trạm 2, 4, 5 phục vụ 20+30+24−6=68 khách hàng. Bộ test 2: chọn 1,3,5 không có vùng chung nào bị trùng nên được 75. Bộ test 3: mọi lựa chọn đều được 75, ưu tiên lựa chọn có trạm 1, rồi trạm 2, rồi trạm 3.
4 3
10 10 10 9
1
3 1 2 3 6
4 2
10 10 10 10
2
2 1 2 4
2 3 4 4
1 1
7
0
0 0
Case Number 1
Number of Customers: 23
Locations recommended: 1 2 4
Case Number 2
Number of Customers: 20
Locations recommended: 1 3
Case Number 3
Number of Customers: 7
Locations recommended: 1
Ví dụ tự thêm. Bộ test 1: chọn cả ba trạm 1,2,3 chỉ được 4+4+4+6=18; mỗi lựa chọn có trạm 4 và hai trong ba trạm kia được 23, ưu tiên 1,2,4. Bộ test 2: 1,2 chỉ được 16, còn 1,3 được 20.

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