trang chủ / đề bài / icpc24_mt_b

Câu đố về bộ bốn phép thuật

Đề bài

Mô tả

Quỳnh Anh là một lập trình viên trẻ thích phiêu lưu và rất mê giải các câu đố về số. Một ngày nọ, khi lang thang trong khu rừng số mang tên ESC21, cô tình cờ tìm thấy một cuộn giấy phép thuật mô tả một câu đố kỳ lạ về mảng và các phép toán trên bit. Câu đố hấp dẫn đến mức cô quyết định tự mình thử sức và rủ bạn bè cùng giải.

Câu đố như sau.

Quỳnh Anh có N số nguyên không âm, biểu diễn bởi mảng A với các phần tử A[1],A[2],…,A[N]. Cô định nghĩa một bộ bốn siêu đẹp là một bộ bốn chỉ số (i,j,p,q) thỏa mãn:

  • 1≤i,j,p,q≤N (các chỉ số không nhất thiết phân biệt);
  • A[i]&A[j]&A[p]&A[q]=0, trong đó & là phép AND theo bit.

Nói cách khác, phép AND theo bit của bốn phần tử ở bốn chỉ số được chọn phải bằng 0.

Chưa hết! Quỳnh Anh muốn duyệt các bộ bốn này theo một thứ tự cụ thể: thứ tự từ điển. Bộ bốn (b1,b2,b3,b4) được coi là nhỏ hơn bộ bốn (c1,c2,c3,c4) nếu tồn tại chỉ số t (1≤t≤4) sao cho b1=c1,…,bt−1=ct−1 và bt<ct.

Hãy giúp Quỳnh Anh tìm bộ bốn siêu đẹp thứ k theo thứ tự từ điển (tính từ nhỏ đến lớn) trong số tất cả các bộ bốn siêu đẹp.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên N và k (1≤N≤5000, 1≤k≤N4).
  • Dòng thứ hai chứa N số nguyên A[1],A[2],…,A[N] (0≤A[x]≤106 với mọi 1≤x≤N).

Dữ liệu ra

In ra bốn số nguyên i, j, p, q: bộ bốn siêu đẹp thứ k theo thứ tự từ điển. Nếu k lớn hơn tổng số bộ bốn siêu đẹp, in ra −1.

Ràng buộc

  • 1≤N≤5000
  • 1≤k≤N4
  • 0≤A[x]≤106

Ví dụ

Input Output Giải thích
6 1
1 4 7 10 13 16
1 1 1 2 1&1&1&4=0; bộ (1,1,1,1) không thỏa vì A[1]=1.
6 2
1 4 7 10 13 16
1 1 1 4
6 1120
1 4 7 10 13 16
6 6 6 5
6 1121
1 4 7 10 13 16
-1 Chỉ có 1120 bộ bốn siêu đẹp.

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