JOI 2024 - Vòng chung kết quốc gia

Chủ tịch K chịu trách nhiệm điều chỉnh nhiệt độ của căn phòng nơi các cán bộ đang làm việc. Ông muốn mọi người cảm thấy thoải mái nhất có thể.

Hiện có \(N\) cán bộ trong phòng, được đánh số từ \(1\) đến \(N\). Khi không mặc áo khoác, nhiệt độ thích hợp với cán bộ \(i\) (\(1 \le i \le N\)) là \(A_i\) độ. Với mỗi người, mỗi khi mặc thêm một chiếc áo khoác, nhiệt độ thích hợp giảm đi \(T\) độ. Nói cách khác, khi cán bộ \(i\) mặc \(k\) chiếc áo khoác, nhiệt độ thích hợp với người đó là \(A_i-kT\) độ.

Khi nhiệt độ phòng là \(x\) độ và nhiệt độ thích hợp với một cán bộ là \(y\) độ, độ khó chịu của người đó là \(|x-y|\), trong đó \(|t|\) là giá trị tuyệt đối của \(t\). Tùy theo nhiệt độ phòng, mỗi cán bộ tự chọn số áo khoác cần mặc, là một số nguyên không âm, để độ khó chịu của mình nhỏ nhất.

Chủ tịch K gọi giá trị lớn nhất trong các độ khó chịu của mọi cán bộ là độ khó chịu của căn phòng. Ông muốn chọn nhiệt độ phòng sao cho giá trị này nhỏ nhất. Nhiệt độ phòng được chọn phải là một số nguyên.

Cho thông tin về các cán bộ và nhiệt độ thích hợp, hãy tìm độ khó chịu nhỏ nhất có thể của căn phòng.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo dạng:

N T
A_1 A_2 ... A_N

Dữ liệu ra

In ra một dòng chứa độ khó chịu nhỏ nhất có thể của căn phòng.

Ràng buộc

• \(2 \le N \le 500\,000\).
• \(1 \le T \le 10^9\).
• \(1 \le A_i \le 10^9\) (\(1 \le i \le N\)).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. 15 điểm: \(N=2\).
2. 5 điểm: \(N \le 3\,000\), \(T=1\).
3. 30 điểm: \(N \le 3\,000\), \(T \le 2\).
4. 35 điểm: \(N \le 3\,000\), \(T \le 3\,000\).
5. 15 điểm: Không có ràng buộc bổ sung.

Ví dụ

2 4
19 24

1

3 1
21 19 23

0

6 8
24 22 21 25 29 17

2

Nguồn

Room Temperature, JOI 2024, vòng chung kết quốc gia, bài 1 (tiếng Anh) · Đề tiếng Nhật. Tác giả: Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Vương quốc JOI có \(N\) nhà ga, được đánh số từ \(1\) đến \(N\), và \(M\) tuyến đường sắt, được đánh số từ \(1\) đến \(M\). Tuyến đường sắt \(i\) (\(1 \le i \le M\)) nối hai chiều giữa ga \(A_i\) và ga \(B_i\), với thời gian di chuyển là \(C_i\) phút.

Là một vị bộ trưởng của vương quốc JOI, bạn quyết định xây thêm đúng một tuyến đường sắt như sau: chọn hai số nguyên \(u,v\) thỏa mãn \(1 \le u<v \le N\), rồi xây một tuyến nối hai chiều giữa ga \(u\) và ga \(v\), với thời gian di chuyển là \(L\) phút. Bạn được phép chọn hai ga đã có tuyến đường sắt nối trực tiếp với nhau.

Sau khi tuyến mới được xây dựng, nhà vua sẽ vui nếu có thể đi từ ga \(S\) đến ga \(T\) bằng các tuyến đường sắt trong thời gian không quá \(K\) phút. Không tính thời gian chờ tàu hay chuyển tuyến.

Có \(\frac{N(N-1)}{2}\) cách chọn hai số \(u,v\). Cho thông tin về các nhà ga, các tuyến đường sắt và yêu cầu của nhà vua, hãy đếm số cách chọn làm nhà vua vui.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo dạng:

N M
S T L K
A_1 B_1 C_1
A_2 B_2 C_2
...
A_M B_M C_M

Dữ liệu ra

In ra một dòng chứa số cách chọn hai số nguyên \(u,v\) làm nhà vua vui.

Ràng buộc

• \(2 \le N \le 200\,000\).
• \(1 \le M \le 200\,000\).
• \(1 \le S<T \le N\).
• \(1 \le L \le 10^9\).
• \(1 \le K \le 10^{15}\).
• \(1 \le A_i<B_i \le N\) (\(1 \le i \le M\)).
• \((A_i,B_i) \ne (A_j,B_j)\) (\(1 \le i<j \le M\)).
• \(1 \le C_i \le 10^9\) (\(1 \le i \le M\)).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. 8 điểm: \(L=1\), \(K=2\), \(C_i=1\) với mọi \(1 \le i \le M\).
2. 16 điểm: \(N \le 50\), \(M \le 50\).
3. 29 điểm: \(N \le 3\,000\), \(M \le 3\,000\).
4. 47 điểm: Không có ràng buộc bổ sung.

Ví dụ

7 8
6 7 1 2
1 2 1
1 6 1
2 3 1
2 4 1
3 5 1
3 7 1
4 5 1
5 6 1

4

3 2
1 3 1 2
1 2 1
2 3 1

3

6 4
2 5 1000000000 1
1 2 1000000000
2 3 1000000000
2 4 1000000000
5 6 1000000000

0

18 21
4 8 678730772 3000000062
5 13 805281073
8 17 80983648
3 8 996533440
10 16 514277428
2 5 57914340
6 11 966149890
8 12 532734310
2 9 188599710
2 3 966306014
12 16 656457780
16 18 662633078
1 15 698078877
2 8 665665772
2 6 652261981
14 15 712798281
7 13 571169114
13 14 860543313
6 7 454251187
9 14 293590683
6 14 959532841
3 11 591245645

16

Nguồn

Construction Project 2, JOI 2024, vòng chung kết quốc gia, bài 2 (tiếng Anh) · Đề tiếng Nhật. Tác giả: Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Đại lộ JOI là một con đường dài \(L\) mét theo hướng đông-tây. Điểm trên đường cách đầu phía tây \(l\) mét (\(0 \le l \le L\)) được gọi là vị trí \(l\).

Năm nay, cuộc thi marathon đầu tiên trên đại lộ JOI sẽ được tổ chức. Cuộc thi có luật khác với marathon thông thường:

• Trước cuộc thi, có \(N\) quả bóng được đặt trên đường. Quả bóng thứ \(i\) (\(1 \le i \le N\)) nằm tại vị trí \(X_i\). Nhiều quả bóng có thể nằm ở cùng một vị trí.
• Người tham gia xuất phát tại vị trí được chỉ định.
• Người tham gia phải thu nhặt đủ \(N\) quả bóng và mang tất cả chúng đến vị trí đích được chỉ định trong thời gian cho phép để hoàn thành cuộc thi. Sau khi nhặt một quả bóng, nếu đặt nó xuống đường thì người tham gia sẽ bị loại.

Vị trí xuất phát, vị trí đích và thời gian cho phép chưa được công bố, nhưng đã biết chúng sẽ được chọn trong \(Q\) kịch bản. Ở kịch bản thứ \(j\) (\(1 \le j \le Q\)), người tham gia xuất phát tại vị trí \(S_j\), về đích tại vị trí \(G_j\), với thời gian cho phép là \(T_j\) giây.

Rie sẽ tham gia cuộc thi. Cô mất \(1\) giây để nhặt một quả bóng. Khi đang mang \(x\) quả bóng, cô mất \(x+1\) giây để di chuyển \(1\) mét trên đường.

Cho thông tin về đại lộ JOI, các quả bóng và các kịch bản, hãy xác định với từng kịch bản liệu có cách để Rie hoàn thành cuộc thi hay không.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo dạng:

N L
X_1 X_2 ... X_N
Q
S_1 G_1 T_1
S_2 G_2 T_2
...
S_Q G_Q T_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa Yes nếu tồn tại cách để Rie hoàn thành cuộc thi ở kịch bản thứ \(j\), hoặc No nếu không tồn tại.

Ràng buộc

• \(1 \le N \le 500\,000\).
• \(1 \le L \le 500\,000\).
• \(0 \le X_i \le L\) (\(1 \le i \le N\)).
• \(1 \le Q \le 500\,000\).
• \(0 \le S_j \le L\) (\(1 \le j \le Q\)).
• \(0 \le G_j \le L\) (\(1 \le j \le Q\)).
• \(1 \le T_j \le 500\,000\) (\(1 \le j \le Q\)).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. 7 điểm: \(N \le 7\), \(Q \le 10\), \(S_j=0\) và \(G_j=0\) với mọi \(1 \le j \le Q\).
2. 7 điểm: \(N \le 7\), \(Q \le 10\).
3. 10 điểm: \(N \le 14\), \(Q \le 10\).
4. 28 điểm: \(N \le 100\), \(Q \le 10\).
5. 10 điểm: \(N \le 2\,000\), \(Q \le 10\).
6. 19 điểm: \(N \le 2\,000\).
7. 19 điểm: Không có ràng buộc bổ sung.

Ví dụ

3 100
30 80 30
3
0 100 403
0 100 300
0 100 262

Yes
Yes
No

3 100
30 80 30
3
0 0 403
0 0 300
0 0 262

Yes
No
No

6 100
0 50 100 0 50 100
4
20 70 600
70 20 600
10 40 600
40 10 600

No
Yes
No
Yes

Nguồn

Marathon Race 2, JOI 2024, vòng chung kết quốc gia, bài 3 (tiếng Anh) · Đề tiếng Nhật. Tác giả: Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Học viện JOI có \(N\) học sinh, được đánh số từ \(1\) đến \(N\).

Học viện sắp tổ chức một buổi trao đổi quà. Mỗi học sinh đã chuẩn bị một món quà để mang đến; món quà của học sinh \(i\) (\(1 \le i \le N\)) có giá trị \(A_i\). Các học sinh không muốn nhận một món quà có giá trị quá thấp so với quà của mình. Cụ thể, học sinh \(i\) sẽ không hài lòng nếu nhận món quà có giá trị nhỏ hơn \(B_i\). Luôn có \(B_i<A_i\).

Tuy nhiên, không nhất thiết cả \(N\) học sinh đều tham gia. Chủ tịch K, người đứng đầu học viện, đang xem xét \(Q\) nhóm học sinh có thể tham gia. Nhóm thứ \(j\) (\(1 \le j \le Q\)) gồm \(R_j-L_j+1\) học sinh \(L_j,L_j+1,\ldots,R_j\).

Một nhóm có ít nhất hai học sinh được gọi là có thể trao đổi quà nếu có cách trao đổi quà trong nhóm sao cho không ai nhận lại quà của chính mình và không ai cảm thấy không hài lòng. Chính xác hơn, nhóm gồm \(m\) học sinh \(p_1,p_2,\ldots,p_m\) (\(m \ge 2\)) có thể trao đổi quà khi và chỉ khi tồn tại một hoán vị \(q_1,q_2,\ldots,q_m\) của \(p_1,p_2,\ldots,p_m\) thỏa mãn cả hai điều kiện sau:

• \(p_k \ne q_k\) với mọi \(1 \le k \le m\).
• \(A_{q_k} \ge B_{p_k}\) với mọi \(1 \le k \le m\).

Ở đây, \(q_k\) là số hiệu của học sinh tặng quà cho học sinh \(p_k\).

Chủ tịch K muốn buổi trao đổi quà thành công. Cho thông tin về các học sinh và các nhóm, hãy xác định với từng nhóm liệu nhóm đó có thể trao đổi quà hay không.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo dạng:

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
Q
L_1 R_1
L_2 R_2
...
L_Q R_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa Yes nếu nhóm thứ \(j\) có thể trao đổi quà, hoặc No nếu không thể.

Ràng buộc

• \(2 \le N \le 500\,000\).
• \(1 \le B_i<A_i \le 2N\) (\(1 \le i \le N\)).
• Các giá trị \(A_1,B_1,A_2,B_2,\ldots,A_N,B_N\) đôi một khác nhau.
• \(1 \le Q \le 200\,000\).
• \(1 \le L_j<R_j \le N\) (\(1 \le j \le Q\)).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. 4 điểm: \(N \le 10\), \(Q \le 10\).
2. 5 điểm: \(N \le 18\), \(Q \le 10\).
3. 10 điểm: \(N \le 100\,000\), \(A_1 \ge 2N-2\), \(B_1=1\), \(Q=1\), \(L_1=1\), \(R_1=N\).
4. 31 điểm: \(N \le 100\,000\), \(Q \le 10\).
5. 8 điểm: \(N \le 100\,000\); \(A_i<A_{i+1}\) và \(B_i<B_{i+1}\) với mọi \(1 \le i \le N-1\).
6. 12 điểm: \(N \le 100\,000\); \(A_i<A_{i+1}\) với mọi \(1 \le i \le N-1\).
7. 18 điểm: \(N \le 100\,000\).
8. 12 điểm: Không có ràng buộc bổ sung.

Ví dụ

4
3 8 5 7
2 6 1 4
3
3 4
1 3
1 4

Yes
No
Yes

3
5 6 3
1 4 2
1
1 3

Yes

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

No
Yes
No

10
2 5 8 10 12 14 16 17 19 20
1 4 7 6 11 13 9 3 18 15
8
2 9
1 6
2 8
2 4
1 2
1 6
7 10
5 8

No
No
Yes
No
No
No
Yes
Yes

Nguồn

Gift Exchange, JOI 2024, vòng chung kết quốc gia, bài 4 (tiếng Anh) · Đề tiếng Nhật. Tác giả: Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Thành phố JOI có một mạng lưới đường dạng ô vuông, gồm \(H\) con đường đông-tây dài vô hạn và \(W\) con đường bắc-nam dài vô hạn. Giao lộ \((i,j)\) (\(1 \le i \le H\), \(1 \le j \le W\)) là nơi con đường đông-tây thứ \(i\) tính từ phía bắc gặp con đường bắc-nam thứ \(j\) tính từ phía tây.

Hiện một số đoạn đường bị đóng do tình trạng xuống cấp. Cụ thể:

• Trên con đường đông-tây thứ \(i\) tính từ phía bắc (\(1 \le i \le H\)), đoạn nối giao lộ \((i,j)\) và \((i,j+1)\) (\(1 \le j \le W-1\)) bị đóng nếu \(A_{i,j}=0\), và đi lại được nếu \(A_{i,j}=1\).
• Trên con đường bắc-nam thứ \(j\) tính từ phía tây (\(1 \le j \le W\)), đoạn nối giao lộ \((i,j)\) và \((i+1,j)\) (\(1 \le i \le H-1\)) bị đóng nếu \(B_{i,j}=0\), và đi lại được nếu \(B_{i,j}=1\).
• Mọi phần đường còn lại, tức là các phần nằm ngoài \(H \times W\) giao lộ, đều bị đóng.

Chủ tịch K, thị trưởng thành phố JOI, quyết định lập một kế hoạch sửa đường. Một kế hoạch gồm không hoặc nhiều lần sửa. Trong một lần sửa, chọn một số nguyên \(i\) thỏa mãn \(1 \le i \le H\), rồi mở lại mọi đoạn đang bị đóng nối \((i,j)\) với \((i,j+1)\), với mọi \(1 \le j \le W-1\). Như vậy, sau lần sửa này, toàn bộ các đoạn giữa các giao lộ trên con đường đông-tây thứ \(i\) đều đi lại được. Cả lần sửa mất \(C_i\) ngày, trong đó \(C_i\) bằng \(1\) hoặc \(2\).

Không thể thực hiện hai lần sửa song song. Vì vậy, thời gian thực hiện một kế hoạch bằng tổng số ngày của tất cả các lần sửa trong kế hoạch đó.

Để bảo đảm việc đi lại giữa các cơ sở quan trọng của thành phố, chủ tịch K đưa ra \(Q\) câu hỏi. Câu hỏi thứ \(k\) (\(1 \le k \le Q\)) như sau: có tồn tại kế hoạch sửa đường để từ bất kỳ giao lộ nào trong \(T_k\) giao lộ \((X_{k,1},Y_{k,1}),(X_{k,2},Y_{k,2}),\ldots,(X_{k,T_k},Y_{k,T_k})\) đều có thể đi đến mọi giao lộ còn lại bằng các đoạn đường đi lại được hay không? Nếu có, thời gian thực hiện nhỏ nhất của một kế hoạch như vậy là bao nhiêu ngày?

Các câu hỏi được xét độc lập trên mạng lưới đường ban đầu. Cho tình trạng đường, số ngày cần để sửa từng con đường đông-tây và nội dung các câu hỏi, hãy trả lời tất cả các câu hỏi.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(H,W,Q\).

\(H\) dòng tiếp theo mô tả \(A\). Dòng thứ \(i\) là một xâu gồm \(W-1\) ký tự 0 hoặc 1 viết liền nhau, không có dấu cách; ký tự thứ \(j\) biểu diễn \(A_{i,j}\).

\(H-1\) dòng tiếp theo mô tả \(B\). Dòng thứ \(i\) là một xâu gồm \(W\) ký tự 0 hoặc 1 viết liền nhau, không có dấu cách; ký tự thứ \(j\) biểu diễn \(B_{i,j}\).

Dòng tiếp theo chứa \(H\) số nguyên \(C_1,C_2,\ldots,C_H\), cách nhau bởi dấu cách.

Sau đó là \(Q\) câu hỏi. Câu hỏi thứ \(k\) có dạng:

T_k
X_{k,1} Y_{k,1}
X_{k,2} Y_{k,2}
...
X_{k,T_k} Y_{k,T_k}

Dữ liệu được đọc từ đầu vào chuẩn.

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa số ngày nhỏ nhất cần thiết của một kế hoạch làm cho \(T_k\) giao lộ trong câu hỏi thứ \(k\) đi lại được với nhau. Nếu không tồn tại kế hoạch như vậy, in ra -1.

Ràng buộc

• \(2 \le H\).
• \(2 \le W\).
• \(H \times W \le 1\,000\,000\).
• \(1 \le Q \le 100\,000\).
• \(A_{i,j}\) bằng \(0\) hoặc \(1\) (\(1 \le i \le H\), \(1 \le j \le W-1\)).
• \(B_{i,j}\) bằng \(0\) hoặc \(1\) (\(1 \le i \le H-1\), \(1 \le j \le W\)).
• \(C_i\) bằng \(1\) hoặc \(2\) (\(1 \le i \le H\)).
• \(2 \le T_k\) (\(1 \le k \le Q\)).
• \(T_1+T_2+\cdots+T_Q \le 200\,000\).
• \(1 \le X_{k,l} \le H\) (\(1 \le k \le Q\), \(1 \le l \le T_k\)).
• \(1 \le Y_{k,l} \le W\) (\(1 \le k \le Q\), \(1 \le l \le T_k\)).
• Với mỗi \(1 \le k \le Q\), các giao lộ \((X_{k,1},Y_{k,1}),(X_{k,2},Y_{k,2}),\ldots,(X_{k,T_k},Y_{k,T_k})\) đôi một khác nhau.
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. 10 điểm: \(C_i=1\) với mọi \(1 \le i \le H\); \(Q \le 5\); \(T_k=2\) với mọi \(1 \le k \le Q\); \(A_{i,j}=0\) với mọi \(1 \le i \le H\), \(1 \le j \le W-1\).
2. 6 điểm: \(C_i=1\) với mọi \(1 \le i \le H\); \(Q \le 5\); \(T_k=2\) với mọi \(1 \le k \le Q\).
3. 15 điểm: \(C_i=1\) với mọi \(1 \le i \le H\); \(Q \le 5\).
4. 11 điểm: \(C_i=1\) với mọi \(1 \le i \le H\); \(T_k=2\) với mọi \(1 \le k \le Q\).
5. 6 điểm: \(C_i=1\) với mọi \(1 \le i \le H\).
6. 12 điểm: \(Q \le 5\).
7. 26 điểm: \(T_k=2\) với mọi \(1 \le k \le Q\).
8. 14 điểm: Không có ràng buộc bổ sung.

Ví dụ

4 3 4
00
00
00
00
100
001
000
1 1 1 1
2
1 1
3 3
2
3 1
1 2
2
2 3
3 3
2
4 2
3 2

1
3
0
-1

4 4 4
100
110
011
010
0010
1001
0101
1 1 1 1
2
1 2
3 1
2
1 4
4 1
2
3 2
1 2
2
4 3
1 1

1
3
2
2

7 3 3
10
00
00
10
00
01
00
110
101
011
001
110
100
1 1 1 1 1 1 1
3
7 2
3 1
3 2
3
3 1
6 3
2 3
7
2 2
1 3
7 3
5 2
1 2
7 2
3 1

3
2
4

4 3 3
00
00
10
00
110
011
001
1 2 2 2
2
1 1
3 1
2
4 3
2 1
2
4 1
1 3

1
2
5

7 3 2
01
00
00
00
00
10
01
100
110
011
001
101
001
1 1 2 1 1 2 2
3
7 2
1 3
5 1
5
1 1
2 2
3 1
2 3
4 2

4
1

Nguồn

Road Service 2, JOI 2024, vòng chung kết quốc gia, bài 5 (tiếng Anh) · Đề tiếng Nhật. Tác giả: Ủy ban Olympic Tin học Nhật Bản. Đề gốc, hình minh họa và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.