JOI 2016/2017 - Vòng chung kết - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2017 - Foehn Phenomena	100 (p)	1.0s	256M
2	JOI 2017 - Semiexpress	100 (p)	1.0s	256M
3	JOI 2017 - The Kingdom of JOIOI	100 (p)	4.0s	256M
4	JOI 2017 - Soccer	100 (p)	3.0s	256M
5	JOI 2017 - Rope	100 (p)	2.5s	256M

1. JOI 2017 - Foehn Phenomena

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Ở Vương quốc IOI, gió luôn thổi từ biển vào đất liền. Có \(N+1\) địa điểm được đánh số từ \(0\) đến \(N\) theo hướng gió thổi. Nhà của ông JOI nằm tại địa điểm \(N\). Độ cao của địa điểm \(0\) là \(A_0=0\), còn độ cao của địa điểm \(i\) là \(A_i\).

Gió chuyển động sát mặt đất. Nhiệt độ gió tại địa điểm \(0\), nơi gần biển nhất, là \(0\) độ. Với mỗi \(0\le i<N\), nhiệt độ thay đổi từ địa điểm \(i\) đến địa điểm \(i+1\) như sau:

Nếu \(A_i<A_{i+1}\), nhiệt độ giảm \(S\) độ trên mỗi đơn vị độ cao tăng lên.
Nếu \(A_i\ge A_{i+1}\), nhiệt độ tăng \(T\) độ trên mỗi đơn vị độ cao giảm xuống.

Hoạt động kiến tạo ở Vương quốc IOI rất mạnh. Bạn có dữ liệu về chuyển động kiến tạo trong \(Q\) ngày. Vào ngày thứ \(j\), độ cao của mọi địa điểm \(k\) với \(L_j\le k\le R_j\) thay đổi thêm \(X_j\). Nếu \(X_j\ge 0\), độ cao tăng \(X_j\); nếu \(X_j<0\), độ cao giảm \(|X_j|\).

Hãy tính nhiệt độ gió tại nhà ông JOI sau chuyển động kiến tạo của từng ngày.

Dữ liệu vào

Dòng đầu chứa bốn số nguyên \(N,Q,S,T\).
\(N+1\) dòng tiếp theo lần lượt chứa \(A_0,A_1,\ldots,A_N\); mỗi số nằm trên một dòng.
\(Q\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(L_j,R_j,X_j\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) chứa nhiệt độ gió tại nhà ông JOI sau chuyển động kiến tạo ngày thứ \(j\).

Ràng buộc

\(1\le N,Q\le 200\,000\).
\(1\le S,T\le 1\,000\,000\).
\(A_0=0\).
\(-1\,000\,000\le A_i\le 1\,000\,000\) với \(1\le i\le N\).
\(1\le L_j\le R_j\le N\).
\(-1\,000\,000\le X_j\le 1\,000\,000\).

Phân nhóm

\(30\) điểm: \(N\le 2\,000\) và \(Q\le 2\,000\)
\(10\) điểm: \(S=T\)
\(60\) điểm: Không có ràng buộc bổ sung

Ví dụ

Ví dụ 1

Input

Output

-5
-7
-13
-13
-18

Giải thích

Ban đầu, độ cao tại các địa điểm \(0,1,2,3\) lần lượt là \(0,4,1,8\). Sau chuyển động kiến tạo ngày đầu tiên, chúng trở thành \(0,6,3,8\); nhiệt độ gió tại các địa điểm tương ứng là \(0,-6,0,-5\).

Ví dụ 2

Input

Output

5
-35

Giải thích

Ví dụ này thỏa mãn ràng buộc của nhóm 2.

Ví dụ 3

Input

Output

Nguồn

JOI 2016/2017, Vòng chung kết.

2. JOI 2017 - Semiexpress

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Đường sắt JOI có \(N\) ga được đánh số từ \(1\) đến \(N\) dọc theo một tuyến đường. Hiện có tàu nhanh và tàu thường.

Tàu thường dừng tại mọi ga và mất \(A\) phút để đi giữa hai ga liên tiếp. Tàu nhanh chỉ dừng tại \(S_1,S_2,\ldots,S_M\), trong đó

\[ 1=S_1<S_2<\cdots<S_M=N, \]

và mất \(B\) phút để đi giữa hai ga liên tiếp.

Đường sắt JOI dự định vận hành tàu bán nhanh, mất \(C\) phút giữa hai ga liên tiếp. Các ga dừng của tàu bán nhanh phải gồm mọi ga tàu nhanh dừng và có đúng \(K\) ga.

Đường sắt JOI muốn chọn các ga dừng sao cho số ga khác ga \(1\) có thể đến từ ga \(1\) trong không quá \(T\) phút là lớn nhất. Không tính thời gian tàu dừng. Chỉ được đi theo chiều số ga tăng dần; tại một ga mà nhiều loại tàu cùng dừng, hành khách có thể chuyển giữa các tàu đó.

Hãy tính số ga lớn nhất có thể đến trong giới hạn thời gian.

Dữ liệu vào

Dòng đầu chứa \(N,M,K\).
Dòng thứ hai chứa \(A,B,C\).
Dòng thứ ba chứa \(T\).
\(M\) dòng tiếp theo lần lượt chứa \(S_1,S_2,\ldots,S_M\); mỗi số nằm trên một dòng.

Dữ liệu ra

In số ga lớn nhất thỏa mãn điều kiện thời gian.

Ràng buộc

\(2\le N\le 1\,000\,000\,000\).
\(2\le M\le K\le 3\,000\) và \(K\le N\).
\(1\le B<C<A\le 1\,000\,000\,000\).
\(1\le T\le 10^{18}\).
\(1=S_1<S_2<\cdots<S_M=N\).

Phân nhóm

\(18\) điểm: \(N\le 300\), \(K-M=2\), \(A\le 1\,000\,000\), \(T\le 1\,000\,000\,000\)
\(30\) điểm: \(N\le 300\)
\(52\) điểm: Không có ràng buộc bổ sung

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Nếu tàu bán nhanh dừng tại \(1,5,6,8,10\), ta đến được mọi ga từ \(2\) đến \(10\) trừ ga \(9\) trong \(30\) phút. Đến ga \(3\) bằng tàu thường mất \(20\) phút. Đến ga \(7\) bằng tàu nhanh tới ga \(6\) rồi tàu thường mất \(25\) phút. Đến ga \(8\) bằng tàu nhanh tới ga \(6\) rồi tàu bán nhanh cũng mất \(25\) phút. Đến ga \(9\) nhanh nhất mất \(35\) phút: tàu nhanh tới \(6\), tàu bán nhanh tới \(8\), rồi tàu thường tới \(9\).

Ví dụ 2

Input

Output

Ví dụ 3

Input

90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90

Output

Ví dụ 4

Input

Output

Giải thích

Ví dụ này không thỏa mãn ràng buộc của nhóm 1.

Ví dụ 5

Input

300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300

Output

Giải thích

Ví dụ này không thỏa mãn ràng buộc của nhóm 1.

Ví dụ 6

Input

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

Output

Giải thích

Ví dụ này không thỏa mãn ràng buộc của nhóm 1 hoặc nhóm 2.

Nguồn

JOI 2016/2017, Vòng chung kết.

3. JOI 2017 - The Kingdom of JOIOI

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Vương quốc JOIOI là một bảng chữ nhật gồm \(H\times W\) ô. Để nâng cao hiệu quả quản lý, vương quốc sẽ được chia thành hai vùng mang tên JOI và IOI. Cách chia phải thỏa mãn:

Mỗi vùng chứa ít nhất một ô và mỗi ô thuộc đúng một vùng.
Giữa hai ô bất kỳ của cùng một vùng, có thể đi qua các ô của vùng đó bằng các bước giữa hai ô chung cạnh.
Trên mỗi hàng hoặc cột, các ô thuộc mỗi vùng phải liên thông. Một hàng hoặc cột có thể hoàn toàn thuộc một vùng.

Mỗi ô có một độ cao nguyên. Với mỗi vùng, xét hiệu giữa độ cao lớn nhất và nhỏ nhất trong vùng. Hãy chia vương quốc hợp lệ sao cho giá trị lớn hơn trong hai hiệu này là nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa \(H,W\).
\(H\) dòng tiếp theo, dòng thứ \(i\) chứa \(W\) số nguyên \(A_{i,1},A_{i,2},\ldots,A_{i,W}\).

Dữ liệu ra

In giá trị nhỏ nhất có thể của hiệu độ cao lớn nhất trong hai vùng.

Ràng buộc

\(2\le H,W\le 2\,000\).
\(1\le A_{i,j}\le 1\,000\,000\,000\).

Phân nhóm

\(15\) điểm: \(H\le 10\) và \(W\le 10\)
\(45\) điểm: \(H\le 200\) và \(W\le 200\)
\(40\) điểm: Không có ràng buộc bổ sung

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Một cách chia tối ưu, viết J cho vùng JOI và I cho vùng IOI, là:

J J J I
J J J I
J J I I
J I I I

Cách chia sau không hợp lệ vì các ô I trên cột thứ ba không liên thông:

J J I I
J J J I
J J J I
J I I I

Ví dụ 2

Input

8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16

Output

Nguồn

JOI 2016/2017, Vòng chung kết.

4. JOI 2017 - Soccer

Điểm: 100 (p) Thời gian: 3.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bạn là huấn luyện viên của một đội bóng đá danh tiếng trong giải JOI. Đội có \(N\) cầu thủ, đánh số từ \(1\) đến \(N\). Sân là hình chữ nhật cao \(H\) mét theo hướng bắc-nam và rộng \(W\) mét theo hướng đông-tây. Điểm \((i,j)\) cách góc tây bắc \(i\) mét về phía nam và \(j\) mét về phía đông.

Khi bắt đầu thu dọn sau buổi tập, cầu thủ \(i\) đứng tại \((S_i,T_i)\). Chỉ có một quả bóng và cầu thủ \(1\) đang giữ bóng. Bạn đứng cùng cầu thủ \(N\) tại \((S_N,T_N)\). Việc thu dọn kết thúc khi bóng được đưa tới \((S_N,T_N)\) và bạn bắt được bóng. Bạn không di chuyển.

Mỗi hành động làm tăng mức mệt mỏi của cầu thủ thực hiện:

Nếu đang giữ bóng, cầu thủ chọn một trong bốn hướng và số nguyên dương \(p\), rồi sút bóng đúng \(p\) mét theo hướng đó. Cầu thủ đứng yên, mất quyền giữ bóng và tăng mệt mỏi thêm \(A\times p+B\).
Cầu thủ chọn một trong bốn hướng và di chuyển \(1\) mét. Nếu đang giữ bóng, cầu thủ mang bóng theo. Mức mệt mỏi tăng thêm \(C\).
Nếu đang giữ bóng, cầu thủ đặt bóng tại vị trí hiện tại và mất quyền giữ bóng. Mức mệt mỏi không đổi.
Nếu không ai giữ bóng, cầu thủ đứng cùng vị trí với bóng có thể nhặt bóng. Mức mệt mỏi không đổi.

Cầu thủ và bóng được phép ra ngoài sân; nhiều cầu thủ có thể đứng cùng một vị trí. Hãy tính tổng mức mệt mỏi nhỏ nhất để đưa bóng cho bạn.

Dữ liệu vào

Dòng đầu chứa \(H,W\).
Dòng thứ hai chứa \(A,B,C\).
Dòng thứ ba chứa \(N\).
\(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(S_i,T_i\).

Dữ liệu ra

In tổng mức mệt mỏi nhỏ nhất có thể.

Ràng buộc

\(1\le H,W\le 500\).
\(0\le A,B,C\le 1\,000\,000\,000\).
\(2\le N\le 100\,000\).
\(0\le S_i\le H\) và \(0\le T_i\le W\).
\((S_1,T_1)\ne(S_N,T_N)\).

Phân nhóm

\(5\) điểm: \(N=2\)
\(30\) điểm: \(N\le 1\,000\) và \(A=0\)
\(65\) điểm: Không có ràng buộc bổ sung

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Ví dụ này không thỏa mãn nhóm 1 hoặc nhóm 2. Ban đầu, cầu thủ \(1\) ở \((1,1)\) và giữ bóng, cầu thủ \(2\) ở \((0,4)\), còn cầu thủ \(3\) và bạn ở \((6,5)\).

Cầu thủ \(1\) sút bóng \(3\) mét về phía đông, tốn \(1\times3+3=6\). Bóng tới \((1,4)\).
Cầu thủ \(2\) đi \(1\) mét về phía nam rồi nhặt bóng, tốn \(6\).
Cầu thủ \(2\) đi \(1\) mét về phía đông, tốn \(6\).
Cầu thủ \(2\) sút bóng \(5\) mét về phía nam, tốn \(1\times5+3=8\). Bóng tới \((6,5)\).

Tổng mức mệt mỏi là \(26\) và đây là giá trị nhỏ nhất.

Ví dụ 2

Input

Output

Giải thích

Ví dụ này thỏa mãn nhóm 1 và nhóm 2. Không cần sút bóng.

Ví dụ 3

Input

Output

Giải thích

Ví dụ này thỏa mãn nhóm 1 và nhóm 2.

Ví dụ 4

Input

Output

Giải thích

Ví dụ này không thỏa mãn nhóm 1 nhưng thỏa mãn nhóm 2. Lưu ý rằng nhiều cầu thủ có thể đứng cùng một vị trí.

Nguồn

JOI 2016/2017, Vòng chung kết.

5. JOI 2017 - Rope

Điểm: 100 (p) Thời gian: 2.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

JOI đang chơi với một sợi dây dài \(N\), đặt thẳng từ trái sang phải. Dây gồm \(N\) đoạn nối liên tiếp; ban đầu mỗi đoạn dài \(1\), dày \(1\). Có tổng cộng \(M\) màu, và đoạn thứ \(i\) từ trái sang có màu \(C_i\).

JOI lặp lại thao tác sau cho tới khi dây còn dài \(2\). Gọi \(L\) là chiều dài hiện tại, chọn số nguyên \(j\) với \(1\le j<L\), rồi gập và ghép dây sao cho điểm cách đầu trái \(j\) đơn vị trở thành một đầu dây:

Nếu \(j\le L/2\), với mỗi \(1\le i\le j\), ghép đoạn thứ \(i\) từ trái với đoạn thứ \(2j-i+1\). Đầu phải cũ vẫn là đầu phải, và chiều dài mới là \(L-j\).
Nếu \(j>L/2\), với mỗi \(2j-L+1\le i\le j\), ghép đoạn thứ \(i\) từ trái với đoạn thứ \(2j-i+1\). Đầu trái cũ trở thành đầu phải, và chiều dài mới là \(j\).

Hai đoạn chỉ có thể ghép khi cùng màu. Trước khi ghép, JOI có thể đổi màu một đoạn với chi phí bằng độ dày của đoạn đó. Hai đoạn sau khi ghép trở thành một đoạn có độ dày bằng tổng độ dày ban đầu.

Với mỗi màu, hãy tính tổng chi phí nhỏ nhất để rút dây còn chiều dài \(2\) và trong hai đoạn cuối có một đoạn mang màu đó.

Dữ liệu vào

Dòng đầu chứa \(N,M\).
Dòng thứ hai chứa \(C_1,C_2,\ldots,C_N\).

Dữ liệu ra

In \(M\) dòng. Dòng thứ \(c\) chứa chi phí nhỏ nhất để dây cuối cùng có một đoạn màu \(c\).

Ràng buộc

\(2\le N\le 1\,000\,000\).
\(1\le M\le N\).
\(1\le C_i\le M\).
Với mỗi \(1\le c\le M\), tồn tại ít nhất một \(i\) sao cho \(C_i=c\).

Phân nhóm

\(15\) điểm: \(N\le 15\) và \(M\le 10\)
\(30\) điểm: \(N\le 100\,000\) và \(M\le 10\)
\(10\) điểm: \(N\le 100\,000\) và \(M\le 500\)
\(25\) điểm: \(M\le 5\,000\)
\(20\) điểm: Không có ràng buộc bổ sung

Ví dụ

Ví dụ 1

Input

5 3
1 2 3 3 2

Output

2
1
1

Giải thích

Để dây cuối cùng chứa màu \(1\), có thể đổi đoạn thứ hai thành màu \(1\), chọn \(j=1\), rồi đổi đoạn thứ tư của dây mới thành màu \(1\) và chọn \(j=2\). Dây cuối có màu \(3,1\), độ dày \(2,3\) và tổng chi phí là \(2\).

Để dây cuối chứa màu \(2\) hoặc \(3\), trước tiên chọn \(j=3\), thu được các màu \(3,2,1\) với độ dày \(2,2,1\). Đổi đoạn thứ ba thành màu \(2\) rồi chọn \(j=2\). Dây cuối có màu \(2,3\), độ dày \(3,2\) và tổng chi phí là \(1\).

Ví dụ 2

Input

7 3
1 2 2 1 3 3 3

Output

2
2
2

Giải thích

Để dây cuối chứa màu \(1\) với chi phí \(2\), lần lượt chọn \(j=2\); đổi đoạn ngoài cùng bên trái thành màu \(1\) rồi chọn \(j=1\) (đoạn này dày \(2\) nên việc đổi màu tốn \(2\)); chọn \(j=3\); cuối cùng chọn \(j=1\).

Ví dụ 3

Input

10 3
2 2 1 1 3 3 2 1 1 2

Output

3
3
4

Giải thích

Có thể cần đổi màu một số đoạn trước khi bắt đầu rút ngắn dây.

Nguồn

JOI 2016/2017, Vòng chung kết.