JOI 2016/2017 - Vòng sơ khảo

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 2017 - Microwave 100 (p) 1.0s 256M
2 JOI 2017 - Point Card 100 (p) 1.0s 256M
3 JOI 2017 - Refreshment Area 100 (p) 1.0s 256M
4 JOI 2017 - Plush Toys 100 (p) 1.0s 256M
5 JOI 2017 - Ridge 100 (p) 1.0s 256M
6 JOI 2017 - Snake JOI 100 (p) 1.0s 256M

1. JOI 2017 - Microwave

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

Để chuẩn bị bữa ăn, JOI muốn dùng lò vi sóng để làm nóng một miếng thịt từ nhiệt độ \(A\) °C lên \(B\) °C.

Khi nhiệt độ của miếng thịt nhỏ hơn \(0\) °C, miếng thịt đang đông lạnh. Khi nhiệt độ lớn hơn \(0\) °C, miếng thịt không đông lạnh. Ở đúng \(0\) °C, miếng thịt có thể đang đông lạnh hoặc đã rã đông.

JOI ước tính thời gian làm nóng theo các quy tắc sau:

  • Nếu miếng thịt đang đông lạnh và nhiệt độ nhỏ hơn \(0\) °C, cần \(C\) giây để nhiệt độ tăng thêm \(1\) °C.
  • Nếu miếng thịt đang đông lạnh và nhiệt độ đúng bằng \(0\) °C, cần \(D\) giây để rã đông miếng thịt, đưa nó về trạng thái không đông lạnh.
  • Nếu miếng thịt không đông lạnh, cần \(E\) giây để nhiệt độ tăng thêm \(1\) °C.

Theo cách ước tính này, hãy tính số giây cần thiết để đưa miếng thịt lên nhiệt độ \(B\) °C.

Dữ liệu vào

Dữ liệu vào gồm \(5\) dòng, mỗi dòng chứa một số nguyên:

  • Dòng thứ nhất chứa nhiệt độ ban đầu \(A\) của miếng thịt.
  • Dòng thứ hai chứa nhiệt độ đích \(B\).
  • Dòng thứ ba chứa thời gian \(C\) để làm miếng thịt đông lạnh nóng thêm \(1\) °C.
  • Dòng thứ tư chứa thời gian \(D\) để rã đông miếng thịt.
  • Dòng thứ năm chứa thời gian \(E\) để làm miếng thịt không đông lạnh nóng thêm \(1\) °C.

Dữ liệu ra

In ra một số nguyên trên một dòng: số giây cần thiết để đưa miếng thịt lên nhiệt độ \(B\) °C.

Ràng buộc

Các giá trị thỏa mãn:

  • \(-100 \le A \le 100\).
  • \(1 \le B \le 100\).
  • \(A \ne 0\).
  • \(A < B\).
  • \(1 \le C,D,E \le 100\).

Phân nhóm

Bài có năm bộ dữ liệu chấm, mỗi bộ trị giá \(20\) điểm.

Ví dụ

Ví dụ 1

Input 
-10
20
5
10
3
Output 
120
Giải thích

Ban đầu miếng thịt ở \(-10\) °C và đang đông lạnh. Thời gian cần thiết được tính như sau:

  • Làm nóng từ \(-10\) °C lên \(0\) °C mất \(5 \times 10 = 50\) giây.
  • Rã đông miếng thịt ở \(0\) °C mất \(10\) giây.
  • Làm nóng từ \(0\) °C lên \(20\) °C mất \(3 \times 20 = 60\) giây.

Vì vậy, tổng thời gian là \(120\) giây.

Ví dụ 2

Input 
35
92
31
50
11
Output 
627
Giải thích

Ban đầu miếng thịt không đông lạnh. Do đó, cần \(627\) giây để làm nóng miếng thịt từ \(35\) °C lên \(92\) °C.

Nguồn

Kỳ thi chọn đội tuyển Olympic Tin học Nhật Bản JOI 2016/2017, vòng sơ khảo, bài 1: Microwave.

2. JOI 2017 - Point Card

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

Khu phố mua sắm JOI có một chương trình thẻ tích điểm. Mỗi thẻ có \(2N\) ô. Khi mua hàng, khách hàng được rút thăm; tùy theo kết quả, một dấu "trúng" hoặc "trượt" được đóng vào một ô. Không ô nào bị đóng dấu hai lần. Một thẻ có dấu "trúng" trong ít nhất \(N\) trên tổng số \(2N\) ô có thể được đổi lấy một phần quà.

Ngoài ra, có thể đổi dấu trong một ô với chi phí \(1\) yên.

JOI có \(M\) thẻ tích điểm mà cả \(2N\) ô đều đã được đóng dấu. Thẻ thứ \(i\) (\(1 \le i \le M\)) có \(A_i\) dấu "trúng" và \(B_i\) dấu "trượt". JOI muốn nhận được ít nhất \(M-1\) phần quà.

Hãy tính chi phí nhỏ nhất để JOI nhận được ít nhất \(M-1\) phần quà.

Dữ liệu vào

Dữ liệu vào gồm \(M+1\) dòng:

  • Dòng thứ nhất chứa hai số nguyên \(N, M\); mỗi thẻ có \(2N\) ô và JOI có \(M\) thẻ.
  • Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i, B_i\), mô tả số dấu "trúng" và số dấu "trượt" trên thẻ thứ \(i\).

Dữ liệu ra

In ra một số nguyên trên một dòng: chi phí nhỏ nhất để JOI nhận được ít nhất \(M-1\) phần quà.

Ràng buộc

Các giá trị thỏa mãn:

  • \(1 \le N \le 1\,000\).
  • \(1 \le M \le 1\,000\).
  • \(0 \le A_i \le 2N\).
  • \(0 \le B_i \le 2N\).
  • \(A_i+B_i=2N\).

Phân nhóm

Bài có năm bộ dữ liệu chấm, mỗi bộ trị giá \(20\) điểm.

Ví dụ

Ví dụ 1

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

Đổi \(3\) dấu "trượt" trên thẻ \(1\) và \(1\) dấu "trượt" trên thẻ \(3\) thành dấu "trúng" tốn \(4\) yên. Khi đó, \(4 = 5-1\) thẻ có thể đổi lấy quà, và đây là chi phí nhỏ nhất.

Ví dụ 2

Input 
5 4
5 5
8 2
3 7
8 2
Output 
0
Giải thích

Đã có sẵn \(3 = 4-1\) thẻ có thể đổi lấy quà, nên JOI không cần đổi dấu nào.

Nguồn

Kỳ thi chọn đội tuyển Olympic Tin học Nhật Bản JOI 2016/2017, vòng sơ khảo, bài 2: Point Card.

3. JOI 2017 - Refreshment Area

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

Một cuộc thi lập trình quốc tế sắp được tổ chức tại Nhật Bản và địa điểm thi đang được chuẩn bị. Địa điểm được chia thành một lưới gồm \(N\) ô theo hướng Bắc - Nam và \(M\) ô theo hướng Đông - Tây. Một số ô đang chứa thiết bị phục vụ cuộc thi.

Để thí sinh nghỉ ngơi trong thời gian thi, ban tổ chức sẽ bố trí đồ ăn nhẹ và thức uống tại đúng một khu vực nghỉ giải lao. Khu vực nghỉ phải gồm \(D\) ô liên tiếp theo hướng Bắc - Nam hoặc theo hướng Đông - Tây. Không được bố trí khu vực nghỉ trên ô có thiết bị.

Hãy tính số cách bố trí khu vực nghỉ giải lao trong địa điểm thi.

Dữ liệu vào

Dữ liệu vào gồm \(N+1\) dòng:

  • Dòng thứ nhất chứa ba số nguyên \(N, M, D\). Địa điểm có \(N\) ô theo hướng Bắc - Nam, \(M\) ô theo hướng Đông - Tây, và khu vực nghỉ gồm \(D\) ô liên tiếp theo một trong hai hướng đó.
  • Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu gồm \(M\) ký tự mô tả địa điểm. Ký tự thứ \(j\) của dòng thứ \(i\) mô tả ô ở hàng thứ \(i\) tính từ phía Bắc và cột thứ \(j\) tính từ phía Tây. Ký tự # nghĩa là ô có thiết bị, còn . nghĩa là ô không có thiết bị.

Dữ liệu ra

In ra một số nguyên trên một dòng: số cách bố trí khu vực nghỉ giải lao.

Ràng buộc

Các giá trị thỏa mãn:

  • \(1 \le N \le 100\).
  • \(1 \le M \le 100\).
  • \(2 \le D \le 100\).

Phân nhóm

Bài có năm bộ dữ liệu chấm, mỗi bộ trị giá \(20\) điểm.

Ví dụ

Ví dụ 1

Input 
3 5 2
...#.
#...#
....#
Output 
12
Giải thích

Có tổng cộng \(12\) cách bố trí khu vực nghỉ, như minh họa dưới đây.

Ví dụ 2

Input 
4 7 5
.#.....
.....##
.......
#......
Output 
7

Nguồn

Kỳ thi chọn đội tuyển Olympic Tin học Nhật Bản JOI 2016/2017, vòng sơ khảo, bài 3: Refreshment Area.

4. JOI 2017 - Plush Toys

Đ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 viên của JOI làm việc tại cửa hàng đồ chơi. Hôm nay, người này cần sắp xếp lại khu vực thú nhồi bông trong cửa hàng.

Trên một chiếc kệ, \(N\) con thú nhồi bông được đặt thành một hàng từ trái sang phải. Kệ được chia thành \(N\) ngăn và mỗi ngăn chứa đúng một con thú. Cửa hàng bán tổng cộng \(M\) loại thú nhồi bông, được đánh số từ \(1\) đến \(M\). Mỗi con thú trên kệ thuộc một trong \(M\) loại này, và mỗi loại xuất hiện ít nhất một lần.

Để trông đẹp mắt hơn, người này muốn sắp xếp lại sao cho tất cả thú nhồi bông cùng loại nằm liên tiếp trên kệ. Việc sắp xếp được thực hiện như sau:

  1. Chọn một số con trong \(N\) con thú và lấy chúng ra khỏi kệ. Vị trí của những con không bị lấy ra không thay đổi.
  2. Đặt những con đã lấy ra trở lại các ngăn trống theo thứ tự tùy ý.

Sau khi sắp xếp, tất cả thú nhồi bông cùng loại phải nằm liên tiếp trên kệ.

Hãy tính số thú nhồi bông ít nhất cần lấy ra để thực hiện việc sắp xếp.

Dữ liệu vào

Dữ liệu vào gồm \(N+1\) dòng:

  • Dòng thứ nhất chứa hai số nguyên \(N, M\), lần lượt là số thú nhồi bông và số loại thú.
  • Mỗi dòng trong \(N\) dòng tiếp theo chứa một số nguyên. Số nguyên trên dòng thứ \(i\) là loại của con thú nằm ở ngăn thứ \(i\) tính từ trái sang phải.

Dữ liệu ra

In ra một số nguyên trên một dòng: số thú nhồi bông ít nhất cần lấy ra.

Ràng buộc

Các giá trị thỏa mãn:

\[ 1 \le N \le 100\,000, \]
\[ 1 \le M \le 20. \]

Mỗi loại từ \(1\) đến \(M\) xuất hiện ít nhất một lần.

Phân nhóm

Bài có năm bộ dữ liệu chấm, mỗi bộ trị giá \(20\) điểm.

Ví dụ

Ví dụ 1

Input 
7 2
1
2
2
2
1
2
1
Output 
2
Giải thích

Ban đầu, các loại thú từ trái sang phải là \(1,2,2,2,1,2,1\). Một cách tối ưu là lấy con thứ nhất và con thứ sáu tính từ trái sang, sau đó đặt một con loại \(2\) vào ngăn thứ nhất và một con loại \(1\) vào ngăn thứ sáu. Khi đó chỉ cần lấy ra \(2\) con.

Ví dụ 2

Input 
12 4
1
3
2
4
2
1
2
3
1
1
3
4
Output 
7

Nguồn

Kỳ thi chọn đội tuyển Olympic Tin học Nhật Bản JOI 2016/2017, vòng sơ khảo, bài 4: Plush Toys.

5. JOI 2017 - Ridge

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

Miệng chảo JOI là một địa hình đẹp, được nhiều người leo núi yêu thích nhờ phong cảnh tuyệt vời. Đặc biệt, cảnh nhìn từ những nơi được gọi là sống núi rất ngoạn mục.

Miệng chảo JOI là một hình chữ nhật dài \(H\) kilômét theo hướng Bắc - Nam và \(W\) kilômét theo hướng Đông - Tây. Chia vùng đất theo từng kilômét ở cả hai hướng, ta thu được \(H \times W\) khu vực. Trong mỗi khu vực, độ cao là không đổi; độ cao của mọi cặp khu vực khác nhau đều khác nhau.

Khi mưa rơi xuống một khu vực, nước chảy sang tất cả các khu vực kề cạnh theo hướng Bắc, Nam, Đông hoặc Tây có độ cao thấp hơn khu vực đó. Nếu không có khu vực kề cạnh nào thấp hơn, nước đọng lại tại khu vực hiện tại. Nước chảy đến từ khu vực khác cũng tuân theo quy tắc này. Bên ngoài miệng chảo JOI là những vách núi dốc của vành miệng chảo, nên nước không thể chảy ra ngoài.

Một khu vực được gọi là sống núi nếu, khi mưa chỉ rơi xuống khu vực đó, cuối cùng nước đọng lại tại nhiều hơn một khu vực.

Hãy tính số khu vực là sống núi.

Dữ liệu vào

Dữ liệu vào gồm \(H+1\) dòng:

  • Dòng thứ nhất chứa hai số nguyên \(H, W\), cho biết kích thước của miệng chảo JOI theo hướng Bắc - Nam và Đông - Tây.
  • Mỗi dòng trong \(H\) dòng tiếp theo chứa \(W\) số nguyên. Số nguyên \(M_{i,j}\) ở vị trí thứ \(j\) trên dòng thứ \(i\) là độ cao của khu vực ở hàng thứ \(i\) tính từ phía Bắc và cột thứ \(j\) tính từ phía Tây.

Dữ liệu ra

In ra một số nguyên trên một dòng: số khu vực là sống núi.

Ràng buộc

Các giá trị thỏa mãn:

  • \(1 \le H \le 1\,000\).
  • \(1 \le W \le 1\,000\).
  • \(1 \le M_{i,j} \le H \times W\).

Với mọi \((i,j) \ne (k,l)\), ta có \(M_{i,j} \ne M_{k,l}\).

Phân nhóm

Bài có năm bộ dữ liệu chấm, mỗi bộ trị giá \(20\) điểm.

Ví dụ

Ví dụ 1

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

Bốn khu vực có độ cao \(5,7,8,9\) là sống núi. Chẳng hạn, nếu mưa rơi xuống khu vực có độ cao \(9\), cuối cùng nước đọng lại tại ba khu vực có độ cao \(1,2,3\), nên khu vực có độ cao \(9\) là sống núi. Nếu mưa rơi xuống khu vực có độ cao \(6\), cuối cùng nước chỉ đọng lại tại khu vực có độ cao \(1\), nên khu vực có độ cao \(6\) không phải là sống núi.

Ví dụ 2

Input 
3 5
5 3 8 2 14
9 10 4 1 13
12 7 11 6 15
Output 
4
Giải thích

Bốn khu vực có độ cao \(8,10,11,12\) là sống núi.

Nguồn

Kỳ thi chọn đội tuyển Olympic Tin học Nhật Bản JOI 2016/2017, vòng sơ khảo, bài 5: Ridge.

6. JOI 2017 - Snake JOI

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

JOI, một chú rắn, bị lạc vào một dinh thự rộng lớn. Chú phải thoát ra trước khi bị chủ dinh thự phát hiện.

Dinh thự có \(N\) căn phòng, được đánh số từ \(1\) đến \(N\), và \(M\) hành lang. Hành lang thứ \(i\) (\(1 \le i \le M\)) nối phòng \(A_i\) với phòng \(B_i\). JOI có thể đi qua mỗi hành lang theo cả hai hướng và cần \(D_i\) phút để đi qua hành lang thứ \(i\). Không có cách nào di chuyển giữa các phòng ngoài việc đi qua hành lang.

Nhiệt độ trong mỗi phòng được giữ cố định và đối với JOI, căn phòng đó hoặc quá lạnh, hoặc dễ chịu, hoặc quá nóng. Vì không thể thích nghi với sự thay đổi nhiệt độ đột ngột, JOI không được bước vào một căn phòng quá nóng khi chưa đủ \(X\) phút kể từ lần gần nhất rời khỏi một căn phòng quá lạnh. Tương tự, JOI không được bước vào một căn phòng quá lạnh khi chưa đủ \(X\) phút kể từ lần gần nhất rời khỏi một căn phòng quá nóng.

Trong lúc di chuyển, ngay sau khi bước vào một căn phòng, JOI phải lập tức rời khỏi căn phòng đó. Chú không được quay lại giữa hành lang hoặc mất nhiều hơn \(D_i\) phút để đi qua hành lang thứ \(i\). Tuy nhiên, JOI được phép bước vào lại một phòng đã từng đến và đi lại qua một hành lang đã từng sử dụng.

Ban đầu JOI đang ở phòng \(1\), một căn phòng quá lạnh. Khi bước vào phòng \(N\), nơi có lối ra, JOI thoát khỏi dinh thự.

Hãy tính thời gian ngắn nhất để JOI thoát khỏi dinh thự.

Dữ liệu vào

Dữ liệu vào gồm \(1+N+M\) dòng:

  • Dòng thứ nhất chứa ba số nguyên \(N, M, X\). Dinh thự có \(N\) phòng, \(M\) hành lang, và JOI cần \(X\) phút để thích nghi với sự thay đổi nhiệt độ.
  • Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(T_i\) mô tả nhiệt độ của phòng \(i\): \(T_i=0\) nếu phòng quá lạnh, \(T_i=1\) nếu phòng dễ chịu, và \(T_i=2\) nếu phòng quá nóng.
  • Trong \(M\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(A_j, B_j, D_j\). Hành lang thứ \(j\) nối phòng \(A_j\) với phòng \(B_j\) và cần \(D_j\) phút để đi qua. Có thể có nhiều hành lang nối cùng một cặp phòng.

Dữ liệu ra

In ra một số nguyên trên một dòng: số phút ít nhất để JOI thoát khỏi dinh thự.

Ràng buộc

Các giá trị thỏa mãn:

  • \(2 \le N \le 10\,000\).
  • \(1 \le M \le 20\,000\).
  • \(1 \le X \le 200\).
  • \(0 \le T_i \le 2\).
  • \(T_1=0\).
  • \(1 \le A_j < B_j \le N\).
  • \(1 \le D_j \le 200\).

Dữ liệu bảo đảm JOI có thể thoát khỏi dinh thự.

Phân nhóm

Bài có năm bộ dữ liệu chấm, mỗi bộ trị giá \(20\) điểm.

Ví dụ

Ví dụ 1

Input 
8 10 4
0
1
1
2
1
1
2
0
1 2 1
1 3 1
2 3 3
2 4 5
3 4 1
4 5 1
5 6 1
5 8 1
1 7 2
7 8 2
Output 
9
Giải thích

Lộ trình nhanh nhất đi qua các phòng theo thứ tự \(1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8\).

Ví dụ 2

Input 
15 25 4
0
1
1
0
2
1
0
1
1
2
0
0
1
0
1
8 11 1
7 10 1
12 14 1
3 8 1
1 5 1
3 9 1
3 8 1
1 5 1
6 15 1
11 12 1
2 14 1
7 10 1
11 12 1
5 13 1
2 8 1
1 4 1
2 11 1
5 6 1
1 13 1
6 12 1
5 10 1
9 13 1
4 10 1
3 12 1
7 13 1
Output 
6
Giải thích

Trong ví dụ này, một số cặp phòng, chẳng hạn phòng \(1\) và phòng \(5\), được nối bởi nhiều hành lang.

Nguồn

Kỳ thi chọn đội tuyển Olympic Tin học Nhật Bản JOI 2016/2017, vòng sơ khảo, bài 6: Snake JOI.