trang chủ / đề bài / icpcwf16_j

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 n người. Bạn thu được ba thông tin từ mỗi người, với người thứ i được ghi lại như sau:

  • ai: số chữ số của π mà người đó thuộc lòng;
  • bi: số sợi tóc trên đầu người đó;
  • ci: 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 a, b và c 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 S và T, rồi sắp xếp các kết quả thăm dò (ai,bi,ci) theo đại lượng ai·S+bi·T. Phép sắp xếp trông đẹp nhất nếu các kết quả có ci đúng tụ lại gần nhau nhất có thể. Chính xác hơn, nếu j và k 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ó ci đúng, bạn muốn cực tiểu hóa kích thước cụm, tức là k−j+1. Lưu ý rằng với một số cách chọn S và T, các bộ (ai,bi,ci) 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 (S,T) đó).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n, số người được thăm dò.

Mỗi dòng trong n dòng tiếp theo mô tả một người, gồm ba số nguyên ai, bi và ci, trong đó ci=1 nếu người đó bỏ phiếu cho Ứng viên X và ci=0 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 (S,T).

Ràng buộc

  • 1≤n≤250000.
  • 0≤ai,bi≤2000000, ci∈{0,1}.
  • 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 S=140, T=40, các đại lượng là 400,1400,2000,900,1620,1660. Thứ tự sắp xếp là 400,900,1400,1620,1660,2000; người đầu tiên bỏ phiếu cho X có đại lượng 1400 (vị trí 3), người cuối cùng có đại lượng 2000 (vị trí 6), kích thước cụm 6−3+1=4.
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ụ, S=−16, T=4 đạt kích thước cụm 8. Người thứ 9 trùng hoàn toàn với người thứ 1 và thứ 4 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

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