JOI 2025 - Vòng loại 2

JOI đang chơi tô màu bằng giấy và băng dính che sơn.

Tờ giấy hình chữ nhật được chia thành lưới gồm \(H\) hàng và \(W\) cột. Gọi ô ở hàng thứ \(i\) từ trên xuống (\(1 \le i \le H\)), cột thứ \(j\) từ trái sang (\(1 \le j \le W\)) là ô \((i, j)\).

Mỗi ô có một màu, được biểu diễn bằng một số nguyên. Ban đầu, màu của tất cả các ô đều là \(0\).

JOI thực hiện \(Q\) thao tác với tờ giấy và băng dính. Thao tác thứ \(k\) (\(1 \le k \le Q\)) được mô tả tùy theo giá trị của số nguyên \(q_k\) như sau:

• Nếu \(q_k = 1\), thao tác được cho bởi các số nguyên \(x_k, y_k, c_k\). Xét từng ô trong bốn ô \((x_k, y_k)\), \((x_k + 1, y_k)\), \((x_k, y_k + 1)\), \((x_k + 1, y_k + 1)\): nếu ô không bị băng dính che phủ thì đổi màu ô thành \(c_k\); nếu ô bị băng dính che phủ thì không làm gì với ô đó.
• Nếu \(q_k = 2\), thao tác được cho bởi các số nguyên \(x_k, y_k\). Che phủ bốn ô \((x_k, y_k)\), \((x_k + 1, y_k)\), \((x_k, y_k + 1)\), \((x_k + 1, y_k + 1)\) bằng băng dính.

Sau khi hoàn thành \(Q\) thao tác, JOI bóc tất cả băng dính ra. Khi bóc băng dính khỏi một ô, màu của ô đó vẫn là màu ngay trước khi ô bị băng dính che phủ.

Cho thông tin về \(Q\) thao tác, hãy xác định màu cuối cùng của tất cả các ô trên tờ giấy.

Dữ liệu vào

Dữ liệu vào có dạng:

H W Q
(Query 1)
(Query 2)
...
(Query Q)

Mỗi dòng \((\mathrm{Query}\ k)\) (\(1 \le k \le Q\)) chứa các số nguyên cách nhau bởi dấu cách. Số nguyên đầu tiên là \(q_k\), và dòng này có một trong hai dạng:

• Nếu \(q_k = 1\): 1 x_k y_k c_k.
• Nếu \(q_k = 2\): 2 x_k y_k.

Dữ liệu ra

In màu cuối cùng của tất cả các ô trên \(H\) dòng. Dòng thứ \(i\) (\(1 \le i \le H\)) chứa \(W\) số nguyên cách nhau bởi dấu cách, trong đó số thứ \(j\) (\(1 \le j \le W\)) là màu của ô \((i, j)\).

Ràng buộc

• \(2 \le H \le 500\).
• \(2 \le W \le 500\).
• \(1 \le Q \le 200\,000\).
• \(q_k \in \{1, 2\}\) (\(1 \le k \le Q\)).
• Nếu \(q_k = 1\): \(1 \le x_k \le H - 1\), \(1 \le y_k \le W - 1\), \(1 \le c_k \le 10^9\) (\(1 \le k \le Q\)).
• Nếu \(q_k = 2\): \(1 \le x_k \le H - 1\), \(1 \le y_k \le W - 1\) (\(1 \le k \le Q\)).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(32\) điểm: \(H = 2\), \(W = 2\), \(q_k = 1\) với mọi \(1 \le k \le Q\).
2. \(32\) điểm: \(q_k = 1\) với mọi \(1 \le k \le Q\).
3. \(36\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5 5 4
1 2 2 1
2 1 2
2 3 3
1 1 3 5

0 0 0 5 0
0 1 1 5 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0

0  0  0  0  0
0  1  1  0  0
0  1  1  0  0
0  0  0  0  0
0  0  0  0  0

0  0* 0* 0  0
0  1* 1* 0  0
0  1  1  0  0
0  0  0  0  0
0  0  0  0  0

0  0* 0* 0  0
0  1* 1* 0  0
0  1  1* 0* 0
0  0  0* 0* 0
0  0  0  0  0

0  0* 0* 5  0
0  1* 1* 5  0
0  1  1* 0* 0
0  0  0* 0* 0
0  0  0  0  0

5 5 3
1 1 1 2
1 3 3 3
1 2 4 2

2 2 0 0 0
2 2 0 2 2
0 0 3 2 2
0 0 3 3 0
0 0 0 0 0

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

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

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủ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.

Bitaro đang chơi bi-a. Bi-a ở đất nước JOI là trò chơi sử dụng \(N\) viên bi được đánh số \(1, 2, \ldots, N\) đặt trên bàn, trên bàn có các lỗ để đưa bi vào. Một viên bi đã rơi vào lỗ sẽ không được đặt trở lại bàn, nên không thể đưa viên bi đó vào lỗ lần nữa. Mục tiêu của Bitaro là đưa vào lỗ một viên bi có số lớn nhất có thể.

Đưa bi vào lỗ đòi hỏi sự tập trung. Ban đầu, mức tập trung của Bitaro là \(X\). Khi đưa viên bi \(i\) (\(1 \le i \le N\)) vào lỗ, mức tập trung giảm đi \(A_i\). Nếu mức tập trung nhỏ hơn \(A_i\), Bitaro không thể đưa viên bi \(i\) vào lỗ.

Trò chơi này còn có quy tắc về thứ tự đưa bi vào lỗ. Cụ thể, nếu \(P_i = -1\) (\(1 \le i \le N\)), có thể đưa viên bi \(i\) vào lỗ bất cứ lúc nào, miễn là có đủ mức tập trung. Nếu \(P_i \ne -1\), để đưa viên bi \(i\) vào lỗ thì viên bi \(P_i\) phải đã được đưa vào lỗ trước đó.

Cho mức tập trung ban đầu của Bitaro và thông tin về từng viên bi, hãy xác định Bitaro có thể đưa ít nhất một viên bi vào lỗ hay không. Nếu có, hãy tìm số lớn nhất của một viên bi mà Bitaro có thể đưa vào lỗ.

Dữ liệu vào

Dữ liệu vào có dạng:

N X
A_1 A_2 ... A_N
P_1 P_2 ... P_N

Dữ liệu ra

In trên một dòng số lớn nhất của một viên bi mà Bitaro có thể đưa vào lỗ. Nếu Bitaro không thể đưa bất kỳ viên bi nào vào lỗ, in ra -1.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le X \le 10^{15}\).
• \(1 \le A_i \le 10^9\) (\(1 \le i \le N\)).
• \(1 \le P_i \le N\) hoặc \(P_i = -1\) (\(1 \le i \le N\)).
• \(P_i \ne i\) (\(1 \le i \le N\)).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(6\) điểm: \(N \le 1000\), \(P_i = -1\) với mọi \(1 \le i \le N\).
2. \(9\) điểm: \(N \le 1000\), \(P_1 = -1\), \(P_i = i - 1\) với mọi \(2 \le i \le N\).
3. \(16\) điểm: \(N \le 1000\), \(P_i < i\) với mọi \(1 \le i \le N\).
4. \(20\) điểm: \(P_i < i\) với mọi \(1 \le i \le N\).
5. \(19\) điểm: \(N \le 1000\).
6. \(30\) điểm: Không có ràng buộc bổ sung.

Ví dụ

6 7
1 2 4 3 10 100
-1 -1 -1 -1 -1 -1

4

5 12
1 2 3 5 8
-1 1 2 3 4

4

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

7

2 1000000000000000
1 1
2 1

-1

9 2468024680
123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678
6 5 4 -1 3 2 1 9 8

6

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủ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.

Alice và Bob đến cửa hàng kem tươi JOICE. Tại đây, khách hàng đặt một cây kem bằng cách chọn đúng một hương vị, một loại ốc quế và một loại đồ phủ.

• Có \(X\) hương vị, với giá lần lượt là \(A_1, A_2, \ldots, A_X\).
• Có \(Y\) loại ốc quế, với giá lần lượt là \(B_1, B_2, \ldots, B_Y\).
• Có \(Z\) loại đồ phủ, với giá lần lượt là \(C_1, C_2, \ldots, C_Z\).

Giá của cây kem là tổng giá của hương vị, ốc quế và đồ phủ đã chọn. Với số nguyên \(P\) cho trước, điểm số của cây kem là giá trị tuyệt đối của hiệu giữa giá cây kem và \(P\).

Alice và Bob định cùng đặt một cây kem, nhưng mong muốn của hai người hoàn toàn trái ngược nhau: Alice muốn điểm số lớn nhất có thể, còn Bob muốn điểm số nhỏ nhất có thể. Vì vậy, họ quyết định chọn hương vị, ốc quế và đồ phủ theo thứ tự sau:

1. Đầu tiên, Alice chọn hương vị.
2. Tiếp theo, Bob chọn loại ốc quế.
3. Cuối cùng, Alice chọn loại đồ phủ.

Cho thông tin về các hương vị, loại ốc quế, loại đồ phủ và số nguyên \(P\), hãy tìm điểm số của cây kem được đặt cuối cùng nếu cả hai người đều lựa chọn tối ưu ở mỗi lượt.

Dữ liệu vào

Dữ liệu vào có dạng:

X Y Z P
A_1 A_2 ... A_X
B_1 B_2 ... B_Y
C_1 C_2 ... C_Z

Dữ liệu ra

In trên một dòng điểm số của cây kem được đặt cuối cùng.

Ràng buộc

• \(1 \le X \le 200\,000\).
• \(1 \le Y \le 200\,000\).
• \(1 \le Z \le 200\,000\).
• \(0 \le P \le 3 \times 10^8\).
• \(0 \le A_i \le 10^8\) (\(1 \le i \le X\)).
• \(0 \le B_j \le 10^8\) (\(1 \le j \le Y\)).
• \(0 \le C_k \le 10^8\) (\(1 \le k \le Z\)).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(7\) điểm: \(X = 1\), \(Y = 1\), \(Z \le 100\).
2. \(17\) điểm: \(X = 1\), \(Y \le 100\), \(Z \le 100\).
3. \(21\) điểm: \(X \le 100\), \(Y \le 100\), \(Z \le 100\).
4. \(22\) điểm: \(X \le 4000\), \(Y \le 4000\), \(Z \le 4000\).
5. \(33\) điểm: Không có ràng buộc bổ sung.

Ví dụ

1 1 3 22
5
10
9 2 3

5

1 2 2 100
11
33 44
40 60

15

2 2 2 0
15 23
5 16
23 45

73

3 3 3 50
12 5 5
2 19 37
10 5 15

14

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủ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.

Một nhà hàng chuyên phục vụ các món ăn Bolivia có \(N\) đầu bếp, được đánh số từ \(1\) đến \(N\). Đầu bếp \(i\) (\(1 \le i \le N\)) có thể nấu món silpancho với độ ngon \(A_i\) và món pique macho với độ ngon \(B_i\).

Tuy nhiên, các đầu bếp rất có chính kiến nên có \(M\) cặp đầu bếp không hòa thuận với nhau. Cặp không hòa thuận thứ \(j\) (\(1 \le j \le M\)) gồm đầu bếp \(U_j\) và đầu bếp \(V_j\).

Khách đến nhà hàng dùng bữa theo cách sau:

• Chọn hai số nguyên \(p, q\) thỏa mãn \(1 \le p < q \le N\), rồi nhờ cặp đầu bếp \(p\) và \(q\) nấu ăn. Không được chọn một cặp đầu bếp không hòa thuận với nhau.
• Với mỗi món silpancho và pique macho, người nấu là đầu bếp có thể nấu món đó với độ ngon cao hơn trong hai đầu bếp \(p\) và \(q\). Nếu cả hai nấu một món ngon như nhau thì một trong hai người sẽ nấu món đó. Lưu ý rằng một đầu bếp có thể nấu cả hai món.
• Mức độ hài lòng của khách là tổng độ ngon của món silpancho và món pique macho.

Có \(Q\) khách đến nhà hàng, được đánh số từ \(1\) đến \(Q\).

Khách \(k\) (\(1 \le k \le Q\)) chọn cặp đầu bếp mang lại mức độ hài lòng cao thứ \(X_k\) trong số các cặp được phép chọn. Cụ thể, gọi mức độ hài lòng là \(S\), khách chọn cặp đầu bếp \(p\) và \(q\) (\(1 \le p < q \le N\)) có giá trị \(S \times N^2 + p \times N + q\) lớn thứ \(X_k\).

Cho thông tin về các đầu bếp và khách, hãy tính mức độ hài lòng của từng khách \(k\) (\(1 \le k \le Q\)).

Dữ liệu vào

Dữ liệu vào có dạng:

N M Q
A_1 A_2 ... A_N
B_1 B_2 ... B_N
U_1 V_1
U_2 V_2
...
U_M V_M
X_1 X_2 ... X_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa mức độ hài lòng của khách \(k\).

Ràng buộc

• \(2 \le N \le 400\,000\).
• \(1 \le A_i \le 10^9\) (\(1 \le i \le N\)).
• \(1 \le B_i \le 10^9\) (\(1 \le i \le N\)).
• \(0 \le M \le 400\,000\).
• \(M < N(N-1)/2\).
• \(1 \le U_j < V_j \le N\) (\(1 \le j \le M\)).
• \((U_i,V_i) \ne (U_j,V_j)\) (\(1 \le i < j \le M\)).
• \(1 \le Q \le 400\,000\).
• \(1 \le X_k \le 400\,000\) (\(1 \le k \le Q\)).
• \(X_k \le N(N-1)/2-M\) (\(1 \le k \le Q\)).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. 4 điểm: \(N \le 50\), \(M \le 50\), \(Q \le 50\), \(X_k \le 50\) (\(1 \le k \le Q\)).
2. 9 điểm: \(B_i=1\) (\(1 \le i \le N\)), \(M=0\), \(Q=1\).
3. 10 điểm: \(B_i=1\) (\(1 \le i \le N\)), \(Q=1\).
4. 5 điểm: \(B_i=1\) (\(1 \le i \le N\)).
5. 29 điểm: \(N \le 100\,000\), \(M \le 100\,000\), \(Q=1\), \(X_1=1\).
6. 14 điểm: \(N \le 100\,000\), \(M \le 100\,000\), \(Q=1\), \(X_1 \le 100\,000\).
7. 18 điểm: \(N \le 100\,000\), \(M \le 100\,000\), \(Q \le 100\,000\), \(X_k \le 100\,000\) (\(1 \le k \le Q\)).
8. 11 điểm: Không có ràng buộc bổ sung.

Ví dụ

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

13
13
11
11

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

6

5 0 4
1 2 3 4 5
5 4 3 2 1
3 9 10 1

9
7
7
10

13 12 10
2 28 28 60 48 77 63 92 13 71 36 91 87
85 7 64 15 55 92 66 91 83 35 49 22 61
2 9
8 13
7 11
9 11
8 12
5 12
4 7
11 12
10 12
4 11
1 5
3 8
49 21 46 13 20 41 6 33 24 7

121
169
129
174
169
137
183
148
169
183

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của bài Intimate Chef, JOI 2024/2025, vòng loại thứ hai, bài 4 của Ủ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.

Bitaro sống bên một hồ lớn hình tròn có chu vi \(L\). Nhà của Bitaro nằm tại một điểm trên bờ hồ. Gọi điểm cách nhà Bitaro một quãng đường \(x\) theo chiều kim đồng hồ dọc bờ hồ (\(0 \le x < L\)) là điểm \(x\). Hiện tại, một cuộc thi marathon quanh hồ đang được lên kế hoạch.

Bitaro nghe nói cuộc thi sẽ diễn ra như sau:

• Ban tổ chức chuẩn bị các số đeo từ \(0\) đến \(L-1\), mỗi số có đúng một chiếc. Mỗi người tham gia đeo một trong các số này. Người đeo số \(l\) (\(0 \le l \le L-1\)) xuất phát tại điểm \(l\).
• Trong \(T\) giây kể từ khi cuộc thi bắt đầu, mỗi người di chuyển quanh hồ theo chiều kim đồng hồ với vận tốc của mình. Thời điểm sau khi cuộc thi bắt đầu được \(t\) giây (\(0 \le t \le T\)) được gọi là thời điểm \(t\).

Bitaro có danh sách những người tham gia cuộc thi. Hiện tại danh sách có \(N\) người. Người thứ \(i\) (\(1 \le i \le N\)) dự định đeo số \(A_i\) và di chuyển quanh hồ theo chiều kim đồng hồ với vận tốc \(S_i\) đơn vị quãng đường mỗi giây.

Dựa trên danh sách, Bitaro đã tính số lần va chạm xảy ra trong cuộc thi. Một va chạm là việc hai người khác nhau có mặt tại cùng một điểm. Chính xác hơn, Bitaro đếm số bộ \((p,q,t)\), trong đó \(p,q\) là các số nguyên thỏa mãn \(0 \le p < q \le L-1\) và \(t\) là số thực thỏa mãn \(0 \le t \le T\), sao cho:

• Có người tham gia đeo số \(p\).
• Có người tham gia đeo số \(q\).
• Người đeo số \(p\) và người đeo số \(q\) ở cùng một điểm tại thời điểm \(t\).

Tuy nhiên, sau đó danh sách được thay đổi \(Q\) lần. Thay đổi thứ \(j\) (\(1 \le j \le Q\)) được mô tả bởi hai số nguyên \(X_j,Y_j\) như sau:

• Nếu trong danh sách hiện tại có người đeo số \(X_j\) và di chuyển quanh hồ theo chiều kim đồng hồ với vận tốc \(Y_j\) đơn vị quãng đường mỗi giây, xóa người đó khỏi danh sách. Nếu không, thêm vào danh sách một người đeo số \(X_j\) và di chuyển quanh hồ theo chiều kim đồng hồ với vận tốc \(Y_j\) đơn vị quãng đường mỗi giây.

Đảm bảo rằng sau mỗi lần thay đổi, danh sách có ít nhất \(2\) người và số đeo của tất cả những người trong danh sách đôi một khác nhau.

Bitaro muốn biết số lần va chạm sẽ xảy ra trong toàn bộ cuộc thi với danh sách người tham gia sau mỗi lần thay đổi. Từ các ràng buộc của bài toán, có thể chứng minh số lần va chạm trong cuộc thi là hữu hạn.

Cho thông tin về cuộc thi và các thay đổi của danh sách, hãy tính số lần va chạm trong cuộc thi với danh sách sau mỗi lần thay đổi, lấy phần dư khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

Dữ liệu vào có dạng:

N L T
A_1 A_2 ... A_N
S_1 S_2 ... S_N
Q
X_1 Y_1
X_2 Y_2
...
X_Q Y_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa phần dư khi chia số lần va chạm trong cuộc thi với danh sách người tham gia sau thay đổi thứ \(j\) cho \(1\,000\,000\,007\).

Ràng buộc

• \(2 \le N\).
• \(N \le L \le 10^9\).
• \(1 \le T \le 10^9\).
• \(0 \le A_i \le L-1\) (\(1 \le i \le N\)).
• \(A_i \ne A_j\) (\(1 \le i < j \le N\)).
• \(1 \le S_i \le 10^9\) (\(1 \le i \le N\)).
• \(1 \le Q\).
• \(N+Q \le 100\,000\).
• \(0 \le X_j \le L-1\) (\(1 \le j \le Q\)).
• \(1 \le Y_j \le 10^9\) (\(1 \le j \le Q\)).
• Sau mỗi lần thay đổi, có ít nhất \(2\) người tham gia.
• Sau mỗi lần thay đổi, các điểm xuất phát của những người tham gia đôi một khác nhau.
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. 10 điểm: \(T=1\), \(S_i \le 2\) (\(1 \le i \le N\)), \(Y_j \le 2\) (\(1 \le j \le Q\)).
2. 8 điểm: \(N \le 2\,000\), \(Q=1\).
3. 11 điểm: \(N \le 2\,000\), \(Q \le 2\,000\).
4. 27 điểm: \(Q=1\).
5. 34 điểm: \(N+Q \le 78\,000\).
6. 10 điểm: Không có ràng buộc bổ sung.

Ví dụ

3 7 2
1 6 3
4 1 6
1
4 2

7

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

1
0

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

9265409

7 100 100
34 12 46 23 57 63 99
12 34 23 12 34 12 23
5
67 34
99 23
33 34
99 12
23 12

330
264
341
440
341

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của bài Collision, JOI 2024/2025, vòng loại thứ hai, bài 5 của Ủ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.