THTA 2026 Hải Châu - Đà Nẵng - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Xếp hộp trong kho (THT A Hải Châu, Đà Nẵng 2026)	30 (p)	1.0s	256M
2	Mua bút chì cho lớp học (THT A Hải Châu, Đà Nẵng 2026)	30 (p)	1.0s	256M
3	Chữ số cuối cùng (THT A Hải Châu, Đà Nẵng 2026)	25 (p)	1.0s	256M
4	Mã hóa dịch vòng ký tự (THT A Hải Châu, Đà Nẵng 2026)	15 (p)	1.0s	256M

1. Xếp hộp trong kho (THT A Hải Châu, Đà Nẵng 2026)

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

Một nhà kho có dạng hình chữ nhật kích thước \(A \times B\). Người ta muốn xếp các thùng hàng hình vuông cạnh \(k\) (\(8 \le k \le 25\)).

Yêu cầu:

Các thùng phải đặt song song với tường kho.
Không được chồng lên nhau.
Không vượt ra ngoài kho.
Tìm giá trị \(k\) trong khoảng \([8, 25]\) sao cho phần diện tích trống còn lại là nhỏ nhất.

Input

Một dòng duy nhất chứa hai số nguyên \(A, B\) (\(20 \le A, B \le 10^7\)).

Output

In ra một số duy nhất là diện tích trống nhỏ nhất tìm được.

Example

Test 1

Input

30 30

Output

Note

Trường hợp \(k = 15\):

Số thùng xếp được theo chiều dài: \(30 / 15 = 2\).
Số thùng xếp được theo chiều rộng: \(30 / 15 = 2\).
Tổng số thùng: \(2 \cdot 2 = 4\) thùng.
Diện tích đã dùng: \(4 \cdot (15 \cdot 15) = 900\).
Diện tích trống: \(30 \cdot 30 - 900 = 0\).
Đây là diện tích trống nhỏ nhất có thể đạt được.

Test 2

Input

23 17

Output

Note

Trường hợp \(k = 17\):

Xếp được \(1\) thùng.
Diện tích đã dùng: \(17 \cdot 17 = 289\).
Diện tích trống: \((23 \cdot 17) - 289 = 391 - 289 = 102\).
Đây là diện tích trống nhỏ nhất khi xét \(k\) từ \(8\) đến \(25\).

Constraints

\(20 \le A, B \le 10^7\).
\(8 \le k \le 25\).

2. Mua bút chì cho lớp học (THT A Hải Châu, Đà Nẵng 2026)

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

Để chuẩn bị cho năm học mới, cô giáo cần mua một số lượng lớn bút chì để phát cho học sinh trong lớp. Một cửa hàng văn phòng phẩm đưa ra các mức giá ưu đãi như sau:

Mua lẻ từng cây bút chì: giá \(3\) đồng/cây;
Mua theo gói \(4\) cây: giá \(10\) đồng/gói;
Mua theo gói \(9\) cây: giá \(20\) đồng/gói.

Cô giáo có thể mua kết hợp nhiều loại (gói và lẻ) để đạt được đúng số lượng bút cần thiết. Các gói không được tách ra.

Yêu cầu: Hãy giúp cô giáo tính số tiền ít nhất cần chi để mua đúng \(N\) cây bút chì.

Input

Gồm một dòng duy nhất chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).

Output

In ra một số nguyên duy nhất là chi phí nhỏ nhất để mua đúng \(N\) cây bút chì.

Example

Test 1

Input

Output

Note

Cô giáo mua \(1\) gói \(4\) cây bút chì.

Test 2

Input

Output

Note

Cô giáo mua \(1\) gói \(9\) cây và \(1\) cây lẻ (\(20 + 3 = 23\)).

3. Chữ số cuối cùng (THT A Hải Châu, Đà Nẵng 2026)

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

Cho dãy số: \(1, 1 \cdot 2, 1 \cdot 2 \cdot 3, 1 \cdot 2 \cdot 3 \cdot 4, \dots\) (số thứ \(N\) là tích của các số từ \(1\) đến \(N\)).

Yêu cầu: Đưa ra chữ số cuối cùng khác \(0\) của số thứ \(N\) trong dãy là số nào?

Input

Nhập vào số tự nhiên \(N\) (\(N \le 10^6\)).

Output

Đưa ra chữ số cuối cùng khác \(0\) của số thứ \(N\) trong dãy.

Example

Test 1

Input

Output

Note

\(1 \cdot 2 \cdot 3 \cdot 4 = 24\). Chữ số cuối cùng là \(4\).

Test 2

Input

Output

Note

\(1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120\). Chữ số cuối cùng khác \(0\) là \(2\).

4. Mã hóa dịch vòng ký tự (THT A Hải Châu, Đà Nẵng 2026)

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

Cho một chuỗi \(S\) chỉ gồm các chữ cái in thường (a \(\to\) z). Thực hiện mã hóa bằng cách dịch mỗi ký tự sang phải \(K\) đơn vị trong bảng chữ cái.

Sau z quay vòng về a.
\(K\) là số nguyên không âm (\(K \leq 26\)).

Ví dụ: a dịch \(2 \to\) c, z dịch \(1 \to\) a.

Input

Dòng 1: Nhập chuỗi \(S\) (\(|S| \leq 10^5\)).
Dòng 2: Nhập số nguyên \(K\) (\(K \leq 26\)).

Output

In ra chuỗi đã được mã hóa.

Example

Test 1

Input

abcxyz
2

Output

cdezab

Test 2

Input

algorithm
26

Output

algorithm