EGOI 2026 - Ngày 2

Có một tòa nhà cao \(N\) tầng, mỗi tầng có đúng một cư dân. Các tầng được đánh số từ \(0\) đến \(N-1\) theo thứ tự từ dưới lên; cư dân \(r\) sống ở tầng \(r\).

Mỗi tầng có ban công trồng cây. Cư dân có thể giúp tưới cây ở ban công ngay bên dưới. Mỗi sáng tại thời điểm \(0\), mọi cư dân rời tòa nhà. Ban đầu cư dân \(r\) về nhà lúc \(t_r\). Nếu \(r\) về sớm hơn nghiêm ngặt người ở tầng dưới, tức \(t_r<t_{r-1}\), thì \(r\) tưới cây giúp cư dân \(r-1\); nếu không, cư dân \(r-1\) tự tưới.

Cuối mỗi ngày xảy ra đúng một sự kiện:

• !: một cư dân thay đổi giờ về nhà, có hiệu lực từ ngày kế tiếp.
• ?: một cư dân hỏi mình đã tưới cây giúp tầng dưới bao nhiêu lần.

Cư dân \(0\) không tưới giúp ai; cây của cư dân \(N-1\) không được ai ở tầng trên tưới giúp.

Dữ liệu vào

Dòng đầu chứa \(N,D\), số cư dân và số ngày cần theo dõi.

Dòng tiếp theo chứa \(t_0,t_1,\ldots,t_{N-1}\).

\(D\) dòng tiếp theo, dòng thứ \(i\) mô tả sự kiện cuối ngày \(i\):

• ! r x: từ ngày kế tiếp, đặt \(t_r=x\) (\(0\le r<N\)). \(x\) có thể bằng giá trị hiện tại.
• ? r: hỏi số lần cư dân \(r\) đã tưới giúp cư dân \(r-1\) kể từ đầu ngày \(0\) (\(1\le r<N\)).

Bảo đảm có ít nhất một sự kiện ?.

Dữ liệu ra

Với mỗi sự kiện ? r, in số lần cư dân \(r\) đã tưới cây giúp cư dân \(r-1\) kể từ đầu ngày \(0\). Không tính số lần cư dân tự tưới cây của mình.

Ràng buộc

• \(2\le N\le200\,000\).
• \(1\le D\le200\,000\).
• Ban đầu và sau mỗi thay đổi, \(1\le t_r\le10^9\).

Phân nhóm

1. \(9\) điểm: \(D=1\) và sự kiện duy nhất là ?.
2. \(12\) điểm: mọi sự kiện đều là ?.
3. \(13\) điểm: \(N=2\).
4. \(18\) điểm: \(N,D\le2000\).
5. \(21\) điểm: mỗi cư dân thay đổi giờ về nhiều nhất một lần.
6. \(27\) điểm: không có ràng buộc thêm.

Ví dụ

3 4
7 7 5
? 2
? 1
? 2
? 2

1
0
3
4

2 5
5 7
! 1 4
? 1
! 0 4
! 1 6
? 1

1
2

4 6
13 9 15 2
! 1 18
? 3
! 0 12
! 2 1
? 1
? 2

2
1
5

3 6
5 2 4
? 1
! 1 8
! 0 10
! 1 3
? 1
? 2

1
4
2

Nguồn

EGOI 2026 - Ngày 2, Watering Plants.

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

Liliana có \(N\) loại nguyên liệu trang trí bánh, với \(a_i\) miếng thuộc loại \(i\).

Độ ngon của một chiếc bánh là số lần xuất hiện của loại nguyên liệu xuất hiện nhiều nhất trên bánh đó. Ví dụ, bánh có các nguyên liệu \(\{1,1,2,2,2\}\) có độ ngon \(3\); bánh \(\{0,0,1,1,2\}\) có độ ngon \(2\).

Liliana muốn dùng hết mọi nguyên liệu, không để thừa, để làm nhiều bánh có cùng độ ngon. Cô cân nhắc \(Q\) kịch bản; kịch bản \(j\) yêu cầu làm đúng \(K_j\) chiếc bánh. Các bánh có thể nhận số miếng và số loại nguyên liệu khác nhau, nhưng mỗi bánh phải có ít nhất một miếng.

Với mỗi kịch bản, hãy xác định có thể phân phối toàn bộ nguyên liệu vào đúng \(K_j\) bánh có cùng độ ngon hay không.

Dữ liệu vào

Dòng đầu chứa \(N,Q\).

Dòng thứ hai chứa \(a_0,a_1,\ldots,a_{N-1}\).

\(Q\) dòng tiếp theo, mỗi dòng chứa một số \(K_j\).

Dữ liệu ra

In \(Q\) dòng. Dòng \(j\) là YES nếu cách phân phối tương ứng tồn tại, ngược lại là NO.

Ràng buộc

• \(1\le N,Q\le100\,000\).
• \(1\le a_i\le100\,000\).
• \(1\le K_j\le10^{18}\).

Phân nhóm

1. \(9\) điểm: \(N=1\).
2. \(22\) điểm: \(Q=1\) và \(K_j=2\).
3. \(24\) điểm: \(Q\le5\), \(N\le1000\), \(a_i\le1000\).
4. \(24\) điểm: \(Q\le5\).
5. \(21\) điểm: không có ràng buộc thêm.

Ví dụ

4 5
2 5 1 1
1
2
3
4
5

YES
NO
YES
NO
YES

1 1
4
2

YES

5 3
1 1 1 1 1
1
1000000000000000000
5

YES
NO
YES

Nguồn

EGOI 2026 - Ngày 2, Cakes.

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

Một khu vực lớn trên dãy Alps vừa trở thành khu bảo tồn. Ban đầu không có con cáo nào; mỗi ngày có thêm một con cáo đến. Nhà sinh vật học Simona quan tâm đến số gia đình cáo tại từng thời điểm.

Lãnh thổ săn mồi của cáo \(i\) là đoạn \([L_i,R_i]\), với \(L_i<R_i\). Các đoạn có thể giao nhau hoặc chứa nhau. Hai cáo \(i,j\) là họ hàng trực tiếp nếu lãnh thổ này chứa lãnh thổ kia:

hoặc

Hai cáo thuộc cùng một gia đình khi chúng là họ hàng trực tiếp hoặc được nối bởi một chuỗi quan hệ họ hàng trực tiếp. Chính xác hơn, tồn tại dãy cáo \(c_0,c_1,\ldots,c_{m-1}\) với \(c_0=a\), \(c_{m-1}=b\), và \(c_i,c_{i+1}\) là họ hàng trực tiếp với mọi \(0\le i<m-1\).

Cáo \(i\) đến vào ngày \(i\) và ở lại vĩnh viễn với lãnh thổ \([L_i,R_i]\). Sau mỗi ngày, hãy tính số gia đình sau khi cáo mới đến.

Dữ liệu vào

Dòng đầu chứa \(N\).

\(N\) dòng tiếp theo, dòng \(i\) chứa \(L_i,R_i\).

Dữ liệu ra

In \(N\) dòng. Dòng \(i\) chứa số gia đình cáo sau khi cáo \(i\) đến.

Ràng buộc

• \(1\le N\le100\,000\).
• \(0\le L_i<R_i\le200\,000\).
• Không có cặp \((L_i,R_i)\) nào xuất hiện hai lần.

Phân nhóm

1. \(10\) điểm: \(N\le100\).
2. \(15\) điểm: \(N\le2000\).
3. \(16\) điểm: \(R_i-L_i\le2\).
4. \(23\) điểm: \(L_i<L_{i+1}\).
5. \(36\) điểm: không có ràng buộc thêm.

Ví dụ

4
1 4
3 6
3 4
6 7

1
2
1
2

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

1
2
3
4
5
4

5
0 5
1 4
2 7
3 6
4 5

1
1
2
2
1

Nguồn

EGOI 2026 - Ngày 2, Fox Families.

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

Lễ bế mạc EGOI có \(N\) vị khách quan trọng cần ngồi ở hàng ghế đầu theo một thứ tự ngoại giao đã được xác định nhưng bị thất lạc.

Khách và ghế đều được đánh số từ \(0\) đến \(N-1\). Gọi \(g_I\) là khách ngồi ở ghế \(I\), và \(s_I\) là ghế của khách \(I\).

Hình 1: Một hàng có năm khách, với \(g=[3,1,0,2,4]\) và \(s=[2,1,3,0,4]\).

Một ứng dụng nhận đúng ba số hiệu khách phân biệt \(I,J,K\) và trả số khách ít nhất xuất hiện trong một bức ảnh chứa cả ba người, tức:

Hãy dùng ứng dụng để xác định dãy \(g_0,g_1,\ldots,g_{N-1}\). Luôn có đúng hai đáp án, là hai chiều đảo ngược của nhau; có thể in một trong hai. Điểm phụ thuộc vào số truy vấn.

Giao thức tương tác

Đây là bài tương tác qua standard input/output.

Đầu tiên đọc số test \(T\). Với mỗi test:

1. Đọc \(N\).
2. Để hỏi, in ? I J K, trong đó \(I,J,K\) là ba số phân biệt thuộc \([0,N-1]\), rồi đọc một số nguyên dương là câu trả lời.
3. Để trả lời, in ! g_0 g_1 ... g_{N-1}.

Sau khi giải hết \(T\) test, chương trình phải kết thúc bình thường. Grader chính thức có thể thích nghi: ở một số test, hoán vị chưa được cố định trước mà được chọn dần tùy theo các truy vấn đã hỏi.

Phải flush standard output sau mỗi lệnh. Trong C++ có thể dùng cout << endl hoặc fflush(stdout); trong Python dùng print(..., flush=True).

Ràng buộc

• \(1\le T\le10\).
• \(N\) chỉ có thể là \(5\) (chỉ ở ví dụ), \(8\), \(40\) hoặc \(2000\).
• Mỗi test được hỏi nhiều nhất \(10\,000\) truy vấn.

Phân nhóm

1. \(9\) điểm: \(N=8\).
2. \(11\) điểm: \(N=2000\), và khách \(0,1\) ngồi cạnh nhau.
3. \(15\) điểm: \(N=40\).
4. \(65\) điểm: \(N=2000\).

Nhóm 1 và 2 nhận trọn điểm nếu giải đúng mọi test. Với nhóm 3 và 4, gọi \(Q_s\) là số truy vấn lớn nhất trên một test và \(X_s=\max(1,Q_s/N)\). Khi đó:

Điểm được làm tròn đến số nguyên gần nhất theo từng nhóm. Để đạt trọn điểm cần giải nhóm 3 bằng không quá \(55\) truy vấn và nhóm 4 bằng không quá \(2597\) truy vấn.

Ví dụ giao thức

Grader       Submission
1
5
             ? 0 2 4
3
             ? 3 0 1
3
             ? 0 4 3
5
             ! 3 1 0 2 4

Trong ví dụ, ba câu trả lời đủ xác định thứ tự là [3,1,0,2,4] hoặc thứ tự đảo ngược [4,2,0,1,3].

Công cụ thử nghiệm

Gói đính kèm cung cấp testing_tool.py, các template seatingplan.cpp, seatingplan.py và input mẫu. Input cho công cụ gồm \(T\), rồi với mỗi test là \(N\) và hoán vị \(g\). Công cụ chỉ hỗ trợ thử cục bộ; grader chính thức có thể thích nghi và có hành vi khác.

Nguồn

EGOI 2026 - Ngày 2, Seating Plan.

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