Pen Testing

Đề bài

Bạn có \(N\) chiếc bút bi. Mỗi chiếc có một lượng mực nguyên phân biệt từ \(0\) đến \(N-1\), nhưng các bút được đưa theo thứ tự ngẫu nhiên nên bạn không biết chiếc nào ứng với lượng nào.

Bạn sắp đi Nam Cực (nơi không có bút), hành lý chỉ đủ chỗ cho hai chiếc, và bạn sẽ phải viết rất nhiều bưu thiếp quan trọng. Cụ thể, tổng lượng mực của hai bút được chọn phải ít nhất là \(N\) đơn vị.

Cách duy nhất để thu thập thông tin là chọn một bút và thử viết. Nếu thành công, bút mất một đơn vị mực (và có thể vừa cạn); nếu thất bại, bút vốn đã hết mực. Bạn có thể lặp lại nhiều lần với cùng bút hoặc các bút khác nhau.

Cuối cùng, bạn phải chọn hai bút mang theo và thành công nếu tổng lượng mực còn lại của chúng ít nhất là \(N\).

Bạn nhận \(T\) trường hợp kiểm thử và phải thành công trong ít nhất \(C\) trường hợp. Mọi bộ kiểm thử của bài đều có kết quả chấm hiển thị.

Dữ liệu vào

Nội dung vào được cung cấp theo giao thức mô tả dưới đây.

Dữ liệu ra

Đây là bài tương tác. Hãy chắc chắn bạn đã đọc mục Bài toán tương tác trong FAQ.

Ban đầu, đọc một dòng gồm \(T\), \(N\), \(C\): số trường hợp, số bút và số trường hợp tối thiểu phải thành công. (\(N\) giống nhau ở mọi bộ kiểm thử và chỉ được nhập để tiện sử dụng; xem mục Giới hạn.)

Sau đó phải xử lý đồng thời cả \(T\) trường hợp để giảm số lượt trao đổi với bộ chấm. Tương tác được chia thành các vòng.

Đầu mỗi vòng, in một dòng gồm \(T\) số: số thứ \(i\) là số hiệu bút muốn thử trong trường hợp \(i\), hoặc \(0\) nếu không thử bút nào ở trường hợp đó trong vòng này. Bút được đánh số từ \(1\) đến \(N\).

Xả bộ đệm sau từng số thay vì một lần sau cả \(T\) số có thể gây Quá thời gian vì chính chi phí xả bộ đệm.

Bộ chấm trả một dòng gồm \(T\) số: số thứ \(i\) là lượng mực tiêu hao ở trường hợp \(i\) trong vòng này. Nó bằng \(1\) nếu viết thành công; nếu không thì bằng \(0\), có thể vì bút đã hết mực hoặc vì bạn không thử viết.

Bạn được thực hiện nhiều nhất \(N\times(N+1)/2\) vòng; số này đủ để chắc chắn làm cạn mọi bút.

Khi sẵn sàng trả lời tất cả trường hợp, in một dòng có số \(0\) lặp \(T\) lần. Dòng này không tính vào giới hạn vòng và bộ chấm không phản hồi.

Sau đó in một dòng gồm \(2\times T\) số: số thứ \((2\times i-1)\) và \((2\times i)\) là số hiệu phân biệt của hai bút mang đi trong trường hợp \(i\). Bộ chấm không phản hồi; chương trình phải kết thúc không lỗi.

Nếu nhận đầu ra bất ngờ, bộ chấm in duy nhất \(-1\) rồi ngừng. Nếu vẫn chờ sau khi nhận \(-1\), chương trình sẽ Quá thời gian; bạn phải kết thúc kịp để nhận Sai. Vượt bộ nhớ hoặc lỗi khi chạy sẽ nhận kết quả tương ứng.

Thứ tự bút được chọn ngẫu nhiên đều và độc lập cho từng trường hợp và từng lần nộp. Ngay cả khi nộp cùng một mã hai lần, bộ chấm vẫn dùng các thứ tự khác nhau.

Ràng buộc

\(N=15\).

Phân nhóm

Bộ kiểm thử 1 (Kết quả hiển thị)

\(T=20000\).
\(C=10900\) (\(C=0.545\times T\)).

Bộ kiểm thử 2 (Kết quả hiển thị)

\(T=20000\).
\(C=12000\) (\(C=0.6\times T\)).

Bộ kiểm thử 3 (Kết quả hiển thị)

\(T=100000\).
\(C=63600\) (\(C=0.636\times T\)).

Giao thức tương tác

Chương trình phải tuân thủ đầy đủ thứ tự đọc, ghi, phản hồi lỗi và yêu cầu flush được mô tả trong phần dữ liệu vào/ra và công cụ kiểm thử bên dưới.

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử cục bộ hoặc trên nền tảng. Để kiểm tra cục bộ, chạy công cụ song song với mã bằng trình chạy tương tác. Xem hướng dẫn trong chú thích của tệp và mục Bài toán tương tác trong FAQ.

Hướng dẫn nằm trong chú thích của công cụ. Bạn nên tự thêm trường hợp kiểm thử. Dù mô phỏng hệ thống chấm, công cụ KHÔNG phải bộ chấm thật và có thể hành xử khác. Nếu qua công cụ nhưng trượt bộ chấm thật, hãy xem mục Lập trình trong FAQ để bảo đảm dùng cùng trình biên dịch.

Tải công cụ kiểm thử

Ví dụ

Tương tác sau không thuộc ba bộ kiểm thử vì \(T,N\) quá nhỏ; nó chỉ minh họa giao thức.

2 5 11 00 10 1

4 54 30 20 03 4 3 4

  // Đọc 2 vào t, 5 vào n và 1 vào c.
  t, n, c = readline_int_list()
  // Bộ chấm bí mật chọn lượng mực của từng bút:
  // trường hợp 1: 2 0 4 1 3
  // trường hợp 2: 1 3 2 4 0
  // Viết bằng bút 4 ở trường hợp 1 và bút 5 ở trường hợp 2.
  printline 4 5 to stdout
  flush stdout
  // Đọc 1 0: bút 4 ở trường hợp 1 còn mực, bút 5 ở trường hợp 2 thì không.
  a1, a2 = readline_int_list()
  // Lại viết bằng bút 4 ở trường hợp 1 và bút 3 ở trường hợp 2.
  printline 4 3 to stdout
  flush stdout
  // Đọc 0 1.
  a1, a2 = readline_int_list()
  // Lần này chỉ viết ở trường hợp 2, bằng bút 2.
  printline 0 2 to stdout
  flush stdout
  // Đọc 0 1.
  a1, a2 = readline_int_list()
  // Quyết định đã sẵn sàng trả lời.
  printline 0 0 to stdout
  flush stdout
  // Mang bút 3 và 4 đi trong cả hai trường hợp.
  printline 3 4 3 4 to stdout
  flush stdout
  // Trường hợp 1: hai bút còn 4 và 0; 4+0<5 nên thất bại.
  // Trường hợp 2: hai bút còn 1 và 4; 1+4≥5 nên thành công.
  // Thành công 1/2 trường hợp, đủ vì c=1.
  exit

Nguồn

Google Code Jam 2020, Vòng 3, bài Pen Testing.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.