Dinh Can's Blog

Nam có n viên gạch được đánh số từ 1 đến n. Các viên gạch có độ cứng lần lượt là a₁, a₂,..., a_n. Một viên gạch có độ cứng x nghĩa là Nam có thể chồng lên trên viên gạch đó tối đa x viên gạch khác, nếu chồng nhiều hơn thì viên gạch đó bị vỡ. Hỏi Nam có thể sắp được chồng gạch cao nhất là bao nhiêu?

Dữ liệu nhập:

- Dòng đầu tiên là số nguyên n (1 ≤ n ≤ 100) - là số viên gạch.

- Dòng tiếp theo gồm n số nguyên a₁, a₂,..., a_n (0 ≤ a_i ≤ 100) mỗi số cách nhau một khoảng trắng.

Dữ liệu xuất

- Là số nguyên xác định chiều cao cao nhất của chồng gạch mà Nam sắp được.

Ví dụ

Trong một cuốn sách cổ có ghi lại rất nhiều các con số bí ẩn mà chúng có mối liên hệ với 30. Sau một thời gian nghiên cứu các chuyên gia đã tìm được cách giải mã các số đó: hoán vị các chữ số của số bí ẩn đó để thu được một số là bội số lớn nhất của 30.

            Yêu cầu: Hãy viết chương trình giúp các chuyên gia giải mã các con số bí ẩn đó.

Dữ liệu nhập:

  - Gồm một số nguyên dương N duy nhất;

Kết quả:

  - in ra một số duy nhất là kết quả tìm được. Nếu không giải mã được hãy in -1.

Ràng buộc:

  - 50% test: 1 ≤ N ≤ 10⁹

  - 50% test: N có tối đa 10⁷ chữ số

Ví dụ:

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

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

Cho một dãy số nguyên A gồm n số nguyên a₁, a₂, …, a_N.

            Hãy tìm tích lớn nhất của ba số trong dãy A.

            Dữ liệu vào từ tệp văn bản T3S.INP có cấu trúc:

            - Dòng đầu ghi số nguyên dương N (3 ≤ N ≤ 10⁵).

            - Dòng thứ hai gồm N số nguyên a₁, a₂, …, a_N. (|a_i| ≤ 10⁵), i = 1, 2, …, N), các số được ghi cách nhau một dấu cách trống.

            Dữ liệu ra ghi vào tệp văn bản T3S.OUT chỉ ghi duy nhất một số là tích tìm được.

            Ví dụ:

            Ràng buộc:

            - Có 50% số test ứng với 50% số điểm của bài có N ≤ 10³ và |a_i| ≤ 10³, (i = 1, 2, …, N)

            - Có 50% số test còn lại ứng với 50% số điểm của bài tương ứng với các trường hợp còn lại.