trang chủ / đề bài / icpc19_reg_i

Kiểm tra chiếu sáng

Đề bài

Mô tả

Đây là bài toán tương tác.

Dinh thự nhà Zoldyck vô cùng rộng lớn, với hàng chục căn phòng và hàng trăm nguồn sáng: bóng đèn, đèn chùm, đèn bàn, ...

Bạn vừa được nhà Zoldyck thuê làm quản gia. Công việc hằng ngày của bạn là ngồi trong phòng điều khiển chiếu sáng và điều khiển mọi nguồn sáng trong dinh thự.

Trong phòng điều khiển có n công tắc. Mỗi công tắc điều khiển đúng một nguồn sáng. Các công tắc và các nguồn sáng được đánh số từ 1 đến n. Tuy nhiên không có tài liệu nào, nên bạn không biết công tắc nào điều khiển nguồn sáng nào.

Vì vậy, cách duy nhất là lặp lại thao tác sau:

  • Bật/tắt (đảo trạng thái) một số công tắc (ít nhất một).
  • Đi một vòng quanh dinh thự, kiểm tra trạng thái của cả n nguồn sáng.

Vì dinh thự quá rộng, bạn muốn đi vòng quanh nó không quá 32 lần.

Tương tác

Đầu tiên, chương trình của bạn đọc số nguyên n (1≤n≤1000).

Sau đó quá trình sau lặp lại:

  • Chương trình của bạn in ra một trong hai dạng:
    • ASK k a1 a2 … ak (1≤k≤n, 1≤ai≤n, các ai đôi một khác nhau): bạn đảo trạng thái k công tắc a1,a2,…,ak và muốn biết k nguồn sáng nào bị đảo trạng thái.
    • ANSWER b1 b2 … bn (1≤bi≤n): bạn trả lời rằng nguồn sáng i được điều khiển bởi công tắc bi.
  • Nếu chương trình hỏi (ASK), trình chấm in ra k số nguyên trên một dòng là các nguồn sáng bị đảo trạng thái, theo thứ tự bất kỳ. Chương trình cần đọc chúng.
  • Nếu chương trình in câu trả lời (ANSWER), chương trình phải kết thúc ngay sau đó. Bạn chỉ được in câu trả lời đúng một lần.

Lưu ý bạn được tương tác tối đa 32+1=33 lần: 32 lần hỏi và 1 lần trả lời.

Sau mỗi lần in, đừng quên xuống dòng và flush đầu ra: dùng fflush(stdout) hoặc cout.flush() trong C++, sys.stdout.flush() trong Python.

Ràng buộc

  • 1≤n≤1000.
  • Số lần ASK không vượt quá 32.

Ví dụ

Input Output Giải thích
5
2 3
2 4
5
ASK 2 2 4
ASK 2 3 4
ASK 1 5
ANSWER 1 4 2 3 5
Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra. Công tắc 1,2,3,4,5 lần lượt điều khiển nguồn sáng 1,3,4,2,5. Đảo công tắc 2,4 làm đảo nguồn sáng 3,2 (trình chấm có thể in theo thứ tự bất kỳ); đảo công tắc 3,4 làm đảo nguồn sáng 4,2; đảo công tắc 5 làm đảo nguồn sáng 5. Đề gốc minh họa cùng cách nối này bằng 5 câu hỏi ASK 1 1, ASK 2 1 2, ASK 3 1 2 3, ASK 4 1 2 3 4, ASK 5 1 2 3 4 5 (nhận được 1; 1 3; 1 3 4; 1 2 3 4; 1 2 3 4 5) rồi in ANSWER 1 4 2 3 5.
1 ANSWER 1 Ví dụ bổ sung (không có trong đề gốc). Chỉ có một công tắc và một nguồn sáng nên trả lời ngay, không cần hỏi.

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