JOI 2017/2018 - 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 2018 - Stove 100 (p) 1.0s 256M
2 JOI 2018 - Art Exhibition 100 (p) 1.0s 256M
3 JOI 2018 - Dango Maker 100 (p) 2.0s 256M
4 JOI 2018 - Commuter Pass 100 (p) 2.0s 256M
5 JOI 2018 - Snake Escaping 100 (p) 2.0s 64M

1. JOI 2018 - Stove

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

Trong phòng của JOI-kun có một chiếc lò sưởi. Vì đã quen với trời lạnh, cậu không cần bật lò khi ở trong phòng một mình. Tuy nhiên, khi có khách, cậu phải bật lò sưởi.

Một ngày nọ, có \(N\) vị khách đến thăm JOI-kun. Vị khách thứ \(i\) (\(1\le i\le N\)) đến vào thời điểm \(T_i\) và rời đi vào thời điểm \(T_i+1\). Tại mỗi thời điểm, có nhiều nhất một vị khách ở thăm.

JOI-kun có thể bật hoặc tắt lò sưởi vào bất kỳ thời điểm nào. Mỗi lần bật lò cần dùng một que diêm. Cậu chỉ có \(K\) que diêm, nên có thể bật lò nhiều nhất \(K\) lần. Đầu ngày, lò sưởi đang tắt.

Khi được bật, lò sưởi tiêu thụ nhiên liệu. Vì vậy, JOI-kun muốn chọn các thời điểm bật và tắt sao cho tổng thời gian lò hoạt động nhỏ nhất, đồng thời lò luôn được bật khi có khách.

Cho thời gian ghé thăm của các vị khách và số que diêm, hãy tính tổng thời gian hoạt động nhỏ nhất của lò sưởi.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

  • Dòng đầu chứa hai số nguyên \(N,K\), cách nhau bởi dấu cách: số khách và số que diêm.
  • Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa số nguyên \(T_i\), là thời điểm vị khách thứ \(i\) đến. Người đó rời đi vào thời điểm \(T_i+1\).

Dữ liệu ra

Ghi một dòng chứa tổng thời gian hoạt động nhỏ nhất của lò sưởi.

Ràng buộc

  • \(1\le N\le100\,000\).
  • \(1\le K\le N\).
  • \(1\le T_i\le10^9\) với \(1\le i\le N\).
  • \(T_i<T_{i+1}\) với \(1\le i<N\).

Phân nhóm

  1. (20 điểm) \(N\le20\) và \(1\le T_i\le20\) với mọi \(1\le i\le N\).
  2. (30 điểm) \(N\le5000\).
  3. (50 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

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

Có ba vị khách đến thăm. JOI-kun có thể bật và tắt lò như sau:

  • Bật lò ở thời điểm \(1\), khi vị khách thứ nhất đến.
  • Tắt lò ở thời điểm \(4\), khi vị khách thứ hai rời đi.
  • Bật lò ở thời điểm \(6\), khi vị khách thứ ba đến.
  • Tắt lò ở thời điểm \(7\), khi vị khách thứ ba rời đi.

Lò luôn bật khi có khách, được bật hai lần và có tổng thời gian hoạt động \((4-1)+(7-6)=4\). Không thể làm tổng thời gian nhỏ hơn \(4\), nên đáp án là \(4\).

Ví dụ 2

Input 
3 1
1
2
6
Output 
6
Giải thích

JOI-kun chỉ có thể bật lò một lần. Cậu bật lò ở thời điểm \(1\), khi vị khách thứ nhất đến, và tắt lò ở thời điểm \(7\), khi vị khách thứ ba rời đi.

Lưu ý rằng thời điểm một vị khách rời đi có thể trùng với thời điểm vị khách tiếp theo đến.

Ví dụ 3

Input 
3 3
1
3
6
Output 
3
Giải thích

JOI-kun bật lò mỗi khi một vị khách đến và tắt lò khi người đó rời đi.

Ví dụ 4

Input 
10 5
1
2
5
6
8
11
13
15
16
20
Output 
12

Nguồn

JOI 2017/2018, vòng chung kết, bài Stove. Đề do Japanese Committee for the International Olympiad in Informatics công bố. Đề gốc tiếng Anh. Bản dịch tiếng Việt theo CC BY-SA 4.0.

2. JOI 2018 - Art Exhibition

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

Một triển lãm mỹ thuật sẽ được tổ chức tại nước JOI, trưng bày các tác phẩm từ khắp cả nước.

Có \(N\) tác phẩm ứng cử cho triển lãm, đánh số từ \(1\) đến \(N\). Mỗi tác phẩm có hai đại lượng nguyên là kích thước và giá trị. Tác phẩm thứ \(i\) có kích thước \(A_i\) và giá trị \(B_i\).

Ban tổ chức sẽ chọn ít nhất một tác phẩm để trưng bày. Hội trường đủ rộng để trưng bày cả \(N\) tác phẩm. Tuy nhiên, theo quan niệm thẩm mỹ của người dân JOI, chênh lệch kích thước giữa các tác phẩm được chọn không nên quá lớn. Mặt khác, ban tổ chức muốn trưng bày nhiều tác phẩm có giá trị cao. Vì vậy, việc lựa chọn tuân theo tiêu chí sau:

  • Gọi \(A_{\max}\) và \(A_{\min}\) lần lượt là kích thước lớn nhất và nhỏ nhất trong các tác phẩm được chọn; gọi \(S\) là tổng giá trị của chúng.
  • Chọn các tác phẩm sao cho \(S-(A_{\max}-A_{\min})\) lớn nhất.

Cho số tác phẩm ứng cử, kích thước và giá trị của từng tác phẩm, hãy tính giá trị lớn nhất của biểu thức trên.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

  • Dòng đầu chứa số nguyên \(N\), là số tác phẩm ứng cử.
  • Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(A_i,B_i\), cách nhau bởi dấu cách, lần lượt là kích thước và giá trị của tác phẩm thứ \(i\).

Dữ liệu ra

Ghi một dòng chứa giá trị lớn nhất của \(S-(A_{\max}-A_{\min})\).

Ràng buộc

  • \(2\le N\le500\,000\).
  • \(1\le A_i\le10^{15}\) với \(1\le i\le N\).
  • \(1\le B_i\le10^9\) với \(1\le i\le N\).

Phân nhóm

  1. (10 điểm) \(N\le16\).
  2. (20 điểm) \(N\le300\).
  3. (20 điểm) \(N\le5000\).
  4. (50 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
3
2 3
11 2
4 5
Output 
6
Giải thích

Có ba tác phẩm: tác phẩm \(1\) có kích thước \(2\), giá trị \(3\); tác phẩm \(2\) có kích thước \(11\), giá trị \(2\); tác phẩm \(3\) có kích thước \(4\), giá trị \(5\).

Chọn tác phẩm \(1\) và \(3\) để trưng bày:

  • Tác phẩm \(3\) có kích thước lớn nhất trong các tác phẩm được chọn, nên \(A_{\max}=4\).
  • Tác phẩm \(1\) có kích thước nhỏ nhất, nên \(A_{\min}=2\).
  • Tổng giá trị là \(S=3+5=8\).

Do đó \(S-(A_{\max}-A_{\min})=8-(4-2)=6\). Không thể đạt giá trị từ \(7\) trở lên, nên đáp án là \(6\).

Ví dụ 2

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

Ví dụ 3

Input 
15
1543361732 260774320
2089759661 257198921
1555665663 389548466
4133306295 296394520
2596448427 301103944
1701413087 274491541
2347488426 912791996
2133012079 444074242
2659886224 656957044
1345396764 259870638
2671164286 233246973
2791812672 585862344
2996614635 91065315
971304780 488995617
1523452673 988137562
Output 
4232545716

Nguồn

JOI 2017/2018, vòng chung kết, bài Art Exhibition. Đề do Japanese Committee for the International Olympiad in Informatics công bố. Đề gốc tiếng Anh. Bản dịch tiếng Việt theo CC BY-SA 4.0.

3. JOI 2018 - Dango Maker

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

Bạn là một thợ làm bánh chuyên nghiệp, chuyên làm dango, một loại bánh viên ngọt của Nhật Bản. Bây giờ, bạn chuẩn bị xiên các viên bánh vào que.

Các viên bánh được đặt trên một bảng gồm \(N\) hàng và \(M\) cột, mỗi ô chứa một viên. Mỗi viên có một trong ba màu: đỏ (R), xanh lá (G) hoặc trắng (W).

Để tạo một xiên bánh, bạn chọn ba viên ở ba ô liên tiếp theo chiều từ trái sang phải hoặc từ trên xuống dưới, rồi xiên chúng theo đúng thứ tự đó. Bạn chỉ muốn tạo các xiên có màu lần lượt là đỏ, xanh lá, trắng. Không được dùng một viên bánh cho nhiều hơn một xiên.

Cho màu của tất cả các viên bánh trên bảng, hãy tìm số xiên bánh nhiều nhất có thể tạo ra.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

  • Dòng đầu chứa hai số nguyên \(N,M\), cách nhau bởi dấu cách.
  • Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa một xâu độ dài \(M\), chỉ gồm các ký tự R, G, W. Ký tự thứ \(j\) là màu của viên bánh ở hàng thứ \(i\) tính từ trên xuống và cột thứ \(j\) tính từ trái sang phải.

Dữ liệu ra

Ghi một dòng chứa số xiên bánh nhiều nhất có thể tạo ra, mỗi xiên gồm ba màu đỏ, xanh lá, trắng theo đúng thứ tự.

Ràng buộc

  • \(1\le N\le3000\).
  • \(1\le M\le3000\).
  • Mỗi hàng của bảng là một xâu độ dài \(M\) chỉ gồm R, G, W.

Phân nhóm

  1. (13 điểm) \(N\le4\) và \(M\le4\).
  2. (20 điểm) \(N\le10\) và \(M\le10\).
  3. (67 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
3 4
RGWR
GRGG
RGWW
Output 
3
Giải thích

Có thể tạo ba xiên như sau. Các tọa độ dưới đây có dạng (hàng, cột), tính từ trên xuống và từ trái sang phải:

  • Chọn ba viên liên tiếp từ ô \((1,1)\) theo chiều từ trái sang phải: \((1,1),(1,2),(1,3)\).
  • Chọn ba viên liên tiếp từ ô \((1,4)\) theo chiều từ trên xuống dưới: \((1,4),(2,4),(3,4)\).
  • Chọn ba viên liên tiếp từ ô \((3,1)\) theo chiều từ trái sang phải: \((3,1),(3,2),(3,3)\).

Trong mỗi trường hợp, xiên các viên theo thứ tự vừa chọn. Không thể tạo bốn xiên, nên đáp án là \(3\).

Ví dụ 2

Input 
4 4
RGWR
GRRG
WGGW
WWWR
Output 
4
Giải thích

Có thể tạo bốn xiên, mỗi xiên theo đúng thứ tự các viên được liệt kê:

  • Từ ô \((1,1)\) theo chiều từ trái sang phải: \((1,1),(1,2),(1,3)\).
  • Từ ô \((1,4)\) theo chiều từ trên xuống dưới: \((1,4),(2,4),(3,4)\).
  • Từ ô \((2,2)\) theo chiều từ trên xuống dưới: \((2,2),(3,2),(4,2)\).
  • Từ ô \((2,3)\) theo chiều từ trên xuống dưới: \((2,3),(3,3),(4,3)\).

Không thể tạo năm xiên, nên đáp án là \(4\).

Ví dụ 3

Input 
5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
Output 
6

Nguồn

JOI 2017/2018, vòng chung kết, bài Dango Maker. Đề do Japanese Committee for the International Olympiad in Informatics công bố. Đề gốc tiếng Anh. Bản dịch tiếng Việt theo CC BY-SA 4.0.

4. JOI 2018 - Commuter Pass

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

JOI-kun sống trong một thành phố có \(N\) nhà ga, đánh số từ \(1\) đến \(N\). Có \(M\) tuyến đường sắt, đánh số từ \(1\) đến \(M\). Tuyến thứ \(i\) nối hai chiều giữa ga \(A_i\) và ga \(B_i\), với giá vé \(C_i\) yên.

JOI-kun sống gần ga \(S\) và đi học tại trường trung học IOI gần ga \(T\). Cậu dự định mua một vé tháng nối hai ga này. Khi mua vé tháng, cậu phải chọn một đường đi có tổng giá vé nhỏ nhất từ \(S\) đến \(T\). Với vé tháng đó, cậu có thể đi trên bất kỳ tuyến đường sắt nào thuộc đường đi đã chọn, theo bất kỳ chiều nào, mà không phải trả thêm tiền.

JOI-kun thường đến các hiệu sách gần ga \(U\) và ga \(V\). Vì vậy, cậu muốn chọn đường đi cho vé tháng sao cho chi phí đi từ \(U\) đến \(V\) nhỏ nhất.

Khi đi từ \(U\) đến \(V\), trước hết cậu chọn một đường đi giữa hai ga. Với mỗi tuyến đường sắt thứ \(i\) trên đường đi này, cậu phải trả:

  • \(0\) yên nếu tuyến đó thuộc đường đi đã chọn khi mua vé tháng.
  • \(C_i\) yên nếu tuyến đó không thuộc đường đi đã chọn khi mua vé tháng.

Chi phí đi từ \(U\) đến \(V\) là tổng các khoản tiền trên. Hãy tính chi phí nhỏ nhất có thể đạt được khi JOI-kun lựa chọn đường đi cho vé tháng một cách thích hợp.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

  • Dòng đầu chứa hai số nguyên \(N,M\), cách nhau bởi dấu cách, lần lượt là số nhà ga và số tuyến đường sắt.
  • Dòng thứ hai chứa hai số nguyên \(S,T\), là hai ga mà vé tháng nối với nhau.
  • Dòng thứ ba chứa hai số nguyên \(U,V\), là hai ga mà JOI-kun muốn giảm thiểu chi phí đi lại.
  • Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa ba số nguyên \(A_i,B_i,C_i\), cách nhau bởi dấu cách. Tuyến thứ \(i\) nối hai chiều giữa \(A_i\) và \(B_i\), có giá vé \(C_i\) yên.

Dữ liệu ra

Ghi một dòng chứa chi phí nhỏ nhất để đi từ \(U\) đến \(V\), khi đường đi cho vé tháng được chọn một cách thích hợp.

Ràng buộc

  • \(2\le N\le100\,000\).
  • \(1\le M\le200\,000\).
  • \(1\le S,T,U,V\le N\).
  • \(S\ne T\).
  • \(U\ne V\).
  • \(S\ne U\) hoặc \(T\ne V\).
  • Có thể đi từ bất kỳ ga nào đến bất kỳ ga nào khác bằng đường sắt.
  • \(1\le A_i<B_i\le N\) với \(1\le i\le M\).
  • Với mọi \(1\le i<j\le M\), có \(A_i\ne A_j\) hoặc \(B_i\ne B_j\); tức là không có hai tuyến nối cùng một cặp ga.
  • \(1\le C_i\le10^9\) với \(1\le i\le M\).

Phân nhóm

  1. (16 điểm) \(S=U\).
  2. (15 điểm) Có duy nhất một đường đi có tổng giá vé nhỏ nhất từ \(S\) đến \(T\).
  3. (24 điểm) \(N\le300\).
  4. (45 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

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

JOI-kun chỉ có một đường đi để chọn khi mua vé tháng: \(1\to2\to3\to5\to6\).

Để giảm thiểu chi phí từ ga \(1\) đến ga \(4\), cậu đi theo đường \(1\to2\to3\to5\to4\). Khi đó:

  • Cậu trả \(2\) yên cho tuyến đường sắt thứ \(5\), nối ga \(4\) và ga \(5\).
  • Các tuyến còn lại trên đường đi đều miễn phí nhờ vé tháng.

Tổng chi phí là \(2\) yên.

Ví dụ 2

Input 
6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
Output 
3000000000
Giải thích

JOI-kun không dùng vé tháng khi đi từ ga \(3\) đến ga \(6\).

Ví dụ 3

Input 
8 8
5 7
6 8
1 2 2
2 3 3
3 4 4
1 4 1
1 5 5
2 6 6
3 7 7
4 8 8
Output 
15

Ví dụ 4

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

Ví dụ 5

Input 
10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16
Output 
19

Nguồn

JOI 2017/2018, vòng chung kết, bài Commuter Pass. Đề do Japanese Committee for the International Olympiad in Informatics công bố. Đề gốc tiếng Anh. Bản dịch tiếng Việt theo CC BY-SA 4.0.

5. JOI 2018 - Snake Escaping

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

Phòng thí nghiệm JOI nuôi \(2^L\) con rắn độc, đánh số từ \(0\) đến \(2^L-1\). Cơ thể mỗi con được chia thành \(L\) phần theo thứ tự từ đầu đến đuôi; mỗi phần có màu xanh dương hoặc đỏ. Với con rắn thứ \(i\), viết biểu diễn nhị phân đủ \(L\) chữ số của \(i\) dưới dạng:

\[ i=\sum_{k=1}^{L}c_k2^{L-k},\qquad c_k\in\{0,1\}. \]
  • Nếu \(c_k=0\), phần thứ \(k\) tính từ đầu của con rắn \(i\) có màu xanh dương.
  • Nếu \(c_k=1\), phần thứ \(k\) tính từ đầu của con rắn \(i\) có màu đỏ.

Mỗi con rắn có một độ độc, là số nguyên từ \(0\) đến \(9\). Bạn được cho xâu \(S\) có độ dài \(2^L\), chỉ gồm các chữ số từ 0 đến 9. Ký tự thứ \(i\) của \(S\) (\(1\le i\le2^L\)) cho biết độ độc của con rắn mang số \(i-1\).

Do di chuyển nhanh, các con rắn thường trốn khỏi phòng thí nghiệm. Những người dân sống gần đó nhìn thấy chúng và gửi phản ánh đến phòng thí nghiệm JOI.

Bạn được cho thông tin phản ánh trong \(Q\) ngày. Thông tin của ngày thứ \(d\) là xâu \(T_d\) có độ dài \(L\), chỉ gồm 0, 1, ?. Với mỗi vị trí \(j\) (\(1\le j\le L\)):

  • Nếu ký tự thứ \(j\) của \(T_d\) là 0, phần thứ \(j\) tính từ đầu của mọi con rắn trốn ra trong ngày đó đều có màu xanh dương.
  • Nếu ký tự đó là 1, phần thứ \(j\) tính từ đầu của mọi con rắn trốn ra trong ngày đó đều có màu đỏ.
  • Nếu ký tự đó là ?, người dân không cung cấp thông tin về phần thứ \(j\) của các con rắn trốn ra trong ngày đó.

Tất cả thông tin phản ánh đều chính xác. Nhân viên phòng thí nghiệm bắt lại toàn bộ các con rắn trốn ra ngay trong ngày. Một con rắn có thể lại trốn ra vào một ngày khác.

Để đánh giá mức độ nguy hiểm, giáo sư K, giám đốc phòng thí nghiệm JOI, muốn biết tổng độ độc của tất cả các con rắn có thể đã trốn ra, tức là có màu sắc phù hợp với thông tin phản ánh. Cho xâu \(S\) và thông tin của \(Q\) ngày, hãy tính tổng này cho từng ngày.

Lưu ý: giới hạn bộ nhớ của bài này nhỏ, chỉ \(64\) MB.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

  • Dòng đầu chứa hai số nguyên \(L,Q\), cách nhau bởi dấu cách, lần lượt là số phần trên cơ thể mỗi con rắn và số ngày có thông tin phản ánh.
  • Dòng thứ hai chứa xâu \(S\) độ dài \(2^L\), mô tả độ độc của các con rắn.
  • Dòng thứ \(d\) trong \(Q\) dòng tiếp theo chứa xâu \(T_d\) độ dài \(L\), là thông tin phản ánh của ngày thứ \(d\).

Dữ liệu ra

Ghi \(Q\) dòng. Dòng thứ \(d\) chứa một số nguyên là tổng độ độc của các con rắn có thể đã trốn khỏi phòng thí nghiệm trong ngày thứ \(d\).

Ràng buộc

  • \(1\le L\le20\).
  • \(1\le Q\le1\,000\,000\).
  • \(S\) có độ dài \(2^L\) và chỉ gồm các ký tự 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
  • Với mọi \(1\le d\le Q\), xâu \(T_d\) có độ dài \(L\) và chỉ gồm các ký tự 0, 1, ?.

Phân nhóm

  1. (5 điểm) \(L\le10\) và \(Q\le1000\).
  2. (7 điểm) \(L\le10\).
  3. (10 điểm) \(L\le13\).
  4. (53 điểm) \(Q\le50\,000\).
  5. (25 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
3 5
12345678
000
0??
1?0
?11
???
Output 
1
10
12
12
36
Giải thích

Ở đây \(L=3\), nên có \(2^3=8\) con rắn, mỗi con có cơ thể chia thành ba phần. Thông tin phản ánh được cho trong năm ngày:

  • Ngày thứ nhất, chỉ con rắn \(0\) có thể đã trốn ra. Tổng độ độc là \(1\).
  • Ngày thứ hai, các con rắn có thể đã trốn ra mang số \(0,1,2,3\). Tổng độ độc là \(10\).
  • Ngày thứ ba, các con rắn có thể đã trốn ra mang số \(4,6\). Tổng độ độc là \(12\).
  • Ngày thứ tư, các con rắn có thể đã trốn ra mang số \(3,7\). Tổng độ độc là \(12\).
  • Ngày thứ năm, các con rắn có thể đã trốn ra mang số \(0,1,2,3,4,5,6,7\). Tổng độ độc là \(36\).

Ví dụ 2

Input 
4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????
Output 
9
18
38
30
14
15
20
80

Nguồn

JOI 2017/2018, vòng chung kết, bài Snake Escaping. Đề do Japanese Committee for the International Olympiad in Informatics công bố. Đề gốc tiếng Anh. Bản dịch tiếng Việt theo CC BY-SA 4.0.