JOI 2015/2016 - 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 2016 - Oranges	100 (p)	1.0s	256M
2	JOI 2016 - Collecting Stamps 2	100 (p)	2.0s	256M
3	JOI 2016 - Train Fare	100 (p)	2.5s	256M
4	JOI 2016 - Territory	100 (p)	1.0s	256M
5	JOI 2016 - Geologic Fault	100 (p)	2.0s	256M

1. JOI 2016 - Oranges

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

JOI (Juicy Orange Industry) chuẩn bị đóng gói và vận chuyển \(N\) quả cam đang nằm trên băng chuyền, được đánh số từ 1 đến \(N\) theo thứ tự từ đầu băng chuyền. Kích thước quả cam \(i\) là \(A_i\).

Các quả cam phải được đóng vào một số hộp theo thứ tự. Mỗi hộp chỉ chứa một đoạn liên tiếp và chứa nhiều nhất \(M\) quả. Nếu một hộp chứa \(s\) quả, trong đó kích thước lớn nhất là \(a\) và nhỏ nhất là \(b\), chi phí của hộp là

\[ K+s(a-b). \]

\(K\) là chi phí cố định, như nhau với mọi hộp. Hãy tìm tổng chi phí nhỏ nhất để đóng gói toàn bộ cam.

Dữ liệu vào

Dòng đầu chứa \(N,M,K\).
\(N\) dòng tiếp theo: dòng \(i\) chứa \(A_i\).

Dữ liệu ra

In ra tổng chi phí nhỏ nhất.

Ràng buộc

\(1\le N\le20000\).
\(1\le M\le1000\) và \(M\le N\).
\(0\le K\le10^9\).
\(1\le A_i\le10^9\).

Phân nhóm

Nhóm 1 (20 điểm): \(N\le20\).
Nhóm 2 (50 điểm): \(N\le2000\), \(M\le100\).
Nhóm 3 (30 điểm): không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Đóng cam 1 đến 3 vào hộp đầu và cam 4 đến 6 vào hộp thứ hai cho chi phí

\[ (6+3(3-1))+(6+3(2-1))=21. \]

Ví dụ 2

Input

Output

Giải thích

Một phương án tối ưu dùng 11 hộp, lần lượt chứa \(1,3,1,1,3,1,1,2,1,1,1\) quả.

Ví dụ 3

Input

Output

Ví dụ 4

Input

10 1 1000000000
1
1
1
1
1
1
1
1
1
1

Output

10000000000

Giải thích

Kết quả có thể vượt miền số nguyên có dấu 32 bit.

Nguồn

Kỳ thi chung kết Olympic Tin học Nhật Bản 2015/2016, bài 1.

2. JOI 2016 - Collecting Stamps 2

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

Phố mua sắm JOI có \(N\) cửa hàng dọc theo một đại lộ một chiều, đánh số từ 1 đến \(N\) theo hướng từ lối vào tới lối ra. Mỗi cửa hàng đã chọn một con dấu J, O hoặc I.

Người tham gia cuộc sưu tập dấu vào đúng ba cửa hàng theo thứ tự trên phố. Nếu ba dấu trên thẻ lần lượt là J, O, I, họ nhận được phiếu quà tặng.

Một cửa hàng mới sẽ được mở tại một trong \(N+1\) vị trí: trước cửa hàng 1, giữa hai cửa hàng liên tiếp, hoặc sau cửa hàng \(N\). Cửa hàng mới cũng chọn một trong ba con dấu. Hãy chọn vị trí và con dấu để tối đa hóa số bộ ba cửa hàng mang lại phiếu quà tặng.

Dữ liệu vào

Dòng 1 chứa \(N\).
Dòng 2 chứa xâu \(S\) dài \(N\), chỉ gồm J, O, I; ký tự thứ \(i\) là dấu của cửa hàng \(i\).

Dữ liệu ra

In ra số bộ ba lớn nhất. Kết quả có thể vượt miền số nguyên có dấu 32 bit.

Ràng buộc

\[ 3\le N\le100000. \]

Phân nhóm

Nhóm 1 (30 điểm): \(N\le200\).
Nhóm 2 (20 điểm): \(N\le3000\).
Nhóm 3 (50 điểm): không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

5
JOIOI

Output

Giải thích

Nếu mở một cửa hàng dấu J giữa cửa hàng 1 và 2, dãy dấu là JJOIOI. Sáu bộ ba hợp lệ là \((1,3,4)\), \((1,3,6)\), \((1,5,6)\), \((2,3,4)\), \((2,3,6)\), \((2,5,6)\). Không thể đạt 7 bộ.

Ví dụ 2

Input

7
JJJOIII

Output

Ví dụ 3

Input

4
OIIJ

Output

Giải thích

Trong ví dụ 3, phương án tối ưu là mở một cửa hàng dấu J trước cửa hàng 1.

Nguồn

Kỳ thi chung kết Olympic Tin học Nhật Bản 2015/2016, bài 2.

3. JOI 2016 - Train Fare

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

JOI có \(N\) thành phố, đánh số từ 1 đến \(N\); thành phố 1 là thủ đô. Có \(M\) tuyến đường sắt hai chiều, tuyến \(i\) nối \(U_i\) và \(V_i\). Có thể đi giữa mọi cặp thành phố bằng đường sắt.

Ban đầu mọi tuyến có giá 1 yên. Trong \(Q\) năm tới, vào đầu năm \(j\), giá tuyến \(R_j\) tăng từ 1 lên 2 yên và giữ nguyên sau đó; không tuyến nào tăng giá hai lần.

Sau lần tăng giá mỗi năm, một thành phố \(k\) (\(2\le k\le N\)) bất mãn khi và chỉ khi chi phí nhỏ nhất từ \(k\) tới thủ đô theo giá hiện tại lớn hơn chi phí nhỏ nhất ban đầu. Chi phí một hành trình là tổng giá các tuyến đã đi. Thành phố 1 không bao giờ bất mãn.

Hãy tính số thành phố bất mãn trong từng năm.

Dữ liệu vào

Dòng đầu chứa \(N,M,Q\).
\(M\) dòng tiếp theo: dòng \(i\) chứa \(U_i,V_i\).
\(Q\) dòng tiếp theo: dòng \(j\) chứa \(R_j\).

Dữ liệu ra

In ra \(Q\) dòng; dòng \(j\) là số thành phố bất mãn trong năm \(j\).

Ràng buộc

\(2\le N\le100000\).
\(1\le Q\le M\le200000\).
\(1\le U_i,V_i\le N\) và \(U_i\ne V_i\).
\(1\le R_j\le M\); các \(R_j\) đôi một khác nhau.
Giữa hai thành phố có nhiều nhất một tuyến trực tiếp.
Mọi thành phố đều có đường tới thành phố 1.

Phân nhóm

Nhóm 1 (12 điểm): \(N\le100\), \(M\le4950\), \(Q\le30\).
Nhóm 2 (14 điểm): \(Q\le30\).
Nhóm 3 (35 điểm): các số nguyên xuất hiện trong đáp án đúng có không quá 50 giá trị khác nhau.
Nhóm 4 (39 điểm): không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Ví dụ 2

Input

Output

Ví dụ 3

Input

2 1 1
1 2
1

Output

Nguồn

Kỳ thi chung kết Olympic Tin học Nhật Bản 2015/2016, bài 3.

4. JOI 2016 - Territory

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

Một thành phố có vô số đường thẳng song song theo hướng bắc-nam và đông-tây, khoảng cách giữa hai đường kề nhau là 1 km. Tòa thị chính ở giao lộ \((0,0)\); giao lộ \((i,j)\) nằm cách đó \(i\) km về đông và \(j\) km về bắc, với giá trị âm chỉ hướng ngược lại.

Một chú chó tên Joy lập kế hoạch đi dạo trong \(K\) ngày:

Sáng ngày đầu, Joy ở \((0,0)\) và đánh dấu giao lộ này.
Mỗi trưa, Joy thực hiện cùng một chuỗi \(N\) bước. Mỗi bước đi tới một giao lộ kề cạnh và đánh dấu nơi tới.
Sau chuỗi bước, Joy ngủ tại vị trí hiện tại tới sáng hôm sau.

Ô vuông có bốn đỉnh \((a,b),(a+1,b),(a+1,b+1),(a,b+1)\) thuộc lãnh thổ của Joy nếu cả bốn giao lộ đều đã được đánh dấu ít nhất một lần. Hãy tính số ô thuộc lãnh thổ sau \(K\) ngày.

Dữ liệu vào

Dòng 1 chứa \(N,K\).
Dòng 2 chứa xâu \(S\) dài \(N\). Ký tự thứ \(p\) là E, N, W, hoặc S, tương ứng đi sang đông, bắc, tây, nam ở bước \(p\).

Dữ liệu ra

In ra số ô thuộc lãnh thổ của Joy.

Ràng buộc

\(1\le N\le100000\).
\(1\le K\le10^9\).

Phân nhóm

Nhóm 1 (5 điểm): \(N\le50\), \(K=1\).
Nhóm 2 (10 điểm): \(K=1\).
Nhóm 3 (23 điểm): \(N\le50\).
Nhóm 4 (62 điểm): không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

12 1
EENWSEEESWWS

Output

Giải thích

Joy đi trong một ngày và tạo ra 3 ô lãnh thổ.

Ví dụ 2

Input

12 2
EENWSEEESWWS

Output

Giải thích

Mỗi ngày Joy đi cùng lộ trình như ví dụ 1; sau hai ngày có 7 ô lãnh thổ. Ví dụ này không thỏa nhóm 1 hoặc 2.

Ví dụ 3

Input

7 1
ENNWNNE

Output

Ví dụ 4

Input

16 5
WSESSSWWWEEENNNW

Output

Giải thích

Ví dụ 4 không thỏa nhóm 1 hoặc 2.

Nguồn

Kỳ thi chung kết Olympic Tin học Nhật Bản 2015/2016, bài 4.

5. JOI 2016 - Geologic Fault

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

Ngày xưa, nền văn minh IOI phát triển dọc một con sông thẳng, rồi bị núi lửa hủy diệt. Khi đó mặt đất phẳng và được xem là trục \(x\); trục \(y\) biểu diễn độ cao. Đường \(y=0\) là mặt đất, \(y>0\) ở trên mặt đất và \(y<0\) ở dưới đất. Lớp địa chất hình thành \(a\) năm trước khi nền văn minh diệt vong ban đầu nằm trên đường \(y=-a\).

Sau đó xảy ra \(Q\) chuyển động địa chất. Chuyển động thứ \(i\) được mô tả bởi \(X_i,D_i,L_i\), với \(D_i\in\{1,2\}\):

Nếu \(D_i=1\), một đứt gãy dọc đường hệ số góc 1 qua \((X_i,0)\) được tạo ra. Mọi điểm \((x,y)\) nằm phía trên đường này chuyển thành \((x+L_i,y+L_i)\).
Nếu \(D_i=2\), một đứt gãy dọc đường hệ số góc \(-1\) qua \((X_i,0)\) được tạo ra. Mọi điểm \((x,y)\) nằm phía trên đường này chuyển thành \((x-L_i,y+L_i)\).
Ngay sau đó, toàn bộ lớp địa chất trong miền \(y>0\) bị phong hóa và biến mất.

Với mỗi \(i\) từ 1 đến \(N\), hãy xác định lớp địa chất đang lộ trên mặt đất giữa \((i-1,0)\) và \((i,0)\) được hình thành bao nhiêu năm trước khi nền văn minh IOI diệt vong.

Dữ liệu vào

Dòng đầu chứa \(N,Q\).
\(Q\) dòng tiếp theo: dòng \(i\) chứa \(X_i,D_i,L_i\).

Dữ liệu ra

In ra \(N\) dòng. Dòng \(i\) là tuổi của lớp địa chất trên đoạn mặt đất từ \((i-1,0)\) đến \((i,0)\).

Ràng buộc

\(1\le N,Q\le200000\).
\(-10^9\le X_i\le10^9\).
\(1\le D_i\le2\).
\(1\le L_i\le10^9\).

Phân nhóm

Nhóm 1 (18 điểm): \(N\le100\), \(Q\le100\), \(-100\le X_i\le100\), và \(L_i=1\) với mọi \(i\).
Nhóm 2 (16 điểm): \(N\le3000\), \(Q\le3000\).
Nhóm 3 (66 điểm): không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

10 2
12 1 3
2 2 2

Output

Ví dụ 2

Input

Output

Giải thích

Ví dụ 2 thỏa các ràng buộc của nhóm 1.

Ví dụ 3

Input

Output

Nguồn

Kỳ thi chung kết Olympic Tin học Nhật Bản 2015/2016, bài 5.