Tòa nhà có các tầng \(0,\ldots,N\) và một sân thượng phía trên tầng \(N\). Mỗi tầng \(f\) có một cư dân chỉ biết giá trị bí mật \(v_f\in[0,3]\). Karlsson ở sân thượng muốn khôi phục càng nhiều giá trị càng tốt.

Thang máy bắt đầu ở tầng \(0\) và chỉ đi lên. Ban đầu chưa có nút nào được nhấn; nút đã nhấn sẽ giữ nguyên. Thang dừng ở tầng \(0\) và ở mỗi tầng có nút được nhấn từ một điểm dừng trước đó. Tại tầng \(f\), cư dân thấy toàn bộ tập nút hiện tại và có thể nhấn một tập các nút chưa nhấn có số tầng lớn hơn \(f\). Sau tầng được nhấn cao nhất, thang đi thẳng lên sân thượng.

Karlsson chỉ thấy tập nút cuối cùng. Các tiến trình không được trao đổi bằng bất kỳ cách nào khác.

Giao diện thư viện

Submission C++ phải include elevator.h và cài đặt:

std::vector<int> press_buttons(
    int subtask, int N, int f, int v, std::vector<int> p);
std::vector<int> answer(
    int subtask, int N, std::vector<int> p);

press_buttons chỉ được gọi ở tầng thang mở cửa. Vector p chứa các nút đã nhấn theo thứ tự tăng; kết quả phải gồm các nút mới, đôi một khác nhau, chưa thuộc p, và thỏa \(f<x\le N\).

answer được gọi đúng một lần cho mỗi kịch bản khi thang tới sân thượng. Vector trả về phải có \(N+1\) phần tử: giá trị đã khôi phục ở vị trí tương ứng hoặc -1 nếu chưa biết.

Đây là bài giao tiếp. Chương trình chạy thành \(N+2\) tiến trình độc lập: một tiến trình cho mỗi tầng và một cho sân thượng. Không được giả sử có trạng thái toàn cục dùng chung. Các kịch bản có thể được xử lý theo thứ tự khác nhau ở mỗi tiến trình.

Dữ liệu vào

Submission không đọc standard input. Manager đọc tối đa \(T\) kịch bản và chuyển dữ liệu qua giao diện.

Dữ liệu ra

Submission không ghi standard output. Các nút mới và đáp án được trả từ hai hàm.

Ràng buộc

• \(N=60\), \(T\le10000\).
• \(0\le v_f\le3\).
• Mỗi tiến trình có giới hạn bộ nhớ \(64\) MiB; toàn bộ lời gọi phải hoàn thành trong \(10\) giây.

Phân nhóm

1. \(15\) điểm: \(0\le v_i\le1\), \(v_0=v_N=1\), và \(v_i=0\) kéo theo \(v_{i+1}=1\). Cần khôi phục \(60\) giá trị để đủ điểm.
2. \(35\) điểm: \(0\le v_i\le1\). Cần khôi phục \(40\) giá trị để đủ điểm.
3. \(15\) điểm: \(0\le v_i\le2\). Cần khôi phục \(30\) giá trị để đủ điểm.
4. \(35\) điểm: \(0\le v_i\le3\). Cần khôi phục \(25\) giá trị để đủ điểm.

Nếu có một giá trị khôi phục sai hoặc thao tác không hợp lệ, phân nhóm nhận \(0\). Gọi \(K\) là số giá trị khôi phục nhỏ nhất trên mọi kịch bản. Điểm lần lượt là: nhóm 1, \(\min(0.25K,15)\); nhóm 2, \(0.5K\) khi \(K<30\), \(2K-45\) khi \(30\le K<40\), và \(35\) khi \(K\ge40\); nhóm 3, \(\min(0.5K,15)\); nhóm 4, \(0.7K\) khi \(K<20\), \(4K-66\) khi \(20\le K<25\), và \(35\) khi \(K\ge25\).

Ví dụ

Trong ví dụ chính thức, thang dừng ở tầng \(0\), rồi các tầng \(2\), \(13\), \(42\); tập nút cuối là {2,13,42}. Karlsson trả đúng \(v_0=1\), \(v_2=0\) và -1 ở các vị trí chưa khôi phục.

Nguồn

EJOI 2026 - Ngày 2, Elevator.

Đề bài EJOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).