Bạn sở hữu một cửa hàng kẹo mút. Đầu ngày, bạn làm \(N\) cây kẹo, mỗi cây có một hương vị riêng biệt, chẳng hạn việt quất, anh đào hoặc chanh. Trong ngày có \(N\) khách lần lượt vào cửa hàng. Mỗi khách đưa danh sách những vị họ thích. Bạn có thể bán cho họ một cây thuộc bất kỳ vị nào trong danh sách, miễn là cây vị đó chưa được bán cho người trước, vì mỗi vị chỉ có một cây. Nếu mọi vị họ thích đều đã hết, bạn không thể bán và họ thất vọng rời đi.

Bạn chỉ biết sở thích của khách khi họ tới. Mỗi khách thích hay không thích từng vị một cách ngẫu nhiên, độc lập với việc họ thích vị khác và với sở thích của mọi người khác. Tuy nhiên, nghiên cứu thị trường cho thấy xác suất được thích của các vị có thể khác nhau: chẳng hạn một khách bất kỳ có thể thích chanh với xác suất 10%, nhưng thích anh đào với xác suất 1%. Xác suất của mỗi vị được chọn độc lập và đều trên đoạn \([0.005,0.1]\).

Bạn muốn bán cho càng nhiều khách càng tốt. Vì không biết trước sở thích tương lai, bạn không phải lúc nào cũng quyết định tối ưu: có thể bán một vị cho khách hiện tại rồi về sau ước rằng mình đã bán vị khác.

Giả sử biết trước sở thích của tất cả khách và có thể lập kế hoạch, gọi \(M\) là số kẹo lớn nhất có thể bán. Dù không được biết trước, chương trình của bạn phải bán ít nhất 90% của \(M\) trong mỗi bộ test.

Dữ liệu vào

Đây là bài tương tác: khái niệm input và output khác bài thông thường. Chương trình tương tác với một tiến trình riêng vừa cung cấp thông tin vừa đánh giá câu trả lời. Mọi thông tin đi vào qua đầu vào chuẩn; mọi nội dung cần giao tiếp phải gửi qua đầu ra chuẩn.

Nhiều ngôn ngữ mặc định đệm output, vì vậy phải bảo đảm dữ liệu thực sự được gửi đi — chẳng hạn flush bộ đệm — trước khi chặn để chờ phản hồi. Mọi thứ ghi ra lỗi chuẩn bị bỏ qua, nhưng vẫn có thể tiêu tốn bộ nhớ, nên không được ghi tràn lan.

Dữ liệu ra

Mọi lựa chọn bán kẹo được gửi tới judge qua đầu ra chuẩn theo giao thức dưới đây. Mỗi câu trả lời phải được flush trước khi chương trình chờ dữ liệu tiếp theo.

Giao thức tương tác

Ban đầu đọc một dòng chứa số nguyên \(T\), số bộ test, rồi xử lý lần lượt \(T\) bộ.

Ở đầu mỗi bộ test, đọc một dòng chứa \(N\), vừa là số cây kẹo vừa là số khách. Với từng khách, đọc một dòng các số nguyên cách nhau bằng dấu cách. Số đầu tiên là \(D\), số vị khách đó thích; tiếp theo là \(D\) ID vị theo thứ tự tăng nghiêm ngặt. ID vị nằm trong \([0,N-1]\) và là duy nhất. \(D\) có thể bằng 0 đối với một số hoặc tất cả khách.

Ngay sau mỗi dòng đó, phải ghi một dòng chứa ID của một trong \(D\) vị sẽ bán cho khách, hoặc -1 nếu không bán. Sau khi ghi dòng thứ \(N\) của bộ test, nếu đó là bộ cuối thì kết thúc; nếu không thì bắt đầu đọc bộ tiếp theo.

Nếu chương trình làm sai — chẳng hạn bán lại một vị đã bán, bán vị khách không thích, dùng sai định dạng hoặc in giá trị ngoài miền — judge gửi -1 vào input và không gửi gì thêm. Nếu chương trình vẫn chờ judge sau khi nhận -1, nó sẽ hết thời gian. Chương trình có trách nhiệm thoát kịp thời để nhận kết quả phù hợp thay vì TLE. Không bán đủ kẹo trong một bộ test không khiến judge gửi -1.

Không gửi thêm thông tin sau khi xử lý xong tất cả bộ test; nếu tiếp tục in sau bộ cuối, kết quả là Wrong Answer.

Hành vi của judge

Ở đầu mỗi bộ test, judge xác định toàn bộ sở thích khách hàng bằng một danh sách ẩn các xác suất \(P_i\in[0.005,0.1]\), mỗi vị một xác suất. Mỗi khách thích vị \(i\) với xác suất \(P_i\); với một \(i\) cố định, các biến ngẫu nhiên cho biết khách \(j\) có thích vị \(i\) hay không là độc lập và cùng phân phối. Toàn bộ sở thích được cố định trong suốt bộ test và không bị sửa để phản ứng với lựa chọn của chương trình.

Ràng buộc

• \(0\le D\le N\).

Phân nhóm

• Test Set 1 (Hiển thị): \(T=50\), \(N=200\), \(0\le D\le N\).

Ví dụ

Các giá trị \(T,N\) trong ví dụ nhỏ hơn dữ liệu thật; công cụ kiểm thử cục bộ cũng dùng các trường hợp nhỏ hơn.

  t = readline_int()           // reads 10 into t
  n = readline_int()           // reads 4 into n (four customers & flavors)
  prefs = readline_int_list()  // reads 1 2 (customer only likes flavor 2)
  printline 2 to stdout        // sells this customer flavor 2
  flush stdout
  prefs = readline_int_list()  // reads 0 (customer likes nothing)
  printline -1 to stdout       // no flavor to sell to the customer!
  flush stdout
  prefs = readline_int_list()  // reads 1 2 (customer only likes flavor 2)
  printline -1 to stdout       // already used flavor 2, so no flavor to sell
  flush stdout
  prefs = readline_int_list()  // reads 2 1 3 (customer likes 1 and 3)
  printline 3 to stdout        // note: we could have also sold flavor 1
  flush stdout
  n = readline_int()           // (start of case 2) reads 1
  prefs = readline_int_list()  // reads 1 0
  printline -1 to stdout       // non-optimal but legal choice
  flush stdout
  n = readline_int()           // (start of case 3) reads 5
  prefs = readline_int_list()  // reads 2 1 3
  printline 1 to stdout
  flush stdout
  prefs = readline_int_list()  // reads 2 1 2
  printline 1 to stdout        // error -- tried to give same flavor twice!
  flush stdout
  prefs = readline_int_list()  // reads -1 (judge has given up on us)
  exit                         // exits to avoid an ambiguous TLE error

Công cụ kiểm thử

Có thể dùng công cụ kiểm thử cục bộ chính thức trên máy hoặc nền tảng. Khi chạy cục bộ, cần chạy công cụ song song với chương trình, có thể dùng interactive runner. Hướng dẫn nằm trong phần chú thích của tệp; bạn được khuyến khích bổ sung test riêng.

Nguồn

Google Code Jam 2018, Vòng 1C, bài Lollipop Shop.

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