Trong một đợt nâng cấp hệ thống máy chủ tại trung tâm dữ liệu của Khoa Công nghệ Thông tin - Trường Đại học Công nghệ Thông tin và Truyền thông (ICTU), một sự cố xung đột phần mềm đã xảy ra khiến hai chỉ số quan trọng trong thuật toán bảo mật bị biến mất.

Kỹ sư hệ thống chỉ còn tìm lại được hai thông số còn sót lại trong file log:

1. M: Độ dài của dãy mã khóa (số lượng chữ số).

2. S: Tổng kiểm tra (checksum) của toàn bộ dãy mã đó.

Theo quy định bảo mật của ICTU, hệ thống sử dụng cơ chế "Khóa Kép" để khởi động lại:

• Mã Ưu Tiên Cao (Số lớn nhất): Dùng để cấp quyền cho các quản trị viên hệ thống.

• Mã Ưu Tiên Thấp (Số nhỏ nhất): Dùng để cấp quyền cho các node cảm biến trong mạng IoT của trường.

Tuy nhiên, các dãy mã này không được phép bắt đầu bằng chữ số 0 (trừ khi dãy mã chỉ có duy nhất 1 chữ số và tổng bằng 0).

Nhiệm vụ: Là một sinh viên yêu thích lập trình của khoa Công nghệ máy tính, em hãy viết chương trình khôi phục lại hai dãy mã này từ các thông số M và S để giúp nhà trường vận hành lại hệ thống.

Dữ liệu vào (Input):

Một dòng duy nhất chứa hai số nguyên M (1 <= M <= 100) và S (0 <= S <= 900)

Dữ liệu ra (Output):

• Dòng 1: In ra Mã Ưu Tiên Cao (số lớn nhất).

• Dòng 2: In ra Mã Ưu Tiên Thấp (số nhỏ nhất).

• Nếu không thể tạo ra số nào thỏa mãn điều kiện, in ra NOT FOUND.

Ví dụ:

Input 01:

2 16

Output 01:

97
79

Input 02:

3 0

Output 02:

NOT FOUND

Input 03:

1 0

Output 03:

0 0

Ràng buộc:

Có 30% số điểm tương ứng với M <= 6

Có 40% số điểm tương tứng với M <= 15

Có 30% số điểm còn lại không có ràng buộc gì thêm (full test) (16 <= M <= 100)

Thời gian: <= 1.0s

Bộ nhớ: <= 256MB.

Trong chương trình chuyển đổi số quốc gia, nhóm sinh viên tình nguyện của Khoa Công nghệ Thông tin - Trường Đại học Công nghệ Thông tin và Truyền thông (ICTU) thực hiện dự án lắp đặt trạm phát sóng WiFi miễn phí cho N hộ gia đình dọc theo tuyến đường quốc lộ tại các xã vùng xa.

Các hộ gia đình nằm rải rác trên một trục đường thẳng (coi là trục tọa độ OX), nhà thứ i có tọa độ là Xi. Nhóm chỉ được cấp kinh phí để lắp đặt tối đa K trạm phát sóng. Mỗi trạm phát sóng khi được đặt tại vị trí P bất kỳ sẽ có bán kính phủ sóng là R. Điều này có nghĩa là tất cả các ngôi nhà nằm trong đoạn [P - R, P + R] đều sẽ có tín hiệu mạng. Để tiết kiệm chi phí vận hành mà vẫn đảm bảo 100% hộ dân đều có sóng WiFi, nhóm nghiên cứu cần tìm ra giá trị bán kính R nhỏ nhất có thể.

Nhiệm vụ: Hãy giúp nhóm nghiên cứu ICTU xác định bán kính R tối ưu này.

Dữ liệu vào (Input):

• Dòng 1: Hai số nguyên N và K (1 <= K <= N <= 10^5)là số hộ gia đình và số trạm phát sóng

• Dòng 2: N số nguyên X1, X2, ..., Xn đã được sắp xếp tăng dần với Xi là tọa độ của nhà thứ i (0 <= Xi <= 10^9)

Kết quả ra (Output):

• Một số thực là giá trị R nhỏ nhất tìm được là bán kính tối ưu, làm tròn đúng 1 chữ số thập phân.

Ví dụ:

Input:

3 1
1 3 5

Output:

2.0

Giải thích: Có 3 nhà tại tọa độ 1, 3, 5. Chỉ có 1 trạm. Ta đặt trạm đặt tại tọa độ 3.0 sẽ phủ được toàn bộ khoảng cách từ 1.0 đến 5.0 (bán kính R=2.0).

Ràng buộc:

Có 30% số điểm tương ứng với N, K <= 10

Có 40% số điểm tương tứng với N, K <= 2000

Có 30% số điểm còn lại không có ràng buộc gì thêm (full test) (2001 <= K <= N <= 10^5; 0 <= Xi <= 10^9)

Thời gian: \le\ 1.0s 

Bộ nhớ: \le\ 256MB.

Trong Hội xuân tại Thái Nguyên, Ban tổ chức có các mệnh giá tiền thưởng: 1, 2, 5, 10, 20, 50, 100, 200, 500 (đơn vị nghìn đồng). Một học sinh trúng thưởng số tiền là N nghìn đồng. Ban tổ chức muốn trao thưởng cho học sinh này bằng số lượng tờ tiền ít nhất có thể. Hãy tính số tờ tiền ít nhất cần dùng.

Dữ liệu vào: Số nguyên dương N (1 <= N <= 10^9).

Kết quả ra: Số lượng tờ tiền ít nhất.Ví dụ:

Input:

845

Output:

6

(Giải thích: 1 tờ 500, 1 tờ 200, 1 tờ 100, 2 tờ 20, 1 tờ 5).

Đêm hội trăng rằm, có N em nhỏ, em thứ i có mức độ thèm ăn là gi. Thầy có M chiếc kẹo, chiếc thứ j có kích thước là sj. Một em nhỏ chỉ cảm thấy vui nếu nhận được 1 chiếc kẹo có kích thước sj >= gi. Mỗi em chỉ được nhận tối đa 1 chiếc kẹo. Hãy tìm số lượng em nhỏ tối đa được vui vẻ.

Dữ liệu vào:

Dòng 1: Hai số nguyên N và M (1 <= N, M <= 10^5).

Dòng 2: N số nguyên gi (1 <= gi <= 10^9).

Dòng 3: M số nguyên sj (1 <= sj <= 10^9).

Kết quả ra: Số lượng em nhỏ vui vẻ tối đa.

Ví dụ:

Input:

3 2
1 2 3
1 1

Output:

1

(Chỉ chia được kẹo s=1 cho em g=1).

Có N chiếc xe điện VinFast cần vào trạm sạc. Chiếc thứ i đến vào thời điểm Ai và rời đi vào thời điểm Di. Nếu 2 xe có thời gian sạc trùng nhau (kể cả tại mốc thời gian đến/đi), chúng phải dùng 2 trụ sạc khác nhau. Hỏi trạm cần trang bị ít nhất bao nhiêu trụ sạc để không xe nào phải chờ?

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

N dòng tiếp theo: Mỗi dòng chứa 2 số nguyên Ai và Di (0 <= Ai <= Di <= 2359, định dạng HHMM).

Kết quả ra: Số trụ sạc tối thiểu.

Ví dụ:

Input:

3
900 930
915 1200
930 1100

Output:

3

(Tại thời điểm 930 có 3 xe cùng ở trạm).