Bậc thầy xoay chuyển dư luận
Đề bài
Mô tả
Là nhân viên của tập đoàn thăm dò dư luận chính trị được tin cậy nhất thế giới, bạn phải lấy những vấn đề phức tạp ngoài đời thực và rút gọn chúng thành vài con số. Việc này không phải lúc nào cũng dễ. Một cuộc bầu cử lớn sắp diễn ra và, theo yêu cầu của Ứng viên X, bạn vừa thăm dò xong người. Bạn thu được ba thông tin từ mỗi người, với người thứ được ghi lại như sau:
- : số chữ số của mà người đó thuộc lòng;
- : số sợi tóc trên đầu người đó;
- : người đó có bỏ phiếu cho Ứng viên X hay không.
Thật không may, bạn bắt đầu tự hỏi liệu đây có thực sự là những câu hỏi phù hợp nhất hay không. Thực tế, bạn không thấy bất kỳ mối tương quan nào giữa , và trong dữ liệu. Tất nhiên, bạn không thể cứ thế nói ngược lại khách hàng của mình, đó là cách nhanh nhất để mất việc!
Có lẽ lời giải là tìm một công thức trọng số nào đó khiến kết quả trông có ý nghĩa. Bạn sẽ chọn hai số thực và , rồi sắp xếp các kết quả thăm dò theo đại lượng . Phép sắp xếp trông đẹp nhất nếu các kết quả có đúng tụ lại gần nhau nhất có thể. Chính xác hơn, nếu và là chỉ số (trong dãy đã sắp xếp) của kết quả đầu tiên và kết quả cuối cùng có đúng, bạn muốn cực tiểu hóa kích thước cụm, tức là . Lưu ý rằng với một số cách chọn và , các bộ có thể bằng nhau về đại lượng này. Khi đó, bạn phải giả sử thứ tự tệ nhất có thể xảy ra (thứ tự làm kích thước cụm lớn nhất với cặp đó).
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , số người được thăm dò.
Mỗi dòng trong dòng tiếp theo mô tả một người, gồm ba số nguyên , và , trong đó nếu người đó bỏ phiếu cho Ứng viên X và nếu ngược lại.
Dữ liệu ra
In ra kích thước cụm nhỏ nhất có thể trên mọi cặp .
Ràng buộc
- .
- , .
- Có ít nhất một người bỏ phiếu cho Ứng viên X.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 0 10 0 10 0 1 12 8 1 5 5 0 11 2 1 11 3 0 |
4 | Với , , các đại lượng là . Thứ tự sắp xếp là ; người đầu tiên bỏ phiếu cho X có đại lượng (vị trí ), người cuối cùng có đại lượng (vị trí ), kích thước cụm . |
| 10 6 1 1 0 2 0 2 1 1 6 1 1 8 2 0 4 4 0 4 0 0 2 3 1 6 1 0 6 3 1 |
8 | Ví dụ, , đạt kích thước cụm . Người thứ trùng hoàn toàn với người thứ và thứ nên luôn bị kẹp giữa hai người bỏ phiếu cho X trong thứ tự tệ nhất. |
| 5 5 7 0 3 4 0 5 7 0 5 7 1 9 4 0 |
1 | Chỉ có một người bỏ phiếu cho X nên cụm chỉ gồm đúng người đó, dù có hai người khác trùng giá trị với người này. |
Bình luận