trang chủ / đề bài / icpc24_nat_c

Trò chơi bài liên tiếp

Đề bài

Mô tả

GSPVH đang tham dự một sự kiện trò chơi bài. Anh sẽ chơi trò "Những lá bài trong hộp đen". Nếu thắng, anh sẽ nhận được một giải thưởng cực lớn như một giải jackpot!

Trò chơi diễn ra như sau. Ban đầu, người dẫn chương trình đưa ra một hộp đen không có lá bài nào bên trong. Sau đó, người dẫn bỏ vào hộp n lá bài, trên mỗi lá ghi một số nguyên; các số ghi trên n lá bài là v1,v2,…,vn. Tiếp theo, người dẫn công bố một số nguyên dương k.

Bây giờ GSPVH chơi một vòng khởi động:

  • GSPVH nói với người dẫn một số nguyên dương t0.
  • Người dẫn lấy ngẫu nhiên t0 lá bài ra khỏi hộp đen.
  • Nếu trong các lá bài được lấy ra có k lá ghi k số nguyên liên tiếp thì GSPVH thắng vòng này. Nói cách khác, GSPVH thắng nếu tồn tại số nguyên x sao cho với mọi số nguyên y từ x đến x+k−1 (tính cả hai đầu), có một lá bài ghi giá trị y được lấy ra. Ngược lại GSPVH thua vòng này.
  • Nếu GSPVH thua, trò chơi kết thúc ngay và GSPVH không nhận được giải thưởng nào. Nếu GSPVH thắng, mọi lá bài đã lấy ra được bỏ lại vào hộp đen và trò chơi tiếp tục.

Nếu trò chơi vẫn tiếp tục, GSPVH sẽ chơi thêm q vòng liên tiếp, đánh số từ 1 đến q. Vòng thứ i diễn ra như sau:

  • Người dẫn công bố ba số nguyên li, ri và ci.
  • Với mỗi số nguyên j từ li đến ri (tính cả hai đầu), người dẫn lấy ra khỏi hộp đen tất cả các lá bài ghi giá trị j và đốt chúng đi vĩnh viễn, rồi bỏ vào hộp đen đúng ci lá bài mới ghi giá trị j. Nói cách khác, sau bước này, với mỗi số nguyên j từ li đến ri có đúng ci lá bài ghi giá trị j.
  • GSPVH nói với người dẫn một số nguyên dương ti.
  • Người dẫn lấy ngẫu nhiên ti lá bài ra khỏi hộp đen.
  • Nếu trong các lá bài được lấy ra có k lá ghi k số nguyên liên tiếp thì GSPVH thắng vòng này. Ngược lại GSPVH thua vòng này.
  • Nếu GSPVH thua, trò chơi kết thúc ngay và GSPVH không nhận được giải thưởng nào. Nếu GSPVH thắng, mọi lá bài đã lấy ra được bỏ lại vào hộp đen và trò chơi tiếp tục.

GSPVH chỉ nhận được giải thưởng nếu thắng tất cả q vòng này. Lưu ý rằng:

  • Ở mỗi vòng, số GSPVH nói ra phải nhỏ hơn hoặc bằng số lá bài đang có trong hộp đen.
  • Ở mỗi vòng, GSPVH quyết định số lá bài được lấy ra nhưng không thể điều khiển chính xác những lá bài nào được lấy ra.
  • Giá trị k không đổi trong suốt trò chơi.
  • Ở mỗi vòng, nếu GSPVH thắng, mọi lá bài được lấy ra đều được bỏ lại vào hộp đen trước vòng tiếp theo. Do đó, ở mỗi vòng, tập các lá bài trong hộp đen không phụ thuộc vào việc những lá bài nào đã được lấy ra ở các vòng trước.

Vì giải thưởng rất lớn, GSPVH muốn chắc chắn thắng. Cụ thể, ở mỗi vòng, GSPVH muốn chọn số lá bài được lấy ra sao cho dù người dẫn lấy ra những lá nào thì GSPVH cũng chắc chắn thắng. Đồng thời, GSPVH muốn số mình nói ra nhỏ nhất có thể.

Hãy giúp GSPVH xác định, ở mỗi vòng, số lá bài nhỏ nhất cần lấy ra để GSPVH chắc chắn nhận được giải thưởng!

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên n, k và q (1≤n≤106, 1≤q≤105, 1≤k≤5).
  • Dòng thứ hai chứa n số nguyên v1,v2,…,vn (−109≤vi≤109).
  • Dòng thứ i trong q dòng cuối chứa ba số nguyên li, ri và ci (−109≤li≤ri≤109, 1≤ci≤109).

Dữ liệu đảm bảo ở mọi vòng, trước khi GSPVH nói ra một số, hộp đen có chứa các lá bài ghi k số nguyên liên tiếp.

Dữ liệu ra

In ra q+1 số nguyên, lần lượt là số lá bài nhỏ nhất cần lấy ra để chắc chắn thắng ở vòng khởi động và ở q vòng tiếp theo. Mỗi số in trên một dòng.

Ràng buộc

  • 1≤n≤106, 1≤q≤105, 1≤k≤5
  • −109≤vi≤109
  • −109≤li≤ri≤109, 1≤ci≤109

Ví dụ

Input Output Giải thích
4 2 2
1 2 4 5
8 8 1
6 7 1
3
4
5
Vòng khởi động: hộp có 4 lá 1,2,4,5; lấy 3 lá thì chắc chắn có cả 1 và 2 hoặc cả 4 và 5. Vòng 1: hộp có 1,2,4,5,8, cần 4 lá. Vòng 2: hộp có 1,2,4,5,6,7,8; 4 lá chưa đủ vì có thể lấy ra 1,4,6,8, còn 5 lá thì chắc chắn thắng.
8 3 3
1 2 3 3 5 6 6 6
4 4 2
10 12 1000000000
-1000000000 1000000000 1
8
9
2000000009
1333333335
Vòng khởi động: có thể lấy 7 lá 2,3,3,5,6,6,6 mà không có ba giá trị liên tiếp. Vòng 3: mọi giá trị từ −109 đến 109 có đúng một lá.

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