JOI 2019 - Vòng chung kết

Bitaro Dũng Cảm đang đối mặt với Quỷ Vương. Để tấn công, Bitaro đặt các viên ngọc, quả cầu và thỏi kim loại lên một bảng gồm \(H\) hàng và \(W\) cột rồi niệm phép. Ô ở hàng thứ \(i\) từ trên xuống và cột thứ \(j\) từ trái sang phải được ký hiệu là \((i,j)\).

Bitaro đã đặt đúng một vật thuộc một trong ba loại trên vào mỗi ô. Sức mạnh của phép thuật bằng số bộ bốn số nguyên \((i,j,k,\ell)\) thỏa mãn \(1 \le i < k \le H\), \(1 \le j < \ell \le W\) và điều kiện sau: ô \((i,j)\) chứa một viên ngọc, ô \((i,\ell)\) chứa một quả cầu, còn ô \((k,j)\) chứa một thỏi kim loại.

Cho cách sắp xếp các vật trên bảng, hãy tính sức mạnh của phép thuật mà Bitaro niệm.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(H\) và \(W\).

Trong \(H\) dòng tiếp theo, dòng thứ \(i\) chứa chuỗi \(S_i\) có độ dài \(W\), mô tả hàng thứ \(i\). Ký tự thứ \(j\) của \(S_i\) là J nếu ô \((i,j)\) chứa một viên ngọc, O nếu chứa một quả cầu và I nếu chứa một thỏi kim loại.

Dữ liệu ra

In ra một dòng chứa sức mạnh của phép thuật.

Ràng buộc

• \(2 \le H,W \le 3000\).
• Mỗi chuỗi \(S_i\) có độ dài \(W\) và chỉ chứa các ký tự J, O, I.

Phân nhóm

1. \(20\) điểm: \(2 \le H,W \le 100\); mỗi \(S_i\) có độ dài \(W\) và chỉ gồm J, O, I.
2. \(30\) điểm: \(2 \le H,W \le 500\); mỗi \(S_i\) có độ dài \(W\) và chỉ gồm J, O, I.
3. \(50\) điểm: \(2 \le H,W \le 3000\); mỗi \(S_i\) có độ dài \(W\) và chỉ gồm J, O, I.

Ví dụ

3 4
JOIJ
JIOO
IIII

3

4 4
JJOO
JJOO
IIJO
IIIJ

17

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2018/2019, bài 1. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bạn dự định tổ chức một triển lãm tranh. Trong triển lãm, bạn sẽ đặt một số bức tranh vào khung rồi trưng bày chúng thành một hàng.

Có \(N\) bức tranh có thể được chọn, đánh số từ \(1\) đến \(N\). Bức tranh \(i\) có kích thước \(S_i\) và giá trị \(V_i\). Có \(M\) khung tranh, đánh số từ \(1\) đến \(M\). Khung \(j\) có kích thước \(C_j\) và chỉ chứa được tranh có kích thước không vượt quá \(C_j\). Mỗi khung chứa nhiều nhất một bức tranh.

Mỗi bức tranh được trưng bày phải được đặt trong một khung. Để triển lãm trông đẹp mắt, cách sắp xếp phải thỏa mãn:

• Với hai bức tranh bất kỳ đứng cạnh nhau, kích thước khung của bức bên phải không nhỏ hơn kích thước khung của bức bên trái.
• Với hai bức tranh bất kỳ đứng cạnh nhau, giá trị của bức bên phải không nhỏ hơn giá trị của bức bên trái.

Hãy tính số bức tranh lớn nhất có thể trưng bày.

Dữ liệu vào

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

N M
S_1 V_1
...
S_N V_N
C_1
...
C_M

Dữ liệu ra

In ra một dòng chứa số bức tranh lớn nhất có thể trưng bày.

Ràng buộc

• Các giá trị đầu vào đều là số nguyên.
• \(1 \le N,M \le 100000\).
• \(1 \le S_i,V_i \le 10^9\) với \(1 \le i \le N\).
• \(1 \le C_j \le 10^9\) với \(1 \le j \le M\).

Phân nhóm

Các ràng buộc chung ở trên áp dụng cho mọi nhóm.

1. \(10\) điểm: \(1 \le N,M \le 10\).
2. \(40\) điểm: \(1 \le N,M \le 1000\).
3. \(50\) điểm: \(1 \le N,M \le 100000\).

Ví dụ

3 4
10 20
5 1
3 5
4
6
10
4

2

3 2
1 2
1 2
1 2
1
1

2

4 2
28 1
8 8
6 10
16 9
4
3

0

8 8
508917604 35617051
501958939 840246141
485338402 32896484
957730250 357542366
904165504 137209882
684085683 775621730
552953629 20004459
125090903 607302990
433255278
979756183
28423637
856448848
276518245
314201319
666094038
149542543

3

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2018/2019, bài 2. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

JOI là người giỏi làm vườn tại nhà. Cậu trồng cỏ Joy trong khu vườn của mình. Có \(N\) chậu cây được xếp thành một hàng theo hướng đông-tây, đánh số từ \(1\) đến \(N\) tính từ đầu phía tây. Có \(N\) cây cỏ Joy, mỗi chậu trồng một cây.

Vào mùa xuân, trái với dự đoán, JOI nhận thấy cỏ Joy mọc lá có nhiều màu khác nhau. Cậu còn thấy cây không phát triển tốt như mong đợi. Tra cứu sách, cậu biết được rằng:

• Có ba loại cỏ Joy, lần lượt có lá màu đỏ, xanh lá và vàng.
• Nếu các cây cỏ Joy có cùng màu lá được đặt gần nhau, sự phát triển của chúng sẽ bị cản trở.

Vì vậy, JOI quyết định sắp xếp lại sao cho không có hai cây cùng màu lá đứng cạnh nhau. Do các chậu rất nặng, trong mỗi thao tác cậu chỉ có thể hoán đổi hai cây ở hai chậu kề nhau. Cụ thể, cậu chọn một chỉ số \(i\) với \(1 \le i \le N-1\) rồi hoán đổi cây ở chậu \(i\) và chậu \(i+1\).

Hãy tính số thao tác ít nhất cần thực hiện để không có hai cây cùng màu lá đứng cạnh nhau.

Dữ liệu vào

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

N
S

\(S\) là chuỗi độ dài \(N\). Ký tự thứ \(i\) là R, G hoặc Y nếu cây ở chậu \(i\) có lá lần lượt màu đỏ, xanh lá hoặc vàng.

Dữ liệu ra

In ra một dòng chứa số thao tác ít nhất cần thực hiện. Nếu không thể sắp xếp để không có hai cây cùng màu lá đứng cạnh nhau, in ra \(-1\).

Ràng buộc

• \(N\) là số nguyên và \(1 \le N \le 400\).
• \(S\) có độ dài \(N\).
• Mỗi ký tự của \(S\) là R, G hoặc Y.

Phân nhóm

1. \(5\) điểm: \(1 \le N \le 15\); \(S\) có độ dài \(N\) và chỉ gồm R, G, Y.
2. \(55\) điểm: \(1 \le N \le 60\); \(S\) có độ dài \(N\) và chỉ gồm R, G, Y.
3. \(15\) điểm: \(1 \le N \le 400\); \(S\) có độ dài \(N\) và chỉ gồm R, G.
4. \(25\) điểm: \(1 \le N \le 400\); \(S\) có độ dài \(N\) và chỉ gồm R, G, Y.

Ví dụ

5
RRGYY

2

6
RRRRRG

-1

20
YYGYYYGGGGRGYYGRGRYG

8

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2018/2019, bài 3. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Ông JOI có một chiếc bàn rất lớn trong phòng trưng bày bộ sưu tập, trên đó đặt nhiều đồng xu quý hiếm. Để dọn bàn, ông muốn sắp xếp lại các đồng xu.

Chiếc bàn được xem như một lưới gồm \(2000000001 \times 2000000001\) ô. Các cột được đánh số từ \(-10^9\) đến \(10^9\) từ trái sang phải, còn các hàng được đánh số từ \(-10^9\) đến \(10^9\) từ dưới lên trên. Ô ở cột \(x\), hàng \(y\) được ký hiệu là \((x,y)\).

Có \(2N\) đồng xu. Ban đầu, đồng xu thứ \(i\) nằm tại ô \((X_i,Y_i)\). Mục tiêu của ông JOI là đặt một đồng xu vào mỗi ô \((x,y)\) thỏa mãn \(1 \le x \le N\) và \(1 \le y \le 2\).

Để tránh làm hỏng đồng xu, thao tác duy nhất ông có thể thực hiện là chọn một đồng xu rồi chuyển nó sang một ô kề cạnh. Hai ô kề cạnh khi và chỉ khi chúng có chung một cạnh. Trong quá trình di chuyển, nhiều đồng xu được phép nằm trên cùng một ô.

Hãy tính số thao tác ít nhất cần thực hiện để đạt được mục tiêu.

Dữ liệu vào

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

N
X_1 Y_1
...
X_{2N} Y_{2N}

Dữ liệu ra

In ra một dòng chứa số thao tác ít nhất cần thực hiện.

Ràng buộc

• Các giá trị đầu vào đều là số nguyên.
• \(1 \le N \le 100000\).
• \(-10^9 \le X_i,Y_i \le 10^9\) với \(1 \le i \le 2N\).

Phân nhóm

1. \(8\) điểm: \(1 \le N \le 10\); \(-10^9 \le X_i,Y_i \le 10^9\) với \(1 \le i \le 2N\).
2. \(29\) điểm: \(1 \le N \le 1000\); \(-10^9 \le X_i,Y_i \le 10^9\) với \(1 \le i \le 2N\).
3. \(63\) điểm: \(1 \le N \le 100000\); \(-10^9 \le X_i,Y_i \le 10^9\) với \(1 \le i \le 2N\).

Ví dụ

3
0 0
0 4
4 0
2 1
2 5
-1 1

15

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

9

5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3

8000000029

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2018/2019, bài 4. Đề 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\) thành phố, đánh số từ \(1\) đến \(N\), được nối với nhau bởi \(N-1\) con đường. Con đường thứ \(i\) nối hai thành phố \(A_i\) và \(B_i\), cho phép đi lại theo cả hai chiều. Từ một thành phố bất kỳ có thể đi đến mọi thành phố khác bằng các con đường này.

Đất nước JOI có một số loại đặc sản địa phương. Mỗi loại đặc sản được gán một số nguyên từ \(1\) đến \(M\); một số số nguyên trong khoảng này có thể không tương ứng với loại đặc sản nào. Mỗi thành phố sản xuất đúng một loại đặc sản. Thành phố \(j\) sản xuất đặc sản \(C_j\). Nhiều thành phố có thể sản xuất cùng một loại đặc sản.

Khoảng cách giữa hai thành phố là số con đường ít nhất cần đi qua để đến thành phố này từ thành phố kia. Với một thành phố \(x\), một thành phố \(y \ne x\) được gọi là thành phố độc nhất đối với \(x\) nếu với mọi thành phố \(z\) khác cả \(x\) và \(y\), khoảng cách từ \(x\) đến \(y\) khác khoảng cách từ \(x\) đến \(z\). Nói cách khác, không có thành phố nào khác có cùng khoảng cách đến \(x\) như \(y\).

Ông K, Bộ trưởng Giao thông của đất nước JOI, muốn biết với mỗi thành phố \(j\), có bao nhiêu loại đặc sản khác nhau được sản xuất tại các thành phố độc nhất đối với \(j\).

Hãy tính các giá trị này từ thông tin về đường sá và đặc sản của từng thành phố.

Dữ liệu vào

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

N M
A_1 B_1
...
A_{N-1} B_{N-1}
C_1 C_2 ... C_N

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(j\) chứa số loại đặc sản khác nhau được sản xuất tại các thành phố độc nhất đối với thành phố \(j\).

Ràng buộc

• Các giá trị đầu vào đều là số nguyên.
• \(2 \le N \le 200000\).
• \(1 \le M \le N\).
• \(1 \le A_i,B_i \le N\) và \(A_i \ne B_i\) với \(1 \le i \le N-1\).
• Từ một thành phố bất kỳ có thể đi đến mọi thành phố khác bằng các con đường đã cho.
• \(1 \le C_j \le M\) với \(1 \le j \le N\).

Phân nhóm

Các điều kiện về đường sá và phạm vi \(C_j\) trong phần ràng buộc chung áp dụng cho mọi nhóm.

1. \(4\) điểm: \(2 \le N \le 2000\), \(1 \le M \le N\).
2. \(32\) điểm: \(2 \le N \le 200000\), \(M=1\), \(C_j=1\) với mọi \(1 \le j \le N\).
3. \(32\) điểm: \(2 \le N \le 200000\), \(M=N\), \(C_j=j\) với mọi \(1 \le j \le N\).
4. \(32\) điểm: \(2 \le N \le 200000\), \(1 \le M \le N\).

Ví dụ

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

2
0
1
1
1

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

1
1
1
0
1
1
1

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

4
3
4
2
0
2
2
0
3
2

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

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

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2018/2019, bài 5. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.