JOI 2015/2015 - Vòng sơ khảo - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2015 - Water Rate	100 (p)	10.0s	256M
2	JOI 2015 - Christmas Party	100 (p)	10.0s	256M
3	JOI 2015 - Weather Forecaster	100 (p)	10.0s	256M
4	JOI 2015 - Silk Road	100 (p)	10.0s	256M
5	JOI 2015 - Sandcastle	100 (p)	10.0s	1G
6	JOI 2015 - Treasures	100 (p)	10.0s	1G

1. JOI 2015 - Water Rate

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

JOI sống tại khu vực có hai công ty nước X và Y. Công ty X thu \(A\) yên cho mỗi lít. Công ty Y thu phí cơ bản \(B\) yên nếu lượng dùng không quá \(C\) lít; với mỗi lít vượt quá \(C\), công ty thu thêm \(D\) yên.

Nhà JOI dùng \(P\) lít trong một tháng. Hãy tính số tiền ít nhất khi chọn công ty rẻ hơn.

Dữ liệu vào

Năm dòng lần lượt chứa các số nguyên \(A,B,C,D,P\).

Dữ liệu ra

In chi phí nước nhỏ nhất trong một tháng.

Ràng buộc

\[ 1 \le A,B,C,D,P \le 10\,000. \]

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Ở ví dụ 1, X thu \(9\times10=90\) yên, còn Y thu \(100\) yên.

Ví dụ 2

Input

Output

Giải thích

Ở ví dụ 2, X thu \(2000\) yên, còn Y thu \(300+10\times150=1800\) yên.

2. JOI 2015 - Christmas Party

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

JOI tổ chức tiệc với \(N\) người bạn. Trong mỗi ván, JOI bí mật chọn một người làm mục tiêu. Mỗi người đoán mục tiêu bằng cách ghi tên một người; riêng mục tiêu luôn ghi tên mình. Người đoán đúng được \(1\) điểm. Ngoài ra, nếu có \(X\) người đoán sai thì mục tiêu được thêm \(X\) điểm.

Sau \(M\) ván, hãy tính tổng điểm của từng người.

Dữ liệu vào

Dòng 1: \(N\).
Dòng 2: \(M\).
Dòng 3: \(A_1,\ldots,A_M\), trong đó \(A_i\) là mục tiêu ván \(i\).
\(M\) dòng tiếp theo: dòng \(i\) chứa \(B_{i,1},\ldots,B_{i,N}\), tên mà mỗi người ghi trong ván \(i\). Luôn có \(B_{i,A_i}=A_i\).

Dữ liệu ra

In \(N\) dòng; dòng \(j\) là tổng điểm của người \(j\).

Ràng buộc

\[ 3\le N,M\le100, \]

\[ 1\le A_i,B_{i,j}\le N. \]

Ví dụ

Ví dụ 1

Input

Output

3
4
5

Ví dụ 2

Input

Output

3. JOI 2015 - Weather Forecaster

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

Thành phố JOI là lưới \(H\times W\). Mây hiện diện được ký hiệu c, ô không mây là .. Mỗi phút, mọi đám mây dịch đúng một ô về phía đông; không có mây đi vào thành phố từ bên ngoài.

Với mỗi ô, hãy xác định số phút đến lần đầu mây xuất hiện trên ô đó.

Dữ liệu vào

Dòng đầu chứa \(H,W\). Mỗi trong \(H\) dòng sau là một xâu \(W\) ký tự mô tả một hàng từ bắc xuống nam.

Dữ liệu ra

In \(H\) dòng, mỗi dòng \(W\) số. In 0 nếu ô đang có mây và -1 nếu mây không bao giờ tới; không có khoảng trắng thừa đầu hoặc cuối dòng.

Ràng buộc

\[ 1\le H,W\le100. \]

Ví dụ

Ví dụ 1

Input

3 4
c..c
..c.
....

Output

0 1 2 0
-1 -1 0 1
-1 -1 -1 -1

Ví dụ 2

Input

6 8
.c......
........
.ccc..c.
....c...
..c.cc..
....c...

Output

-1 0 1 2 3 4 5 6
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 1 2 0 1
-1 -1 -1 -1 0 1 2 3
-1 -1 0 1 0 0 1 2
-1 -1 -1 -1 0 1 2 3

4. JOI 2015 - Silk Road

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

Có \(N+1\) thành phố đánh số \(0\) đến \(N\) từ tây sang đông; khoảng cách giữa thành phố \(i-1\) và \(i\) là \(D_i\). JOI phải đi từ \(0\) đến \(N\) trong không quá \(M\) ngày. Mỗi ngày anh có thể chờ, hoặc đi một chặng về phía đông.

Thời tiết xấu của ngày \(j\) là \(C_j\). Đi chặng \(i\) vào ngày \(j\) gây mệt mỏi \(D_iC_j\); chờ không gây mệt. Hãy tìm tổng độ mệt nhỏ nhất.

Dữ liệu vào

Dòng đầu: \(N,M\).
\(N\) dòng tiếp: \(D_1,\ldots,D_N\), mỗi số trên một dòng.
\(M\) dòng tiếp: \(C_1,\ldots,C_M\), mỗi số trên một dòng.

Dữ liệu ra

In tổng độ mệt nhỏ nhất.

Ràng buộc

\[ 1\le N\le M\le1000, \]

\[ 1\le D_i,C_j\le1000. \]

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Trong ví dụ 1, JOI chờ ngày 1 và 4, rồi đi vào các ngày 2, 3, 5; tổng là \(10\times30+25\times15+15\times30=1125\).

Ví dụ 2

Input

Output

5. JOI 2015 - Sandcastle

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

Một vùng bãi biển là lưới \(H\times W\). Mỗi ô là đất trống . hoặc một phần lâu đài cát, được ghi bằng chữ số từ 1 đến 9 biểu thị độ bền. Toàn bộ ô biên là đất trống.

Mỗi khi một con sóng tới, mọi ô lâu đài có số ô đất trống trong tám ô kề (cạnh hoặc góc) ít nhất bằng độ bền của nó sẽ đồng thời sụp thành đất trống. Hãy đếm số con sóng làm sụp ít nhất một ô trước khi trạng thái ổn định.

Dữ liệu vào

Dòng đầu chứa \(H,W\), sau đó là \(H\) xâu độ dài \(W\) mô tả lưới.

Dữ liệu ra

In số con sóng làm sụp ít nhất một ô.

Ràng buộc

\[ 2\le H,W\le1000. \]

Mọi ký tự ở biên đều là .. Trong bộ dữ liệu 1, \(H,W\le50\).

Ví dụ

Ví dụ 1

Input

5 6
......
.939..
.3428.
.9393.
......

Output

Ví dụ 2

Input

10 10
..........
.99999999.
.9.323239.
.91444449.
.91444449.
.91444449.
.91444449.
.91232329.
.99999999.
..........

Output

6. JOI 2015 - Treasures

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

Anna và Bruno tìm thấy \(N\) báu vật. Mỗi vật có giá thị trường \(X_i\) và độ quý hiếm \(Y_i\). Mỗi vật có thể được Anna lấy, Bruno lấy, hoặc để lại; không thể thuộc cả hai.

Anna hài lòng nếu trị tuyệt đối hiệu tổng giá thị trường hai người lấy không quá \(D\). Trong các cách làm Anna hài lòng, hãy tối đa hóa tổng độ quý hiếm của Bruno trừ tổng độ quý hiếm của Anna.

Dữ liệu vào

Dòng đầu chứa \(N,D\). Mỗi trong \(N\) dòng sau chứa \(X_i,Y_i\).

Dữ liệu ra

In giá trị lớn nhất có thể.

Ràng buộc

\[ 1\le N\le30,\qquad 0\le D\le10^{15}, \]

\[ 0\le X_i,Y_i\le10^{15}. \]

Trong bộ dữ liệu 1, \(N\le10\). Trong bộ dữ liệu 2, \(D=0\).

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Ở ví dụ 1, Anna lấy các vật 2, 3, 5 và Bruno lấy 1, 6. Hiệu giá thị trường là \(10\le15\) và hiệu độ quý hiếm là \(1600-400=1200\).

Ví dụ 2

Input

5 0
0 1000000000000000
0 1000000000000000
1 1
1000000000000000 0
1000000000000000 0

Output

2000000000000000