EJOI 2026 - Ngày 2

Có \(N\) ô liên tiếp, đánh số \(0,\ldots,N-1\), với độ cao \(p_i\) tạo thành một hoán vị của \(0,\ldots,N-1\). Hai ô là gần nhau khi khoảng cách chỉ số không quá \(1\).

Robot nhận hai loại lệnh. MAX chuyển robot đến ô cao nhất trong các ô gần vị trí hiện tại; MIN chuyển đến ô thấp nhất. Ô hiện tại cũng được xét nên robot có thể đứng yên.

Mỗi truy vấn cho một tập vị trí bắt đầu. Hãy xác định có tồn tại một chuỗi hữu hạn các lệnh MIN/MAX đưa robot đến cùng một ô cuối, bất kể vị trí bắt đầu được chọn trong tập hay không. Không cần dựng chuỗi lệnh.

Giao diện thư viện

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

void initialize(std::vector<int> p);
bool exists_program(std::vector<int> x);

initialize được gọi đúng một lần. Sau đó exists_program được gọi \(Q\) lần; x chứa các chỉ số theo thứ tự tăng nghiêm ngặt.

Dữ liệu vào

Submission không đọc standard input. Sample grader đọc \(N,Q\), hoán vị \(p\), rồi từng truy vấn.

Dữ liệu ra

Submission không ghi standard output. Mỗi đáp án được trả từ exists_program.

Ràng buộc

• \(3\le N\le2\cdot10^5\).
• \(1\le Q\le5\cdot10^5\).
• \(p\) là hoán vị của \(0,\ldots,N-1\).
• \(2\le K_i\le N\) và \(0\le x_0<\cdots<x_{K_i-1}<N\).
• Tổng \(K_i\) trên mọi truy vấn không quá \(10^6\).

Phân nhóm

1. \(3\) điểm: \(K_i=2\); nếu đáp án dương thì tồn tại chương trình đúng một lệnh.
2. \(7\) điểm: \(K_i=2\); nếu đáp án dương thì tồn tại chương trình không quá năm lệnh.
3. \(9\) điểm: \(N\le100\), \(Q\le500\), \(K_i=2\).
4. \(17\) điểm: \(N\le5000\), \(K_i=2\).
5. \(7\) điểm: \(K_i=2\) và \(x_1=x_0+1\).
6. \(8\) điểm: \(N\le5000\).
7. \(13\) điểm: tồn tại \(0<a<b<N-1\) sao cho \(p_0<\cdots<p_a>p_{a+1}>\cdots>p_b<p_{b+1}<\cdots<p_{N-1}\).
8. \(13\) điểm: độ cao xen kẽ \(p_0<p_1>p_2<\cdots\); dấu cuối là < nếu \(N\) chẵn và > nếu \(N\) lẻ.
9. \(23\) điểm: không có ràng buộc thêm.

Ví dụ

3 3
0 2 1
2 0 2
3 0 1 2
2 1 2

111

7 3
0 4 2 1 3 5 6
3 0 1 3
3 1 3 4
2 3 6

001

Nguồn

EJOI 2026 - Ngày 2, Automata.

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

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).

Có \(N\) địa điểm tạo thành một cây. Địa điểm \(i\) thuộc đội \(a_i\in[0,K-1]\); một đội có thể chiếm nhiều địa điểm hoặc không có địa điểm nào.

Một đường đi đơn được gọi là thú vị nếu có độ dài lớn nhất trong mọi đường đi đơn của cây, tức là một đường kính. Độ đa dạng đội của đường đi là số đội phân biệt xuất hiện trên đó.

Hãy tính tổng độ đa dạng đội trên mọi đường đi thú vị khác nhau. Hai đường đi được xem là giống nhau khi chúng đi qua cùng tập đỉnh, nên hai hướng đi không tạo hai đường khác nhau.

Giao diện thư viện

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

long long teamfulness(
    int N, int K,
    std::vector<int> a,
    std::vector<int> u,
    std::vector<int> v);

Hai vector u,v có \(N-1\) phần tử và cạnh thứ \(i\) nối u[i] với v[i]. Hàm được gọi đúng một lần.

Dữ liệu vào

Submission không đọc standard input. Sample grader đọc \(N,K\), dãy đội và \(N-1\) cạnh.

Dữ liệu ra

Submission không ghi standard output. Kết quả được trả từ teamfulness.

Ràng buộc

• \(3\le N\le10^6\).
• \(1\le K\le N\).
• \(0\le a_i<K\).
• \(0\le u_i,v_i<N\).
• Các cạnh tạo thành một cây.

Phân nhóm

1. \(4\) điểm: bậc mỗi đỉnh không quá \(2\).
2. \(7\) điểm: có một đỉnh kề trực tiếp với mọi đỉnh còn lại.
3. \(9\) điểm: \(N\le200\).
4. \(10\) điểm: \(N\le2000\).
5. \(10\) điểm: \(K=1\).
6. \(9\) điểm: \(K\le2\).
7. \(11\) điểm: \(N\le2\cdot10^5\), \(K\le50\).
8. \(12\) điểm: \(N\le2\cdot10^5\).
9. \(13\) điểm: độ dài đường đi thú vị là số lẻ.
10. \(15\) điểm: không có ràng buộc thêm.

Ví dụ

6 3
1 0 0 1 2 1
0 1
0 2
0 3
0 4
0 5

21

7 1
0 0 0 0 0 0 0
0 1
0 2
1 3
1 4
2 5
2 6

4

6 3
0 1 2 0 1 2
0 1
1 2
2 3
1 4
2 5

11

Nguồn

EJOI 2026 - Ngày 2, Teamfulness.

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