Dinh Can's Blog

ĐỀ THI TIN HỌC TRẺ BẢNG B TỈNH HẢI DƯƠNG 2023

Cho một bảng ô vuông gồm n dòng và m cột. Các dòng được đánh số từ 1 đến n, các cột được đánh số từ 1 đên m. Ô nằm ở dòng i và cột j được gọi là ô (i, j). Có k ô màu đen trên bảng, ô đen thứ i nằm ở vị trí (x_i, y_i). Các ô còn lại trong bảng đều có màu trắng.

            Bạn có thể thực hiện một trong hai loại thao tác sau (mỗi thao tác có thể được thực hiện nhiều lần hoặc không lần nào).

            - Chọn một dòng chỉ gồm các ô màu trắng, và xóa dòng đó khỏi bảng.

            - Chọn một cột chỉ gồm các ô màu trắng, và xóa cột đó khỏi bảng.

            Hãy tìm cách thực hiện các loại thao tác trên, sao cho số ô còn lại trong bảng là nhỏ nhất có thể.

Dữ liệu vào:

            - Dòng đầu tiên gồm ba số nguyên n, m, k (1 ≤ n, m, k ≤ 10⁵) – số dòng, số cột của bảng và số ô đen.

            - k dòng tiếp theo, dòng thứ i gồm hai số nguyên x_i, y_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m) – vị trí của ô đen thứ i. Dữ liệu vào đảm bảo không có hai ô đen nào ở cùng vị trí.

Dữ liệu ra: In ra số ô còn lại nhỏ nhất có thể sau khi thực hiện hai loại thao tác trên.

Ví dụ:

 CODE:

Bitcoin là một loại tiền mã hóa, được phát minh bởi Satoshi Nakamoto dưới dạng phần mềm mã nguồn mở từ năm 2009. Bitcoin có thể được trao đổi trực tiếp bằng thiết bị kết nối Internet mà không cần thông qua một tổ chức tài chính trung gian nào.

            Sắn tìm hiểu và rất thích BITCOIN, cậu dự đoán giá của Bitcoin trong N ngày tiếp theo là d₁, d₂, …, d_n (đơn vị USD). Cậu ta nhờ bố giúp đỡ để có thể thu lời từ việc mua bán Bitcoin. Bố cậu ta có thể cho cậu ta mượn 1 đồng Bitcoin với hai điều kiện:

            - Một là phải trả phí: Mượn một ngày trả phí K đô la. Khi trả lại phải đúng 1 Bitcoin và tiền lời.

            - Hai là cho mượn bất cứ ngày nào nhưng chỉ được bán đi và mua lại một lần duy nhất để kiếm lời.

            Sắn đã có kế hoạch cho riêng mình để thu lời. Cậu ấy có thể bán ra đồng Bitcoin vào một ngày bất kỳ nào đó nếu muốn và mua lại vào một ngày nào đó sau ngày bán hoặc là không mua bán lần nào nếu không thu được tiền lời. Đố bạn Sắn sẽ thu được nhiều nhất bao nhiêu tiền nếu có kế hoặc bán tối ưu.

Dữ liệu nhập:

   - Dòng 1 là hai số nguyên N và K (1 ≤ N ≤ 2*10⁵; 0 ≤ K ≤ 10⁵)

   - Dòng 2 là giá Bitcoin trong n ngày tiếp theo d₁, d₂, …, d_n. (0 ≤ d_i ≤ 10⁸)

Kết quả: In ra một số nguyên duy nhất là số tiền lời tối đa mà Sắn thu được.

Ví dụ:

Trong ví dụ trên:

            - Sắn bán ra ở ngày 1 thu được 10 USD

            - Sắn mua lại Bitcoin ở ngày thứ 3 mất 5 USD

            - Tiền lời thu được: 10 – 5 – 2 = 3 USD (2 USD là tiền lãi phải trả cho bố sau 2 ngày mượn).

CODE: 

Tèo và Tí chơi thân với nhau, biết Tí học giỏi môn Toán nên một hôm Tèo đố Tí bài toán: Cho n số nguyên dương a₁, a₂, …, a_n. Hãy ghép các số đó lại với nhau để được số nguyên dương lớn nhất.

            Ví dụ: Với 3 số 12, 907, 91 ta có 6 cách ghép được 6 số là: 1290791, 1291907, 9071291, 9079112, 9112907, 9190712.

            Trong đó số lớn nhất là 9190712.

            Tất nhiên là bài toán này không thể làm khó Tí được nhưng vì còn bận học bài nên Tí muốn nhờ các bạn viết chương trình giải quyết bài toán trên.

Dữ liệu vào:

            - Dòng đầu chứa số nguyên dương n;       

            - Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n. Hai số liên tiếp cách nhau một dấu cách.

            Giới hạn:

·        1 ≤ n ≤ 100; 1 ≤ a_i ≤ 10⁵.

·        Có 50% số test có n  ≤ 10.

Dữ liệu ra: Ghi ra số nguyên dương lớn nhất ghép được.

Ví dụ:

 CODE:

Cho hai dãy số nguyên a₁, a₂, …, a_n và b₁, b₂, …, b_m. Với mỗi chỉ số i (1 ≤ i ≤ m) hãy tìm sự xuất hiện của b_i trong dãy a₁, a₂, …, a_n.

Dữ liệu vào:

            - Dòng đầu ghi hai số nguyên dương n và m;

            - Dòng thứ hai ghi n số nguyên a₁, a₂, …, a_n;

            - Dòng thứ ba ghi m số nguyên b₁, b₂, …, b_m.

Dữ liệu ra:

            - Một dòng duy nhất chứa m số nguyên, trong đó số thứ i (1 ≤ i ≤ m) là chỉ số j nhỏ nhất mà a_j = b_i (nếu tồn tại) và là 0 nếu ngược lại. Hai số liên tiếp được ghi cách nhau một dấu cách.

Ví dụ:

Cho dãy số A gồm n phần tử nguyên dương A₁, A₂, …, A_n. Mỗi phần tử có giá trị không vượt quá 10⁹ và 1 < n ≤ 5000. Một bộ ba số được gọi là bộ số tam giác, nếu ba số này tạo thành ba cạnh của một tam giác nào đó.

            Yêu cầu: Hãy đếm xem trong dãy A có bao nhiêu bộ số tam giác (A_i, A_j, A_k) với i, j, k đôi một khác nhau.

            Dữ liệu vào:

                        - Dòng đầu là số n;

                        - Dòng tiếp theo là các phần tử của dãy A, mỗi phần tử cách nhau một dấu cách.

            Dữ liệu ra: Ghi ra số lượng bộ số tam giác.

Ví dụ:

            Giải thích ví dụ: Ba bộ số tam giác gồm: (4, 3, 5); (4, 5, 7); (3, 5, 7).

            Ràng buộc:

                        - Có 30% số test ứng với 30% số điểm của bài có n ≤ 100.

                        - Có 30% số test ứng với 30% số điểm của bài có 100 < n ≤ 1000.

                        - Có 40% số test ứng với 40% số điểm của bài có 1000 < n ≤ 5000.

CODE:

Cho dãy n số nguyên không âm a₁, a₂, …, a_n. Người ta tiến hành chọn ra 2 chỉ số i, j sao cho i < j và xóa khỏi dãy 2 số a_i, a_j để tổng giá trị các số còn lại trong dãy là số chẵn.

            Yêu cầu: Cho dãy số a₁, a₂, …, a_n. Hãy đếm số lượng cách chọn 2 chỉ số i, j thỏa mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau.

            Dữ liệu nhập: gồm 2 dòng

            - Dòng 1: chứa số nguyên n (2 ≤ n ≤ 10⁶)

            - Dòng 2: chứa n số nguyên không âm a₁, a₂, …, a_n (0 ≤ a_i ≤ 10⁹)

Dữ liệu xuất:

            - Là một số nguyên cho biết số cách chọn 2 chỉ số i, j thỏa mãn.

Ví dụ:

ĐỀ 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ụ: