HSG THCS Hà Nội 2017

Cho hai số nguyên dương \(n\) và \(k\), với \(1 \leq k < n\).

Yêu cầu: Đếm xem trong các số nguyên từ \(1\) đến \(n\) có bao nhiêu số có đúng \(k\) ước số nguyên dương khác nhau.

Input

• Hai số nguyên dương \(n\) và \(k\) \((1 \leq k < n \leq 10^5)\).

Output

• Số lượng các số có đúng \(k\) ước số nguyên dương khác nhau.

Example

8 4

2

Một siêu thị thực hiện ưu đãi khi bán các sản phẩm cho khách hàng như sau: Nếu khách hàng mua \(p\) sản phẩm, với \(p \geq k\) thì không phải thanh toán tiền cho một sản phẩm có giá tiền nhỏ nhất. Ví dụ, với \(k = 2\), khi thanh toán 3 sản phẩm có giá lần lượt là 250, 1000, 200 (đơn vị là nghìn đồng), khách hàng không phải thanh toán tiền cho sản phẩm có giá 200 và chỉ phải trả số tiền là 1250.

Một khách hàng cần mua \(n\) sản phẩm ở siêu thị và biết sản phẩm thứ \(i\) \((1 \leq i \leq n)\) có giá tiền là \(a_i\) (nghìn đồng). Khách hàng có thể thực hiện mua \(n\) sản phẩm thành nhiều lần để được hưởng ưu đãi của siêu thị một cách có lợi nhất.

Yêu cầu: Tìm tổng số tiền ít nhất mà khách hàng phải trả khi mua đủ \(n\) sản phẩm.

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(k\) \((1 \leq n \leq 10^3, \ 2 \leq k \leq 10^2)\).
• Dòng sau chứa \(n\) số nguyên dương \(a_i\) \((1 \leq i \leq n)\), mỗi số không vượt quá \(10^6\).

Output

• Tổng số tiền ít nhất mà khách hàng phải trả.

Example

5 2
250 1000 100 3000 200

3350

Cho \(n\) xâu kí tự \(s_1, s_2, \ldots, s_n\) và một xâu mẫu \(s\) có cùng độ dài \(d\) chỉ gồm các chữ cái thường tiếng Anh. Một phép biến đổi xâu \((i, j, k)\) thực hiện đổi chỗ kí tự thứ \(k\) của hai xâu \(s_i\) và \(s_j\) \((1 \leq i < j \leq n,\ 1 \leq k \leq d)\).

Yêu cầu: Tìm số lượng ít nhất các phép biến đổi xâu cần thực hiện trên \(n\) xâu \(s_1, s_2, \ldots, s_n\) để nhận được xâu mẫu \(s\).

Input

• Dòng đầu chứa số nguyên \(n\) \((2 \leq n \leq 100)\);
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) \((1 \leq i \leq n)\) chứa xâu \(s_i\) gồm \(d\) chữ cái thường tiếng Anh \((2 \leq d \leq 100)\);
• Dòng cuối chứa xâu mẫu \(s\) gồm \(d\) chữ cái thường tiếng Anh.

Output

• Ghi ra số lượng ít nhất các phép biến đổi xâu cần thực hiện. Trong trường hợp không có phương án tiến hành các phép biến đổi xâu trên \(n\) xâu \(s_1, s_2, \ldots, s_n\) để nhận được xâu mẫu \(s\) thì ghi số \(-1\).

Example

3
abc
cab
bca
acb

2

Thành phố Anpha dự định xây dựng sân bay trên một vùng đất được mô tả bởi bản đồ hình chữ nhật có kích thước \(m\) hàng, \(n\) cột. Mỗi ô trên bản đồ chứa một số nguyên (đơn vị mét) là độ cao (so với mực nước biển) của một ô đất ngoài thực địa. Thành phố dự định thiết kế một đường băng cho sân bay nằm trọn trong bản đồ này. Để làm đường băng cần phải san phẳng một dãy các ô liền nhau tạo thành hình chữ nhật có chiều dài \(\geq d\) ô, chiều rộng \(\geq r\) ô và độ cao của mỗi ô là \(h\) mét. Chi phí để san phẳng các ô trên đường băng này bằng tổng độ chênh lệch giữa độ cao mỗi ô đã chọn so với \(h\).

Yêu cầu: Xác định chi phí nhỏ nhất để san phẳng các ô được chọn xây dựng đường băng.

Input

• Dòng đầu chứa hai số nguyên \(m, n\) \((2 < m, n \leq 500)\);
• Dòng thứ hai chứa ba số nguyên \(d, r, h\) \((1 < r;\ d \leq 200,\ 1 < h \leq 10^4)\);
• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) số nguyên mô tả độ cao các ô trong hàng thứ \(i\) của bản đồ, mỗi số có giá trị tuyệt đối không vượt quá \(10^4\).

Output

• Chi phí nhỏ nhất để san phẳng các ô đã chọn. Trong trường hợp không có phương án xây dựng đường băng thì ghi số \(-1\).

Example

5 6
4 2 2
3 4 2 4 3 3
4 5 2 2 5 3
1 4 3 2 5 4
3 4 2 1 5 3
3 4 2 3 1 5

3