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

Chủ tịch K muốn tạo ra một hoa văn trên bảng ô vuông gồm \(N\) hàng và \(N\) cột. Ô ở hàng thứ \(i\) từ trên xuống (\(1 \le i \le N\)) và cột thứ \(j\) từ trái sang (\(1 \le j \le N\)) được gọi là ô \((i,j)\). Mỗi ô sẽ được tô một màu, trong đó mỗi màu được biểu diễn bằng một số nguyên.

Hiện tại, các ô ở cột đầu tiên và hàng đầu tiên đã được tô màu. Cụ thể, ô \((i,1)\) (\(1 \le i \le N\)) có màu \(A_i\), còn ô \((1,j)\) (\(1 \le j \le N\)) có màu \(B_j\). Dữ liệu bảo đảm \(A_1=B_1\).

Chủ tịch K sẽ tô các ô còn lại theo thứ tự hàng \(i=2,3,\ldots,N\). Trong mỗi hàng \(i\), ông lần lượt xét các cột \(j=2,3,\ldots,N\) và tô ô \((i,j)\) bằng màu có số lớn hơn trong hai màu của ô \((i-1,j)\) và ô \((i,j-1)\). Nếu hai màu có cùng số thì tô ô \((i,j)\) bằng màu đó.

Sau khi cả \(N^2\) ô đã được tô, Chủ tịch K muốn biết màu nào xuất hiện trên nhiều ô nhất và số ô được tô màu đó. Cho kích thước bảng cùng thông tin màu của cột đầu tiên và hàng đầu tiên, hãy tìm hai giá trị này. Nếu có nhiều màu cùng xuất hiện trên nhiều ô nhất, hãy chọn màu có số lớn nhất trong số đó.

Dữ liệu vào

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

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

Dữ liệu ra

In ra một dòng chứa hai số nguyên, cách nhau bởi một dấu cách: số của màu xuất hiện trên nhiều ô nhất và số ô được tô màu đó, theo đúng thứ tự này. Nếu có nhiều màu cùng xuất hiện trên nhiều ô nhất, hãy chọn màu có số lớn nhất.

Ràng buộc

• \(2 \le N \le 200\,000\).
• \(1 \le A_i \le 10^9\) (\(1 \le i \le N\)).
• \(1 \le B_j \le 10^9\) (\(1 \le j \le N\)).
• \(A_1=B_1\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. 15 điểm: \(N \le 500\), \(A_i \le 100\,000\) (\(1 \le i \le N\)), \(B_j \le 100\,000\) (\(1 \le j \le N\)).
2. 10 điểm: \(N \le 500\).
3. 20 điểm: \(A_i \le 2\) (\(1 \le i \le N\)), \(B_j \le 2\) (\(1 \le j \le N\)).
4. 25 điểm: \(A_i<A_{i+1}\) (\(1 \le i \le N-1\)), \(B_j<B_{j+1}\) (\(1 \le j \le N-1\)).
5. 30 điểm: Không có ràng buộc bổ sung.

Ví dụ

3
5 2 5
5 3 1

5 4

3
1 7 8
1 3 5

8 3

4
2 1 2 1
2 1 1 2

2 10

Nguồn

Đề bài Grid Coloring, JOI 2024/2025, vòng chung kết quốc gia, bài 1 (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.

Dũng sĩ Bitaro lên đường phiêu lưu để đánh bại các quái vật.

Bitaro có một giá trị gọi là sức mạnh, với giá trị ban đầu là \(x\). Có \(N\) quái vật, được đánh số từ \(1\) đến \(N\). Để đánh bại quái vật \(i\) (\(1 \le i \le N\)), sức mạnh của Bitaro phải ít nhất là \(A_i\). Sau khi đánh bại quái vật này, sức mạnh của Bitaro tăng thêm \(B_i\).

Bitaro muốn đánh bại tất cả quái vật theo cách sau:

1. Chọn một quái vật \(j\) (\(1 \le j \le N\)) làm điểm bắt đầu, rồi lần lượt đánh bại các quái vật \(j,j+1,\ldots,N\) theo đúng thứ tự này.
2. Sau đó, nếu \(j \ge 2\), lần lượt đánh bại các quái vật \(1,2,\ldots,j-1\) theo đúng thứ tự này.

Cho thông tin về các quái vật, hãy tìm giá trị sức mạnh ban đầu \(x\) nhỏ nhất để Bitaro có thể đánh bại tất cả quái vật.

Dữ liệu vào

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

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

Dữ liệu ra

In ra một dòng chứa một số nguyên là giá trị sức mạnh ban đầu \(x\) nhỏ nhất để Bitaro có thể đánh bại tất cả quái vật.

Ràng buộc

• \(2 \le N \le 500\,000\).
• \(0 \le A_i \le 10^9\) (\(1 \le i \le N\)).
• \(0 \le B_i \le 10^9\) (\(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. 10 điểm: \(N \le 2\,000\) và giá trị sức mạnh ban đầu nhỏ nhất cần có không quá \(10\).
2. 21 điểm: \(N \le 2\,000\).
3. 19 điểm: Giá trị sức mạnh ban đầu nhỏ nhất cần có không quá \(10\).
4. 22 điểm: \(B_i=1\) (\(1 \le i \le N\)).
5. 28 điểm: Không có ràng buộc bổ sung.

Ví dụ

5
1 3 2 8 6
4 3 1 1 2

1

5
1 6 3 3 2
1 2 1 0 1

3

10
11 9 8 12 7 7 8 12 9 10
1 1 1 1 1 1 1 1 1 1

9

7
1125 638 0 37 737 820 1202
23 984 558 350 52 345 580

0

Nguồn

Đề bài Bitaro the Brave 2, JOI 2024/2025, vòng chung kết quốc gia, bài 2 (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.

La Paz, thủ đô của Bolivia, nổi tiếng không chỉ là một điểm du lịch mà còn nhờ mạng lưới cáp treo mang tên Mi Teleférico. Bạn đến La Paz du lịch và muốn tham quan càng nhiều nơi càng tốt. Trong bài toán này, ta xét tình huống được đơn giản hóa như sau.

La Paz có \(N\) ga cáp treo, được đánh số từ \(1\) đến \(N\) theo thứ tự độ cao tăng dần. Có \(M\) tuyến cáp treo một chiều, được đánh số từ \(1\) đến \(M\), và \(P\) công ty cáp treo, được đánh số từ \(1\) đến \(P\). Mỗi tuyến do một công ty quản lý. Tuyến \(i\) (\(1 \le i \le M\)) đi từ ga \(A_i\) đến ga \(B_i\) và do công ty \(C_i\) quản lý. Mỗi tuyến luôn đi từ ga thấp hơn đến ga cao hơn, tức là \(A_i<B_i\).

Để thuận tiện cho hành khách, cơ quan giao thông La Paz phát hành vé đi không giới hạn. Trên mỗi vé có hai số nguyên \(l,r\) thỏa mãn \(1 \le l \le r \le P\). Vé cho phép người sở hữu đi các tuyến do các công ty \(l,l+1,\ldots,r\) quản lý. Nói cách khác, với \(1 \le i \le M\), có thể dùng vé để đi tuyến \(i\) nếu \(l \le C_i \le r\). Một vé có thể được dùng cho nhiều tuyến. Ta gọi vé này là vé \((l,r)\).

Có \(Q\) du khách đến La Paz, được đánh số từ \(1\) đến \(Q\). Du khách \(j\) (\(1 \le j \le Q\)) có vé \((L_j,R_j)\) và \(X_j\) boliviano tiền mặt.

Mục tiêu của mỗi du khách là bảo đảm rằng từ ga \(1\) có thể đi đến từng ga, chỉ sử dụng các tuyến mà vé của mình cho phép đi. Để đạt mục tiêu này, du khách \(j\) (\(1 \le j \le Q\)) có thể đổi vé theo các bước sau, nhưng mỗi người chỉ được đổi tối đa một lần:

1. Chọn hai số nguyên \(l',r'\) thỏa mãn \(1 \le l' \le r' \le P\).
2. Đổi vé \((L_j,R_j)\) lấy vé \((l',r')\), với phí đổi vé là \(|L_j-l'|+|R_j-r'|\) boliviano.

Cho thông tin về các ga, các tuyến và các du khách, hãy xác định với từng du khách liệu họ có thể đạt được mục tiêu mà không chi quá số tiền mặt đang có hay không.

Dữ liệu vào

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

N M P
A_1 B_1 C_1
A_2 B_2 C_2
...
A_M B_M C_M
Q
L_1 R_1 X_1
L_2 R_2 X_2
...
L_Q R_Q X_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa Yes nếu du khách \(j\) có thể đạt được mục tiêu trong phạm vi số tiền đang có, hoặc No nếu không thể.

Ràng buộc

• \(2 \le N \le 300\,000\).
• \(1 \le M \le 300\,000\).
• \(1 \le P \le 10^9\).
• \(1 \le A_i<B_i \le N\) (\(1 \le i \le M\)).
• \(1 \le C_i \le P\) (\(1 \le i \le M\)).
• \(1 \le Q \le 400\,000\).
• \(1 \le L_j \le R_j \le P\) (\(1 \le j \le Q\)).
• \(0 \le X_j \le 10^9\) (\(1 \le j \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. 7 điểm: \(N \le 50\), \(M \le 50\), \(Q \le 50\), \(X_j=0\) (\(1 \le j \le Q\)).
2. 8 điểm: \(P \le 10\).
3. 11 điểm: \(P \le 100\).
4. 23 điểm: \(P \le 300\,000\), \(X_j=0\) (\(1 \le j \le Q\)).
5. 9 điểm: \(P \le 300\,000\).
6. 22 điểm: \(N \le 8\,000\), \(M \le 8\,000\).
7. 20 điểm: Không có ràng buộc bổ sung.

Ví dụ

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

Yes
No
No
Yes

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

Yes
No
Yes

3 1 1000000000
1 2 6
1
1 1000000000 1000000000

No

5 9 2000
2 3 1814
2 3 457
1 2 1226
3 4 1354
1 5 1050
1 2 1725
2 3 1383
1 5 1626
1 4 1795
5
850 1872 128
82 428 1217
487 924 573
1639 1926 202
202 420 25

Yes
Yes
Yes
Yes
No

Nguồn

Đề bài Mi Teleférico, JOI 2024/2025, vòng chung kết quốc gia, bài 3 (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.

Công ty Just Odd Inventions nổi tiếng với những phát minh kỳ lạ. Trong bài toán này, ta gọi tắt công ty là JOI.

Nhân dịp kỷ niệm \(5\) năm ra mắt sản phẩm chủ lực "Cà vạt chỉ dài", công ty JOI đã phát triển sản phẩm mới "Cà vạt chỉ có thể dài thêm". Đúng như tên gọi, loại cà vạt mới này có đặc điểm là có thể kéo dài tùy ý, không có giới hạn.

Để quảng bá sản phẩm mới, công ty JOI quyết định tổ chức một buổi giới thiệu và chọn bạn làm người dẫn chương trình. Đầu tiên, một số người mẫu đeo loại cà vạt mới sẽ bước lên sân khấu. Ban đầu, cà vạt của tất cả người mẫu đều có độ dài bằng \(1\).

Sau đó, bạn thực hiện tổng cộng \(N\) màn trình diễn để khán giả thấy được khả năng kéo dài của cà vạt. Trong mỗi màn trình diễn, trước tiên bạn mời khán giả hô lên một số tùy ý, gọi số đó là \(x\). Tiếp theo, bạn chọn đáp lại hoặc bỏ qua số vừa được hô lên.

Nếu chọn đáp lại, bạn phải chọn một người mẫu trên sân khấu có cà vạt với độ dài hiện tại không vượt quá \(x\), rồi đặt độ dài cà vạt của người đó thành đúng \(x\). Bạn cũng được phép chọn người mẫu có cà vạt vốn đã dài đúng \(x\). Tuy nhiên, nếu không có người mẫu nào có thể được chọn thì buổi giới thiệu thất bại. Nếu chọn bỏ qua, bạn không làm gì cả.

Tuy nhiên, nếu bạn bỏ qua số khán giả hô lên từ hai lần liên tiếp trở lên, khán giả sẽ tức giận và buổi giới thiệu cũng thất bại.

Số người mẫu xuất hiện trên sân khấu, ký hiệu là \(k\) (\(k \ge 1\)), vẫn chưa được quyết định. Vì việc thuê người mẫu tốn nhiều tiền, công ty muốn \(k\) nhỏ nhất có thể. Số người mẫu tối thiểu cần có để buổi giới thiệu không thất bại phụ thuộc vào các số mà khán giả hô lên trong từng màn trình diễn. May mắn thay, bạn có khả năng tiên tri và biết trước rằng ở màn trình diễn thứ \(i\) (\(1 \le i \le N\)), khán giả sẽ hô lên số \(A_i\).

Cho thông tin về các số khán giả sẽ hô lên, hãy tìm số người mẫu \(k\) nhỏ nhất cần có để buổi giới thiệu không thất bại.

Dữ liệu vào

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

N
A_1 A_2 ... A_N

Dữ liệu ra

In trên một dòng số người mẫu \(k\) nhỏ nhất cần có để buổi giới thiệu không thất bại.

Ràng buộc

• \(2 \le N \le 5\,000\,000\).
• \(1 \le A_i \le 21\) (\(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. \(10\) điểm: \(N \le 15\).
2. \(6\) điểm: \(N \le 500\), \(A_i \le 2\) với mọi \(1 \le i \le N\).
3. \(12\) điểm: \(N \le 500\), \(A_i \le 5\) với mọi \(1 \le i \le N\).
4. \(18\) điểm: \(N \le 500\), \(A_i \le 15\) với mọi \(1 \le i \le N\).
5. \(26\) điểm: \(N \le 500\,000\), \(A_i \le 15\) với mọi \(1 \le i \le N\).
6. \(10\) điểm: \(N \le 500\,000\).
7. \(18\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5
5 3 4 2 1

2

6
2 1 1 2 2 1

1

10
2 4 6 7 4 5 5 3 4 1

3

Nguồn

Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề 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.

Đất nước JOI có \(N\) bưu điện, được đánh số từ \(1\) đến \(N\). Mỗi bưu điện được chỉ định đúng một bưu điện để gửi hàng đến: bưu điện \(i\) gửi hàng đến bưu điện \(P_i\). Có thể xảy ra trường hợp \(P_i = i\).

Nếu một kiện hàng được gửi đi từ bưu điện \(i\) vào thời điểm \(t\), kiện hàng đó sẽ đến bưu điện \(P_i\) vào thời điểm \(t + 1\). Tuy nhiên, trong thời gian đang gửi một kiện hàng, bưu điện đó không thể gửi đi một kiện hàng khác. Mỗi bưu điện có thể lưu giữ số lượng kiện hàng không giới hạn tại bất kỳ thời điểm nào.

Hiện có \(M\) kiện hàng cần được chuyển ở đất nước JOI. Kiện hàng thứ \(j\) đến bưu điện \(A_j\) vào thời điểm \(0\) và cuối cùng phải được chuyển đến bưu điện \(B_j\) đã được chỉ định.

Cho thông tin về các bưu điện và các kiện hàng, hãy xác định có thể chuyển tất cả các kiện hàng đến đúng bưu điện được chỉ định hay không. Nếu có thể, hãy tìm thời điểm sớm nhất mà kiện hàng cuối cùng đến được bưu điện được chỉ định của nó.

Dữ liệu vào

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

N
P_1 P_2 ... P_N
M
A_1 B_1
A_2 B_2
...
A_M B_M

Dữ liệu ra

In trên một dòng thời điểm sớm nhất mà kiện hàng cuối cùng đến được bưu điện được chỉ định của nó, nếu có thể chuyển tất cả các kiện hàng đến đúng nơi. Nếu không thể, in ra -1.

Ràng buộc

• \(2 \le N \le 200\,000\).
• \(1 \le M \le 200\,000\).
• \(1 \le P_i \le N\) (\(1 \le i \le N\)).
• \(1 \le A_j, B_j \le N\) (\(1 \le j \le M\)).
• \(A_j \ne B_j\) (\(1 \le j \le M\)).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(3\) điểm: \(N \le 3000\), \(M = 1\).
2. \(9\) điểm: \(N \le 3000\), \(M \le 3000\).
3. \(13\) điểm: \(P = (1, 1, 2, \ldots, N - 1)\) và \(\max(B_1, B_2, \ldots, B_M) < \min(A_1, A_2, \ldots, A_M)\).
4. \(25\) điểm: \(P = (1, 1, 2, \ldots, N - 1)\).
5. \(11\) điểm: \(P = (N, 1, 2, \ldots, N - 1)\).
6. \(25\) điểm: \(P_1 = 1\), \(P_i < i\) với mọi \(2 \le i \le N\).
7. \(14\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

3

3
2 1 3
1
1 3

-1

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

5

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

4

7
1 1 1 3 3 4 4
5
6 1
6 3
7 1
5 1
5 1

5

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

6

Nguồn

Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề 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.