EGOI 2026 - Ngày 1

Vòng quay Ferris nổi tiếng ở quảng trường chính Cesenatico đã được tháo dỡ trong mùa đông. Mùa hè sắp đến và đã đến lúc lắp lại vòng quay.

Có \(N\) cabin riêng lẻ, đánh số từ \(0\) đến \(N-1\), cần được nối thành một vòng tròn. Số hiệu cabin không nhất thiết trùng với thứ tự lắp đặt. Mỗi cabin có một khớp nối với cabin kế tiếp theo chiều kim đồng hồ, thuộc một trong hai loại:

• +: chỉ có thể nối với cabin có số hiệu lớn hơn;
• -: chỉ có thể nối với cabin có số hiệu nhỏ hơn.

Hình 1: \(N=5\) cabin rời, mỗi cabin có một khớp loại + hoặc -.

Hãy xác định có thể lắp tất cả \(N\) cabin thành một vòng quay hay không. Nếu có, hãy tìm một thứ tự hợp lệ.

Hình 2: Một vòng quay Ferris hợp lệ được lắp từ năm cabin ở Hình 1.

Một thứ tự hợp lệ là dãy \(C_0,C_1,\ldots,C_{N-1}\) thỏa mãn:

• Mỗi số từ \(0\) đến \(N-1\) xuất hiện đúng một lần.
• Với mọi \(0\le i\le N-2\): nếu cabin \(C_i\) có loại + thì \(C_{i+1}>C_i\); nếu có loại - thì \(C_{i+1}<C_i\).
• Cabin \(C_0\) cũng phải thỏa điều kiện do loại khớp của cabin \(C_{N-1}\) đặt ra.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\).

Dòng thứ hai chứa xâu \(S\) độ dài \(N\), chỉ gồm + và -. Ký tự \(S_i\) là loại khớp của cabin \(i\).

Dữ liệu ra

Nếu không tồn tại thứ tự hợp lệ, in NO.

Nếu tồn tại, in YES, sau đó in một dòng gồm \(N\) số nguyên là các số hiệu cabin theo chiều kim đồng hồ, bắt đầu tại vị trí bất kỳ. Có thể in bất kỳ đáp án hợp lệ nào.

Ràng buộc

• \(3\le N\le300\,000\).
• \(S_i\) là + hoặc -.

Phân nhóm

1. \(16\) điểm: \(N=3\).
2. \(13\) điểm: xâu \(S\) có đúng một ký tự +.
3. \(24\) điểm: các ký tự + và - xen kẽ, tức \(S_i\ne S_{i+1}\) với mọi \(0\le i\le N-2\).
4. \(23\) điểm: \(N\le1000\).
5. \(24\) điểm: không có ràng buộc thêm.

Ví dụ

3
+++

NO

5
+-+--

YES
0 3 2 4 1

7
------+

NO

8
+-+-+-+-

YES
3 2 4 6 7 1 0 5

11
+++--+-++--

YES
10 0 5 8 9 4 2 6 3 1 7

Nguồn

EGOI 2026 - Ngày 1, Ferris Wheel.

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

Bạn là phóng viên tại sự kiện "Excellent Glutenous Ovenmasters of Italy", nơi \(N\) thợ làm pizza giỏi nhất nước Ý vừa tranh tài. Mỗi người làm một chiếc pizza. Ban giám khảo xếp hạng các pizza bằng các số phân biệt từ \(0\) (tốt nhất) đến \(N-1\) (tệ nhất); mỗi thợ nhận thứ hạng của chiếc pizza mình làm.

Sau cuộc thi, tất cả thợ mang pizza đến buổi tiệc. Họ đến lần lượt theo một thứ tự chưa biết. Có \(M\) bàn, đánh số từ \(0\) đến \(M-1\). \(M\) người đến đầu tiên đặt pizza lên lần lượt các bàn \(0,1,\ldots,M-1\).

Mỗi người đến sau muốn ăn một chiếc pizza ngon hơn pizza của mình, nhưng không ngon hơn quá mức cần thiết. Cụ thể, họ chọn pizza đang có thứ hạng lớn nhất trong số các thứ hạng vẫn nhỏ hơn thứ hạng của mình. Họ ăn hết pizza đó rồi để pizza của mình lại trên cùng bàn. Nếu không có pizza phù hợp, người đó thất vọng rời đi và mang pizza của mình theo.

Ví dụ 1 có \(M=2\) bàn và thứ tự đến là \(1,0,3,5,4,2\).

Hình 1: Hai thợ đầu tiên đặt pizza lên các bàn trống \(0\) và \(1\) theo thứ tự đến.

Hình 2: Sau khi các bàn đã có pizza, mỗi thợ chọn chiếc pizza tệ nhất nhưng vẫn ngon hơn pizza của mình; thợ rời đi nếu không có lựa chọn phù hợp.

Sau buổi tiệc, trên mỗi bàn còn một chồng khay theo đúng thứ tự các pizza đã được phục vụ tại bàn đó, từ dưới lên trên. Từ các chồng khay này, hãy khôi phục thứ tự các thợ đã đến. Nếu có nhiều thứ tự hợp lệ, để đạt trọn điểm phải in thứ tự nhỏ nhất theo thứ tự từ điển.

Hình 3: Các chồng khay của ví dụ 1, theo thứ tự từ lần đến đầu tiên ở dưới lên lần gần nhất ở trên; khay tô nổi chứa pizza còn lại cuối buổi tiệc.

Dãy \(a\) nhỏ hơn dãy \(b\) theo thứ tự từ điển nếu tồn tại vị trí \(t\) sao cho \(a_i=b_i\) với mọi \(i<t\) và \(a_t<b_t\).

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N,M\).

\(M\) dòng tiếp theo mô tả các chồng khay. Dòng \(i\) bắt đầu bằng \(T_i\), sau đó là \(T_i\) số \(b_{i,0},b_{i,1},\ldots,b_{i,T_i-1}\), là thứ hạng các pizza đã được phục vụ tại bàn \(i\), theo thứ tự từ khay dưới cùng (đến trước) lên khay trên cùng (đến sau).

Dữ liệu ra

In NO nếu không có thứ tự nào phù hợp.

Nếu có, in YES, rồi in một dòng gồm hoán vị \(a_0,a_1,\ldots,a_{N-1}\) của các thứ hạng theo thứ tự đến. Nếu có nhiều đáp án, hãy in đáp án nhỏ nhất theo thứ tự từ điển. Các đáp án đúng một phần vẫn có thể nhận điểm như mô tả dưới đây.

Ràng buộc

• \(1\le M\le N\le300\,000\).
• \(0\le b_{i,j}\le N-1\).
• Tất cả \(b_{i,j}\) đôi một khác nhau.
• \(1\le T_i\le N\).

Cách chấm điểm đầu ra

• Chỉ in đúng dòng đầu YES/NO: nhận \(20\%\) số điểm của test.
• In đúng dòng đầu và một thứ tự hợp lệ khi đáp án là YES, nhưng chưa chắc nhỏ nhất theo thứ tự từ điển: nhận thêm \(20\%\).
• Để nhận \(60\%\) còn lại, khi đáp án là YES phải in đúng thứ tự hợp lệ nhỏ nhất theo thứ tự từ điển.

Phân nhóm

1. \(20\) điểm: \(M=1\).
2. \(10\) điểm: \(M=2\), \(N\le200\) và \(\sum T_i=N\).
3. \(20\) điểm: \(M\le N\le200\) và \(\sum T_i=N\).
4. \(20\) điểm: \(M\le10\).
5. \(30\) điểm: không có ràng buộc thêm.

Ví dụ

6 2
3 1 3 5
2 0 4

YES
1 0 3 5 4 2

6 2
3 1 3 4
2 0 2

NO

4 2
2 0 3
2 1 2

NO

3 1
2 0 2

YES
0 2 1

8 1
8 7 6 5 4 3 2 1 0

NO

12 4
3 2 3 4
1 5
1 6
5 7 8 9 10 11

YES
2 5 6 7 0 1 3 4 8 9 10 11

Nguồn

EGOI 2026 - Ngày 1, Ovenmasters.

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

Aurora và Bianca rất thích bánh amaretti. Ông của họ vừa nướng một chồng bánh lớn. Hai người chia bánh bằng trò chơi sau. Khi chồng bánh vẫn còn bánh, họ lặp lại:

1. Aurora chọn một số nguyên \(X\ge0\).
2. Bianca chọn một số nguyên \(Y\ge0\) sao cho chồng còn ít nhất \(Y\) chiếc bánh và \(Y\ne X\).
3. Aurora ăn \(Y\) chiếc bánh trên cùng, hoặc không ăn chiếc nào nếu \(Y=0\).
4. Nếu vẫn còn bánh, Bianca ăn chiếc bánh trên cùng.

Mỗi chiếc bánh \(i\) có khối lượng \(W_i\). Khi hết bánh, mức hạnh phúc của mỗi người bằng tổng khối lượng bánh người đó đã ăn. Cả hai đều biết chiến thuật tối ưu và luôn chọn nước đi tối đa hóa mức hạnh phúc cuối cùng của chính mình.

Trong \(Q\) ngày tiếp theo, mỗi ngày ông làm một chồng mới có cùng số bánh. Cuối mỗi ngày trước ngày chơi tiếp theo, ông chỉ thay đổi khối lượng của một chiếc bánh; các chiếc khác giữ nguyên như ngày trước.

Hãy tính mức hạnh phúc cuối cùng của Bianca với chồng ban đầu và sau từng lần thay đổi.

Dữ liệu vào

Dòng đầu chứa \(N,Q\). Các bánh được đánh số từ \(0\) ở trên cùng đến \(N-1\) ở dưới cùng.

Dòng thứ hai chứa \(W_0,W_1,\ldots,W_{N-1}\).

Dòng thứ \(i\) trong \(Q\) dòng tiếp theo chứa \(P_i,Z_i\): khối lượng bánh \(P_i\) được đổi thành \(Z_i\).

Dữ liệu ra

In \(Q+1\) số nguyên: mức hạnh phúc của Bianca với chồng ban đầu rồi sau mỗi thay đổi.

Ràng buộc

• \(2\le N\le100\,000\).
• \(0\le Q\le100\,000\).
• \(1\le W_i\le50\).
• \(0\le P_i\le N-1\) và \(1\le Z_i\le50\).

Phân nhóm

1. \(8\) điểm: \(Q=0\) và mọi \(W_i=1\).
2. \(9\) điểm: \(N\le3\), \(Q\le5\).
3. \(11\) điểm: tại mọi thời điểm \(W_0\ge W_1\ge\cdots\ge W_{N-1}\).
4. \(13\) điểm: \(N\le100\), \(Q\le50\).
5. \(18\) điểm: \(N\le20\,000\), \(Q\le50\).
6. \(12\) điểm: \(N\le20\,000\), \(Q\le5000\).
7. \(29\) điểm: không có ràng buộc thêm.

Ví dụ

2 1
10 15
1 1

10
1

5 2
1 1 1 1 2
2 20
3 30

3
4
24

4 2
1 2 4 8
3 2
2 3

7
4
4

3 0
1 1 1

1

3 4
50 8 1
1 1
1 8
2 7
2 1

8
1
8
8
8

Nguồn

EGOI 2026 - Ngày 1, Biscuits.

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

Tại Cesenatico có một hội kín gồm \(N\) nhà tin học nữ. Không thành viên nào biết thành viên nào khác. Mỗi thành viên có một ID duy nhất là số nguyên không âm \(I\).

Các thành viên chỉ giao tiếp gián tiếp bằng những con số viết phấn tại nhiều địa điểm trong thành phố. Cứ 100 năm, hội tiến hành điều tra dân số. Khi hoàn tất, mọi thành viên phải biết chính xác tổng số thành viên \(N\).

Quá trình kéo dài nhiều ngày. Trong mỗi ngày, mỗi thành viên chưa dừng phải chọn đúng một hành động:

• Đọc: chọn địa điểm \(P\), đến đó ban ngày và đọc số đang được viết.
• Ghi: chọn địa điểm \(P\) và số \(V\), đến đó vào tối muộn và thay số cũ bằng \(V\). Người ghi không được đọc số cũ trước khi ghi.
• Dừng: không thực hiện hành động nào trong các ngày sau.

Nghiêm cấm từ hai thành viên trở lên ghi vào cùng một địa điểm trong cùng ngày. Nhiều người có thể đọc cùng chỗ. Nếu trong cùng ngày có người đọc và người ghi cùng một chỗ, mọi lượt đọc xảy ra trước lượt ghi.

Hãy lập chiến lược làm giảm số ngày đến khi mọi thành viên biết đúng \(N\).

Giao thức tương tác

Đây là bài giao tiếp nhiều tiến trình. Có một số chưa biết \(N\) tiến trình submission chạy đồng thời, mỗi tiến trình đại diện cho một thành viên.

Có \(10^{18}\) địa điểm, đánh số \(0\le P<10^{18}\). Ban đầu mọi địa điểm chứa \(0\). Giá trị được ghi phải là số nguyên \(0\le V\le10^9\); trong hầu hết phân nhóm chỉ được ghi \(0\) hoặc \(1\).

Khi bắt đầu, mỗi tiến trình đọc hai số \(I,M\) (\(0\le I<M\)): ID riêng của thành viên và tổng số ID có thể có. Mọi tiến trình trong cùng test nhận cùng \(M\), nhận các \(I\) đôi một khác nhau, và có thể có ID không thuộc thành viên nào.

Mỗi ngày, tiến trình in đúng một trong các lệnh:

• r P: đọc địa điểm \(P\), sau đó đọc một dòng chứa giá trị hiện tại tại đó.
• w P V: ghi \(V\) tại \(P\). Nếu nhiều tiến trình ghi cùng \(P\) trong ngày, đáp án bị chấm sai.
• ! N: trả lời và dừng. Sau lệnh này, tiến trình phải kết thúc bình thường; các tiến trình khác có thể tiếp tục.

Nếu bất kỳ tiến trình nào trả lời sai, vi phạm giao thức, dùng quá \(500\) ngày hoặc vượt giới hạn thời gian/bộ nhớ riêng của tiến trình, test bị chấm sai. Nếu không, điểm test phụ thuộc vào \(D\), số ngày lớn nhất mà một tiến trình dùng. Để đạt trọn điểm cần \(D\le61\) và chỉ ghi \(V\in\{0,1\}\).

Sau mỗi lần in lệnh, phải flush standard output. Trong C++ có thể dùng cout << endl hoặc fflush(stdout); trong Python, input() tự flush luồng output đang chờ.

Ràng buộc

• \(1\le N\le100\).
• \(1\le M\le100\,000\).
• Được dùng tối đa \(500\) ngày.

Phân nhóm

1. \(11\) điểm: \(M\le100\) và các ID là \(0,1,\ldots,N-1\).
2. \(12\) điểm: \(N\le2\).
3. \(22\) điểm: \(M\le8000\) và được ghi mọi số \(0\le V\le10^9\).
4. \(55\) điểm: không có ràng buộc thêm.

Trong các nhóm 1, 2 và 4, chỉ được ghi \(V=0\) hoặc \(V=1\).

Gọi \(X_s\) là điểm tối đa của nhóm \(s\) và \(D_s\) là số ngày lớn nhất trên các test của nhóm đó. Điểm nhóm là:

Hình 1: Tổng điểm khi mọi phân nhóm đều được giải với cùng số ngày lớn nhất \(D\).

Kết quả được làm tròn đến số nguyên gần nhất theo từng nhóm.

Ví dụ giao thức

Ví dụ chính thức thứ nhất có \(N=5\), \(M=100\), các ID \(0,1,2,3,4\). Ví dụ thứ hai có \(N=2\), \(M=8000\), các ID \(0,3\). Các chuỗi lệnh trong đề gốc chỉ minh họa giao thức, không phải chiến lược hiệu quả. Trong ngày, lượt đọc luôn thấy giá trị trước các lượt ghi của chính ngày đó.

Công cụ thử nghiệm

Gói đính kèm cung cấp testing_tool.py, hai template census.cpp, census.py và hai input mẫu. Input cho công cụ gồm \(N,M\), sau đó là \(N\) ID. Công cụ này chỉ hỗ trợ thử cục bộ và không phải grader chính thức.

Nguồn

EGOI 2026 - Ngày 1, Census.

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