Dinh Can's Blog

ĐỀ THI TIN HỌC TRẺ BẢNG A HUYỆN PHÚ HÒA 2023

ĐỀ THI THT BẢNG A - KHỐI TIỂU HỌC HUYỆN HƯƠNG SƠN 2023

Trong một lần leo núi, Nam đi lạc vào một khu rừng già, nơi có một tòa lâu đài bị lãng quên. Khi bước vào một căn phòng rực rỡ ánh sáng trong tòa lâu đài đó, Nam thấy một nàng công chúa đang nằm ngủ. Nam cố đánh thức nàng dậy mà không được. Nhìn xung quanh, Nam thấy có một quyển sách cùng một cây đũa bạc được để ngay ngắn trên bàn. Tò mò lật ra xem, thì ra đó là cuốn sổ mà bà phù thủy ghi lại câu thần chú bằng tiếng Anh cùng với hướng dẫn cách đánh thức nàng công chúa có thể tỉnh lại.

            Để đánh thức được nàng, Nam phải đọc câu thần chú ấy nhiều lần, sau đó dùng cây đũa bạc gõ nhẹ lên trán công chúa vài cái nữa. Số lần đọc câu thần chú và số lần gõ đũa phải làm đúng như yêu cầu thì mới hiệu nghiệm.

            Để biết được số lần đọc thần chú, Nam cần biết được trong câu thần chú kia có tất cả bao nhiêu loại chữ cái khác nhau (không phân biệt chữ in hoa và chữ in thường)? Số loại chữ cái đó chính là số lần Nam phải đọc.

            Để biết được số lần gõ đũa, Nam cần biết được, chữ cái nào xuất hiện nhiều nhất trong câu thần chú, và số lần xuất hiện của chữ cái đó là bao nhiêu lần? Số lần đó chính là số lần mà Nam phải gõ đũa lên trán công chúa.

            Hãy giúp Nam trả lời hai câu hỏi trên bằng khả năng lập trình của mình nhé.

            Dữ liệu vào: Được cho trong tệp văn bản CUU.INP gồm duy nhất một xâu kí tự là nội dung của câu thần chú, được ghi trên cùng một dòng, có độ dài không vượt quá 10⁶ kí tự.

            Kết quả ra: Ghi ra tệp văn bản CUU.OUT gồm hai số nguyên dương được ghi trên cùng một dòng, theo thứ tự là số lần đọc câu thần chú và số lần gõ đũa, mỗi số cách nhau một dấu cách.

            Ví dụ:

Nhân dịp tết trung thu, Nam được mẹ cho đi dự lễ hội “Đêm trăng rằm”, tại lễ hội Nam đã tích cực tham gia các chương trình đố vui và giành được số điểm là X. Nam muốn tặng bố mẹ mỗi người một món quà theo chương trình đổi điểm lấy quà của ban tổ chức. Biết rằng ban tổ chức có N món quà, món thứ i phải dùng a[i] điểm để đổi (1 ≤ i ≤ N). Với số điểm có được Nam quyết định sẽ đổi 2 món quà khác nhau có tổng giá trị lớn nhất có thể được.

            Yêu cầu: Hãy xác định số điểm Nam dùng quà để đổi tặng bố mẹ.

Dữ liệu nhập:

- Dòng thứ nhất là hai số nguyên N và X (2 ≤ N ≤ 10⁵; 2 ≤ X ≤ 10⁹)

- Dòng thứ hai là dãy a[1], a[2], …, a[n] (1 ≤ a[i] ≤ 10⁹)

Kết quả:

            - In ra một số duy nhất là số điểm quà đã đổi của Nam.

Ràng buộc:

            - 50% test: 1 ≤ N ≤ 1000

Ví dụ:

Cho danh sách A gồm K từ phân biệt và danh sách B gồm N ký tự.

            Yêu cầu: lần lượt xét các ký tự trong danh sách B từ trên xuống, với mỗi ký tự c, hãy ghi ra từ w tìm được trong danh sách A thỏa thứ tự ưu tiên sau:

            1. Từ w phải bắt đầu bằng ký tự c.

            2. Nếu có nhiều từ w bắt đầu bằng ký tự c, chọn từ được lấy ít nhất trong các lần trước đó.

            3. Nếu có nhiều hơn 1 từ thỏa điều kiện 1, 2; lấy từ có độ lớn (thứ tự từ điển) bé nhất.

            Dữ liệu vào đảm bảo với mỗi ký tự có đúng 1 từ được chọn.

            Input:

·        Dòng đầu ghi hai số nguyên dương K, N (1 ≤ K, N ≤ 10⁵)

·        K dòng sau, mỗi dòng ghi 1 từ độ dài không quá 21 ký tự.

·        N dòng sau, mỗi dòng ghi 1 ký tự.

Từ và ký tự chỉ gồm các chữ cái viết thường {a … z}

Output: Ghi N dòng, mỗi dòng là 1 từ tìm được theo yêu cầu.

Ví dụ: