Ghép Đôi (Platinum)

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ con bò đứng trên một đường thẳng, mỗi con là giống Holstein (H) hoặc Guernsey (G). Mỗi con bò $i$ có:

Các con bò được ghép đôi theo các quy tắc sau:

Mỗi cặp gồm đúng một con Holstein và một con Guernsey.
Hai con bò được ghép chỉ khi khoảng cách giữa chúng không vượt quá $K$ : $| x_{h} - x_{g} | \leq K$ .
Mỗi con bò thuộc đúng một cặp hoặc không được ghép.
Cách ghép phải là cực đại: không tồn tại hai con bò chưa được ghép (một Holstein và một Guernsey) mà khoảng cách giữa chúng $\leq K$ .

Cho biết loại bài toán $T$ :

Dòng đầu tiên chứa ba số nguyên $T$ , $N$ , $K$ .

$N$ dòng tiếp theo, mỗi dòng chứa $b_{i}$ , $x_{i}$ , $y_{i}$ (theo thứ tự $x_{i}$ tăng dần nghiêm ngặt).

Một số nguyên duy nhất: tổng trọng số của các con bò không được ghép (nhỏ nhất nếu $T = 1$ , lớn nhất nếu $T = 2$ ).

Input	Output	Giải thích
2 5 4 G 1 1 H 3 4 G 4 2 H 6 6 H 8 9	16	Ghép cặp H(3) với G(4). Các con không được ghép: G(1)=1, H(6)=6, H(8)=9. Tổng = 16. Cách ghép này cực đại vì G(1) và H(3) cách nhau 2 ≤ 4 nhưng H(3) đã được ghép.
1 5 4 G 1 1 H 3 4 G 4 2 H 6 6 H 8 9	6	Ghép cặp G(1) với H(3) và G(4) với H(8). Con không ghép: H(6)=6. Tổng = 6.
2 10 76 H 1 18 H 18 465 H 25 278 H 30 291 H 36 202 G 45 96 G 60 375 G 93 941 G 96 870 G 98 540	1893	Cách ghép tối ưu để tối đa hóa tổng không ghép.

Trong ví dụ 1 (T=2): Nếu ghép G(1) với H(3) thì còn lại G(4), H(6), H(8) không ghép, tổng = 2+6+9=17, nhưng G(4) và H(6) cách nhau 2 ≤ 4, vi phạm tính cực đại. Do đó đây không phải cách ghép hợp lệ.
Trong ví dụ 2 (T=1): Tổng trọng số tất cả bò = 22. Ghép tối ưu để tổng không ghép nhỏ nhất.

Bình luận

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