PRE THI HUYỆN #09 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Khóa số xoay vòng	30 (p)	1.0s	30M
2	Mua trái cây	25 (p)	1.0s	1G
3	Số đặc biệt	30 (p)	1.0s	1G
4	Số lập phương thứ K	25 (p)	1.0s	1G

1. Khóa số xoay vòng

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

Đọc đề ở tệp pdf

2. Mua trái cây

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

Hôm nay Hoa quyết định đi chợ mua hoa quả giúp mẹ. Khu chợ tại nơi sinh sống của Hoa bao gồm \(n\) gian hàng được xếp thành một vòng tròn. Các gian hàng được đánh số từ \(1\) đến \(n\) theo chiều kim đồng hồ (gian hàng \(n\) nằm cạnh gian hàng \(1\)). Gian hàng thứ \(i\) (\(1 ≤ i ≤ n\)) bán một loại quả với giá \(a_i\) đồng. Giả sử rằng mỗi gian hàng có một nguồn cung cấp không giới hạn.
Hoa muốn dùng \(m\) đồng để mua hoa quả. Kế hoạch mua của Hoa là như sau:

Đầu tiên, Hoa ghé thăm gian hàng \(1\), Hoa sẽ mua đúng một quả nếu còn đủ tiền.
Sau đó, Hoa sẽ di chuyển qua gian hàng bên cạnh theo chiều kim đồng hồ và tiếp tục kế hoạch.
Vì số tiền của Hoa có giới hạn, kế hoạch sẽ dừng lại khi Hoa không còn đủ tiền để mua bất kỳ loại quả nào.

Yêu cầu:

Hãy tìm số lượng quả mà Hoa mua được.

Input

Dòng đầu tiên chứa số nguyên \(n\) và \(m\) (\(1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^{18}\)) lần lượt là số lượng gian hàng và số tiền tối đa mà Hoa có thể dùng.
Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\); (\(1 ≤ a_i ≤ 10^9\)) là giá tiền của mỗi loại quả tại mỗi gian hàng.

Ouput

In ra một số nguyên duy nhất là số lượng quả mà Hoa mua được.

Scoring

Subtask 1 (10% số điểm): \(n = 2\)
Subtask 2 (30% số điểm): \(a_1 ≤ a_2 ≤…≤ a_n\)
Subtask 3 (30% số điểm): \(m ≤ min(a_1, a_2, ..., a_n)*10^6\)
Subtask 4 (30% số điểm): Không có ràng buộc gì thêm.

Ví dụ 1:

Input

3 38
5 2 5

Output

Giải thích

Trong ví dụ đầu tiên, cả quá trình diễn ra như sau:
Ghé thăm gian hàng 1, mua một quả với giá 5 đồng, còn 33 đồng.
Ghé thăm gian hàng 2, mua một quả với giá 2 đồng, còn 31 đồng.
Ghé thăm gian hàng 3, mua một quả với giá 5 đồng, còn 26 đồng.
Ghé thăm gian hàng 1, mua một quả với giá 5 đồng, còn 21 đồng.
Ghé thăm gian hàng 2, mua một quả với giá 2 đồng, còn 19 đồng.
Ghé thăm gian hàng 3, mua một quả với giá 5 đồng, còn 14 đồng.
Ghé thăm gian hàng 1, mua một quả với giá 5 đồng, còn 9 đồng.
Ghé thăm gian hàng 2, mua một quả với giá 2 đồng, còn 7 đồng.
Ghé thăm gian hàng 3, mua một quả với giá 5 đồng, còn 2 đồng.
Ghé thăm gian hàng 1, không đủ tiền để mua.
Ghé thăm gian hàng 2, mua một quả với giá 2 đồng, còn 0 đồng.
Kế hoạch dừng lại.

Ví dụ 2:

Input

5 21
2 4 100 2 6

Output

3. Số đặc biệt

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

Một số nguyên \(M > 1\) được gọi là một số đặc biệt nếu nó thoả mãn: Tổng các chữ số của\(M\) bằng tổng các chữ số của tất cả các thừa số nguyên tố trong dạng phân tích của nó. Chẳng hạn như số 4937775 là một số đặc biệt vì:

4937775 = 3 . 5 . 5 . 65837
Có: 4 + 9 + 3 + 7 + 7 + 7 + 5 = 42
Và: 3 + 5 + 5 + 6 + 5 + 8 +3 + 7 = 42

Lưu ý: Số nguyên tố không được xem là số đặc biệt.

Yêu cầu:

Cho trước số nguyên dương N. Tìm số đặc biệt nhỏ nhất lớn hơn N.

Dữ liệu vào:

Gồm duy nhất 1 dòng là số nguyên dương \(N\), (\(N \leq 10^9)\).

Kết quả:

Gồm duy nhất 1 dòng là 1 số đặc biệt nhỏ nhất lớn hơn \(N\).

Ví dụ:

Input

Output

4. Số lập phương thứ K

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

Cho số nguyên dương \(k\).

Yêu cầu:

Tìm số thứ \(k\) mà lập phương của nó có ba chữ số tận cùng là 888

Input

Dòng 1: (\(t ≤ 10^3\)) - số câu hỏi.
\(t\) dòng tiếp theo, mỗi dòng gồm (\(k≤10^{18}\))

Output

Ứng với mỗi test in ra số thứ \(k\) mà lập phương của nó có ba chữ số cuối cùng là 888. Dữ liệu đảm bảo kết quả không vượt quá \(2^{63}\)

Ví dụ:

Input

1
1

Output

Giải thích

\(192^3\) =7077888