JOI 2015/2015 - Vòng chung kết

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 JOI 2015 - Railroad Trip 100 (p) 1.0s 256M
2 JOI 2015 - Cake 2 100 (p) 2.0s 512M
3 JOI 2015 - JOI Park 100 (p) 1.0s 256M
4 JOI 2015 - Ball 100 (p) 1.0s 256M
5 JOI 2015 - Rampart 100 (p) 10.0s 512M

1. JOI 2015 - Railroad Trip

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

JOI có \(N\) thành phố đánh số \(1\) đến \(N\) và \(N-1\) tuyến đường sắt; tuyến \(i\) nối hai chiều thành phố \(i\) và \(i+1\). Đi tuyến \(i\) bằng vé giấy tốn \(A_i\) yên. Đi bằng thẻ IC tốn \(B_i\) yên mỗi lượt, nhưng trước đó phải mua riêng thẻ của tuyến ấy với giá \(C_i\); thẻ dùng được không giới hạn và không dùng được cho tuyến khác. Luôn có \(A_i>B_i\).

Bạn lần lượt ghé \(P_1,P_2,\ldots,P_M\), đi từ \(P_j\) tới \(P_{j+1}\) trong ngày \(j\). Ban đầu bạn không có thẻ. Hãy chọn trước các thẻ cần mua và cách trả tiền để tổng giá thẻ cùng tiền tàu nhỏ nhất.

Dữ liệu vào

  • Dòng 1: \(N,M\).
  • Dòng 2: \(P_1,\ldots,P_M\).
  • \(N-1\) dòng tiếp: \(A_i,B_i,C_i\).

Dữ liệu ra

In chi phí nhỏ nhất, theo yên.

Ràng buộc

  • \(2\le N,M\le100\,000\),
  • \(1\le B_i<A_i\le100\,000,\quad1\le C_i\le100\,000\),
  • \(1\le P_j\le N,\quad P_j\ne P_{j+1}\).

Phân nhóm

  • Nhóm 1 (20 điểm): \(N\le1000\), \(M=2\), \(A_i,B_i,C_i\le1000\).
  • Nhóm 2 (30 điểm): \(N,M\le1000\), \(A_i,B_i,C_i\le1000\).
  • Nhóm 3 (50 điểm): không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
4 4
1 3 2 4
120 90 100
110 50 80
250 70 130
Output 
550
Giải thích

Trong ví dụ 1, mua thẻ cho tuyến 2 và 3 tốn \(210\); tổng tiền tàu là \(170+50+120\), nên tổng cộng \(550\).

Ví dụ 2

Input 
8 5
7 5 3 5 4
12 5 8
16 2 1
3 1 5
17 12 17
19 7 5
12 2 19
4 1 3
Output 
81

2. JOI 2015 - Cake 2

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

Một chiếc bánh tròn được chia thành \(N\) miếng đánh số ngược chiều kim đồng hồ. Miếng \(i\) kề miếng \(i-1\) và \(i+1\) (coi miếng \(0\) là \(N\), miếng \(N+1\) là \(1\)), có kích thước \(A_i\); mọi \(A_i\) đôi một khác nhau.

JOI chọn trước một miếng bất kỳ. Sau đó IOI và JOI luân phiên lấy, IOI đi trước. Chỉ được lấy miếng có ít nhất một miếng kề đã bị lấy. Nếu có nhiều lựa chọn, IOI luôn lấy miếng lớn nhất, còn JOI được tùy ý chọn. Hãy tìm tổng kích thước lớn nhất JOI có thể lấy.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ \(i+1\) chứa \(A_i\).

Dữ liệu ra

In tổng lớn nhất JOI có thể lấy.

Ràng buộc

\[ 1\le N\le2000,\qquad1\le A_i\le10^9, \]

các \(A_i\) đôi một khác nhau.

Phân nhóm

  • Nhóm 1 (15 điểm): \(N\le20\).
  • Nhóm 2 (45 điểm): \(N\le300\).
  • Nhóm 3 (40 điểm): không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
5
2
8
1
10
9
Output 
18
Giải thích

Trong ví dụ 1, JOI có thể lần lượt lấy các miếng 2, 5, 3, đạt \(8+9+1=18\).

Ví dụ 2

Input 
8
1
10
4
5
6
2
9
3
Output 
26

Ví dụ 3

Input 
15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079805
564327789
Output 
3600242976

3. JOI 2015 - JOI Park

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

Công viên JOI có \(N\) quảng trường và \(M\) đường hai chiều. Đường \(i\) nối \(A_i,B_i\), dài \(D_i\); đồ thị liên thông. Khoảng cách giữa hai quảng trường là tổng độ dài nhỏ nhất của một đường đi.

Kế hoạch cải tạo chọn số nguyên \(X\ge0\), nối ngầm lẫn nhau mọi quảng trường cách quảng trường 1 không quá \(X\), với chi phí \(CX\). Sau đó xóa miễn phí mọi đường có cả hai đầu đã được nối ngầm, rồi sửa tất cả đường còn lại; sửa đường dài \(d\) tốn \(d\). Ban đầu không có đường ngầm. Hãy tìm tổng chi phí nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa \(N,M,C\). Mỗi trong \(M\) dòng sau chứa \(A_i,B_i,D_i\).

Dữ liệu ra

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

Ràng buộc

\[ 2\le N\le100\,000,\quad1\le M\le200\,000,\quad1\le C\le100\,000, \]
\[ 1\le A_i,B_i\le N,\quad A_i\ne B_i,\quad1\le D_i\le100\,000. \]

Không có hai đường nối cùng một cặp quảng trường (kể cả đảo thứ tự), và đồ thị liên thông.

Phân nhóm

  • Nhóm 1 (15 điểm): \(N\le100\), \(M\le200\), \(C\le100\), \(D_i\le10\).
  • Nhóm 2 (45 điểm): \(N\le100\), \(M\le4000\).
  • Nhóm 3 (40 điểm): không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5
Output 
14
Giải thích

Ví dụ 1 tối ưu với \(X=3\); ví dụ 2 với \(X=0\); ví dụ 3 với \(X=5\).

Ví dụ 2

Input 
5 4 10
1 2 3
2 3 4
3 4 3
4 5 5
Output 
15

Ví dụ 3

Input 
6 5 2
1 2 2
1 3 4
1 4 3
1 5 1
1 6 5
Output 
10

4. JOI 2015 - Ball

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

Có \(N\) quý tộc đánh số \(1\) đến \(N\), với \(N\) lẻ. Kỹ năng khiêu vũ của người \(i\) là \(D_i\). Họ xếp thành hàng và ghép cặp như sau, cho tới khi còn một người:

  1. Xét ba người đầu hàng.
  2. Chọn \(A\) có kỹ năng lớn nhất; nếu hòa, chọn người có số nhỏ nhất.
  3. Chọn \(B\) có kỹ năng nhỏ nhất; nếu hòa, chọn người có số lớn nhất.
  4. \(A,B\) rời hàng thành một cặp; người còn lại chuyển xuống cuối hàng.

Người cuối cùng ghép với công chúa JOI. Vị trí ban đầu của các quý tộc \(1\) đến \(M\) đã cố định; nhà vua được xếp những người còn lại vào các vị trí trống. Hãy tối đa hóa kỹ năng của người ghép với công chúa.

Dữ liệu vào

  • Dòng đầu: \(N,M\).
  • \(M\) dòng tiếp: \(D_i,P_i\), trong đó quý tộc \(i\) đứng vị trí \(P_i\) tính từ đầu hàng.
  • \(N-M\) dòng tiếp: dòng thứ \(i\) chứa \(D_{i+M}\).

Dữ liệu ra

In kỹ năng lớn nhất có thể của bạn nhảy công chúa.

Ràng buộc

\[ 3\le N\le99\,999,\quad N\text{ lẻ},\quad1\le M\le N-2, \]
\[ 1\le D_i\le10^9,\quad1\le P_i\le N, \]

các \(P_i\) đôi một khác nhau.

Phân nhóm

  • Nhóm 1 (8 điểm): \(N\le9\).
  • Nhóm 2 (16 điểm): \(N\le19\).
  • Nhóm 3 (44 điểm): \(N\le1999\).
  • Nhóm 4 (32 điểm): không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
7 3
5 2
5 5
8 6
6
2
8
9
Output 
8

Ví dụ 2

Input 
3 1
5 3
5
5
Output 
5

Ví dụ 3

Input 
7 2
32 4
27 6
37
41
41
30
27
Output 
37

5. JOI 2015 - Rampart

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

Vương quốc IOI là lưới \(H\times W\). Một thành lũy kích thước \(s\) (\(s\ge3\)) là đường viền dày một ô của một hình vuông \(s\times s\), tức phần còn lại sau khi bỏ hình vuông trong \((s-2)\times(s-2)\).

Thành lũy quanh thủ đô có kích thước ít nhất \(L\). Có \(P\) ô được biết chắc không có thành lũy. Hãy đếm số thành lũy có thể có, xét mọi kích thước và vị trí hoàn toàn nằm trong lưới, không đi qua ô bị cấm.

Dữ liệu vào

Dòng đầu chứa \(H,W,L,P\). Mỗi trong \(P\) dòng sau chứa \(A_i,B_i\), là hàng từ trên xuống và cột từ trái sang của một ô không có thành lũy.

Dữ liệu ra

In số thành lũy có thể có.

Ràng buộc

  • \(1\le H,W\le4000\),
  • \(3\le L\le H,\quad3\le L\le W\),
  • \(0\le P\le100\,000\),
  • \(1\le A_i\le H,\quad1\le B_i\le W\),
  • các cặp \((A_i,B_i)\) đôi một khác nhau.

Phân nhóm

  • Nhóm 1 (4 điểm): \(H,W\le500\).
  • Nhóm 2 (16 điểm): \(P\le10\).
  • Nhóm 3 (80 điểm): không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
5 5 3 2
2 2
4 3
Output 
4

Ví dụ 2

Input 
7 8 4 3
2 2
3 7
6 5
Output 
13

Ví dụ 3

Input 
4000 4000 1234 4
1161 3028
596 1892
3731 2606
702 1530
Output 
7050792912