Python: Bài tập phần thuật toán

Bài tập 1 (Bình Thuận 2022 - Bài 3):

Một cái thùng không có nắp có dạng hình hộp chữ nhật, có chiều dài 1.5m và chiều cao 1.2m, chiều rộng bằng 2/3 chiều dài. Người ta sơn cả trong và ngoài thùng, biết rằng cứ 0.8kg sơn thì sơn đươc 2m². Tính lượng sơn để sơn toàn bộ thùng.

Bài tập 2 (Hà Nội 2022 - Bài 1):

Nhập vào 3 số tự nhiên A, B, C. Đưa ra tổng của giá trị lớn nhất và giá trị nhỏ nhất của 3 số đó.

Dữ liệu: Nhập vào 3 số A, B, C (1 <= A, B, C <= 100)

Kết quả: Trả về một số duy nhất là tổng của số lớn nhất và số nhỏ nhất.

Ví dụ:

Bài tập 3 (Đồng Nai 2022 - Câu 3):

Cho tam giác số như sau:

1
2 3
4 5 6
7 8 9 10
...

Hãy mời người dùng nhập vào một số tự nhiên N, sau đó ta lập trình để đưa ra số đầu tiên ở hàng thứ N của tam giác là bao nhiêu?

Bài tập 4:

Cho tam giác Pascal như sau:

      1
    1 2 1
   1 3 3 1
  1 4 6 4 1
1 5 10 10 5 1
...

Hãy mời người dùng nhập vào hai số tự nhiên N và M, sau đó lập trình để đưa ra số ở vị trí M hàng thứ N của tam giác Pascal là bao nhiêu?

Bài tập 5 (Đồng Nai 2022 - Câu 2): Đổi thời gian

Hãy mời người dùng nhập vào một số tự nhiên N là số giây (seconds), sau đó hãy đổi ra giờ, phút, giây tương ứng và hiển thị theo dạng: hh : mm : ss

Ví dụ, nếu người dùng nhập vào N = 4000 thì sẽ hiển thị: 01 : 06 : 40

Bài tập 6:

Viết chương trình tìm ước số chung lớn nhất (USCLN) và bội số chung nhỏ nhất (BSCNN) của hai số nguyên dương a và b nhập từ bàn phím.

Bài tập 7:

Viết chương trình nhập vào một số N bất kỳ vàn kiểm tra xem N có phải số nguyên tố hay không. Trong trường hợp N là số nguyên tố thì hãy tìm và hiển thị số nguyên tố tiếp theo sau N.

Bài tập 8:

Viết chương trình nhập vào số nguyên dương N và sau đó phân tích số nguyên N thành các thừa số nguyên tố trong. Ví dụ: 100 = 2 x 2 x 5 x 5.

Bài tập 9 (Đà Nẵng 2022 - Bài 1): Mắc bóng đèn

Người ta mắc bóng đèn xung quanh một bảng quảng cáo hình vuông có chiều dài a dm, hai bóng đèn liên tiếp cách nhau 5 cm. Hãy mời người dùng nhập vào một số nguyên dương a, sau đó tính và hiển thị số lượng bóng đèn cần mắc.

Bài tập 10 (Đà Nẵng 2022 - Bài 3): Không thích số 3

Polycarp không thích những số chia hết cho 3 và những số có chữ số hàng đơn vị là 3. Polycarp bắt đầu viết các số nguyên dương mà bạn ý thích: 1, 2, 4, 5, 7, 8, 10, 11, 14, 16, ...

Em hãy mời người dùng nhập vào một số nguyên dương N, sau đó hiển thị ra số thứ N trong dãy số của Polycarp là bao nhiêu?

Bài tập 11 (Đà Nẵng 2022 - Bài 4): Số cân bằng

Số cân bằng là số:

• Có số lượng các chữ số là chẵn.
• Nửa nhóm ký tự bên trái giống nửa nhóm ký tự bên phải.

Ví dụ, số 6767, 123123, ... là những số cân bằng.

Em hãy mời người dùng nhập vào một số nguyên dương N và hiển thị tất cả các số cân bằng <= N.

Bài tập 12:

Tổng số các chữ số của một số tự nhiên là tổng của từng chữ số. Ví dụ số 1234 có tổng của các chữ số là: 1 + 2 + 3 + 4 = 10

Em hãy lập trình đếm các số tự nhiên có 4 chữ số mà có tổng các chữ số bằng 10.

Bài tập 13:

Cho hai số tự nhiên A và B. Gọi C là tích của A và B. Hãy mời người dùng nhập vào hai số tự nhiên A và B, sau đó tính tổng của các chữ số của C. Ví dụ, A = 3 và B = 5, thì C = 15, tức tổng các chữ số của C sẽ là 1 + 5 = 6.

Bài tập 14:

Cho dãy số theo quy luật như sau: 3, 4, 6, 7, 9, 10, 12, ... Hãy mời người dùng nhập vào hai số nguyên dương A và B, sau đó hãy tính tổng của các phần tử của dãy mà lớn hơn A và nhỏ hơn B. Ví dụ, A = 1 và B = 8 thì sẽ tính tổng của dãy số 3, 4, 6, 7.

Bài tập 15:

Jack mua N cuốn sách và muốn chia đều cho M người bạn thân. Em hãy giúp Jack biết cần mua ít nhất bao nhiêu cuốn sách nữa để có thể chia đều các cuốn sách cho M người bạn?

Ví dụ, nếu Jack mua N = 30 cuốn sách và Jack có M = 8 người bạn thân, thì Jack cần mua thêm ít nhất 2 cuốn nữa.

Bài tập 16:

Phương viết dòng chữ V1STUDY lặp đi lặp lại nhiều lần thành dãy các ký tự liên tiếp nhau: V1STUDYV1STUDYV1STUDYV1STUDYV1STUDY...

Sau đó Phương tô màu cho từng chữ trong dãy trên theo trật tự: RED, GREEN, BLUE, YELLOW, RED, GREEN, BLUE, YELLOW, ...

Em hãy nhập vào một số nguyên dương k, sau đó in ra màn hình chữ cái và màu tương ứng thứ k là gì theo quy cách: Chữ - Màu

Ví dụ, nếu k = 5 thì sẽ in ra là: U - RED.

Bài tập 17:

Cho ba số nguyên dương 𝑎, 𝑏 và 𝑁. Hãy tính tổng 𝑁 chữ số sau dấu chấm thập phân của phép chia 𝑎 cho 𝑏. Có thể thêm vô hạn số 0 vào cuối phần thập phân.

Ví dụ:

  + Nếu nhập vào 20, 13 và 5 thì kết quả là 4. Giải thích: 20 / 13 = 1.5384615, vậy tổng 5 chữ số sau dấu chấm là: 5 + 3 + 8 + 4 + 6 = 26.

  + Nếu nhập vào 25, 3 và 4 thì kết quả là 12. Giải thích: 25 / 3 = 8.333333, vậy tổng 4 chữ số sau dấu chấm là: 3 + 3 + 3 + 3 = 12

  + Nếu nhập vào 4, 2 và 6 thì kết quả là 0. Giải thích: 4 / 2 = 2.00000000, vậy tổng 6 chữ số sau dấu chấm là: 0.

Bài tập 18:

Cho hai số nguyên dương 𝑁 và 𝐾. Ta có 𝑋10 của một số là nhân số đó với 10, ví dụ số 𝑋10 của 24 là 240; 𝑋10 tiếp được số 2400… Số 𝑆 là tổng của số 𝑁 và 𝐾 số 𝑋10 liên tiếp của N. Hãy in ra tổng các chữ số của 𝑆.

Ví dụ: 𝑁 = 123, 𝐾 = 3 thì ta có 𝑆 = 123 + 1230 + 12300 + 123000 = 136653. Vậy tổng các chữ số của số S là: 1 + 3 + 6 + 6 + 5 + 3 = 24.

Bài tập 19:

Cho 𝑁 điểm phân biệt trên hệ trục toạ độ Oxy. Hãy đếm xem có bao nhiêu hình chữ nhật có các cạnh song song với các trục toạ độ mà bốn đỉnh là bốn điểm trong 𝑁 điểm đã cho. Dữ liệu: nhập vào từ file HCN.INP - Dòng đầu tiên gồm một số nguyên dương 𝑁 là số lượng các điểm. - 𝑁 dòng sau, mỗi dòng gồm hai số nguyên 𝑥, 𝑦 là toạ độ của một điểm.

Ví dụ:

Bài tập 20:

Cho số 𝑁, 𝑋 và một dãy số có 𝑁 phần tử. Hãy chọn ra ít phần tử nhất trong 𝑁 phần tử đó để tích của chúng chia hết cho 10^𝑋. In ra số lượng phần tử ít nhất đã chọn.

Ví dụ: Với N = 5, X = 4 và dãy số 5 phần tử là 10, 8, 100, 25, 6, thì kết quả là 3, tức là chọn được 3 số để tích chia hết cho 10⁴ là 8 x 25 x 100 = 20000.

Bài tập 21: Dãy bậc K

Mít mới học ba định nghĩa mới liên quan đến dãy số như sau:

  • Một dãy số được gọi là dãy đầy đủ bậc K khi dãy số có đúng K phần tử và gồm đủ các phần tử từ 1 đến K. Ví dụ dãy số (2, 3, 1) là dãy số đầy đủ bậc 3.

  • Dãy số B được gọi là dãy con của dãy số A khi dãy số B được tạo ra bằng cách xóa bỏ một số phần tử của của dãy số A (giữ nguyên thứ tự trước sau và có thể không xóa bỏ phần tử nào). Ví dụ dãy số A là (4, 2, 1, 2, 5, 6), một số dãy số con của dãy số A là (4, 1, 6); (2, 2, 5, 6); (4, 2, 1, 2, 5, 6); …

  • Dãy số A được gọi là có thứ tự từ điển nhỏ hơn dãy số B khi tồn tại vị trí i mà:

    - Với mọi vị trí j (j < i) thì a_j = b_j

    - a_i < b_i.

Sau khi học xong lý thuyết, thầy giáo đã giao cho Mít một bài tập rất khó: cho một số K và dãy số A có N số nguyên dương không lớn hơn K. Hãy tìm dãy con của dãy số A có thứ tự từ điển nhỏ nhất và là một dãy đầy đủ bậc K.

Yêu cầu: Hãy lập trình giúp Mít tìm dãy con thỏa mãn yêu cầu của thầy giáo.

Ví dụ: Nếu nhập vào N = 4, K = 3 và các phần tử của dãy là 3, 2, 1, 2 thì kết quả sẽ là: 3, 1, 2.

Bài tập 22: San bằng

Bản đồ mặt bằng của một công trình xây dựng là một hình chữ nhật kích thước m × n được chia thành lưới ô vuông đơn vị (m, n ≤ 10⁶), các hàng ô của lưới được đánh số từ 1 tới m từ trên xuống dưới và các cột ô của lưới được đánh số từ 1 tới n từ trái qua phải. Ô nằm trên giao của hàng x và cột y được gọi là ô (x, y). Mùa mưa đến, người ta muốn tôn cao mặt bằng của công trình để tránh ngập úng bằng cách dùng k (k ≤ 10⁶) chuyến xe ben chở đất đá bên ngoài đổ vào mặt bằng công trình. Chuyến xe thứ i đổ vào ô (x_i, y_i) đúng a_i tấn đất đá (a_i là số nguyên và 1 ≤ i ≤ k). Tổng khối lượng đất đá được các chuyến xe ben đổ vào công trình là số nguyên không vượt quá 10¹² và chia hết cho m × n. Tiếp theo, máy ủi được điều tới để san đều toàn bộ khối lượng đất đá này vào các ô. Chi phí để máy ủi chuyển mỗi tấn đất đá từ một ô sang một ô khác kề cạnh là 1 (chú ý là không được chuyển đất đá ra khỏi mặt bằng công trình). Yêu cầu: Tìm cách điều khiển các máy ủi để san đều toàn bộ khối lượng đất đá vào các ô với chi phí ít nhất. Cho biết chi phí đó.

Dữ liệu nhập vào theo dạng như sau:

  - Đầu tiên nhập m, n và k.

  - k dòng tiếp theo mỗi dòng i nhập ba giá trị x_i, y_i và a_i.

Ví dụ, nếu nhập vào dữ liệu như sau:

3 4 4
1 1 4
1 1 5
3 1 3
3 2 6

Thì kết quả sẽ là: 18

Giải thích:

Bài tập 23: Bội chính phương

Cho một dãy số A có N phần tử. Tìm số nguyên dương P nhỏ nhất thoả mãn: P là số chính phương và P chia hết cho tất cả các phần tử của dãy số A.

Ví dụ: Nếu nhập vào N = 3 và nhập vào 3 phần tử của dãy A là 2, 1, 3, thì kết quả P = 36.

Bài tập 24: Xâu tương đồng

Cho 2 xâu 𝐴 và 𝐵 chỉ chứa các kí tự in hoa trong khoảng từ A tới Z. Kí hiệu |𝐴|, |𝐵| lần lượt là độ dài của hai xâu 𝐴 và 𝐵, (1 ≤ |𝐴|, |𝐵| ≤ 50000). Các kí tự của mỗi xâu được đánh số từ 1.

Gọi 𝐴[𝑖 … 𝑗] là xâu con gồm các kí tự liên tiếp của xâu 𝐴 từ vị trí thứ 𝑖 đến vị trí thứ 𝑗 (1 ≤ 𝑖 ≤ 𝑗 ≤ |𝐴|). Gọi 𝐵[𝑝 … 𝑞] là xâu con gồm các kí tự liên tiếp của xâu 𝐵 từ vị trí thứ 𝑝 đến vị trí thứ 𝑞 (1 ≤ 𝑝 ≤ 𝑞 ≤ |𝐵|).

Hai xâu con 𝐴[𝑖 … 𝑗] và 𝐵[𝑝 … 𝑞] được gọi là tương đồng nhau nếu tập hợp các chữ cái xuất hiện trong xâu con 𝐴[𝑖 … 𝑗] bằng với tập hợp các chữ cái xuất hiện trong xâu con 𝐵[𝑝 … 𝑞].

Xét ví dụ 𝐴 = "AAABBC" và 𝐵 = "AZACAB" ta có:

𝐴[3 … 5] = "ABB" và 𝐵[5 … 6] = "AB" là tương đồng nhau vì cùng có tập hợp các chữ cái xuất hiện là { ′A′, ′B′}

𝐴[3 … 6] = "ABBC" và 𝐵[4. .6] = "CAB" là tương đồng nhau vì cùng có tập hợp các chữ cái xuất hiện là {′A′, ′B′, ′C′}.

Yêu cầu: cho xâu 𝐴 và xâu 𝐵, hãy xác định số bộ (𝑖,𝑗, 𝑝, 𝑞) (1 ≤ 𝑖 ≤ 𝑗 ≤ |𝐴|; 1 ≤ 𝑝 ≤ 𝑞 ≤ |𝐵|) thỏa mãn 𝐴[𝑖 … 𝑗] tương đồng với 𝐵[𝑝 … 𝑞].

Dữ liệu: Vào từ thiết bị nhập chuẩn:

Dòng thứ nhất ghi xâu A.

Dòng thứ hai ghi xâu B.

Kết quả: Ghi ra thiết bị xuất chuẩn một số nguyên duy nhất là số lượng bộ (𝑖,𝑗, 𝑝, 𝑞) thỏa mãn yêu cầu.

Ví dụ:

Bài tập 25: Bốc bi

Hộp bi của Bờm có dạng hình chữ nhật kích thước 𝑚 × 𝑛 được chia thành lưới ô vuông đơn vị (𝑚, 𝑛 ≤ 10⁶). Các hàng ô của lưới được đánh số từ 1 tới 𝑚 từ trên xuống dưới và các cột ô của lưới được đánh số từ 1 tới 𝑛 từ trái qua phải. Ô nằm trên giao của hàng 𝑥 và cột 𝑦 được gọi là ô (𝑥, 𝑦). Ban đầu hộp bi chưa có viên bi nào.

Đầu tiên, Bờm thực hiện 𝑘 lần bốc bi vào hộp (𝑘 ≤ 10⁶), ở lần thứ 𝑖, Bờm bốc 𝑎𝑖 viên bi cho thêm vào ô (𝑥𝑖 , 𝑦𝑖 ), tổng số bi Bờm bốc vào hộp không vượt quá 10¹².

Bờm nhận thấy rằng nếu để các viên bi phân bố không đều trong các ô, sẽ có ô chứa quá nhiều viên bi gây khó khăn cho việc đóng hộp. Bờm bèn chế tạo một robot để di chuyển bi giữa các ô sao cho tất cả các ô trong hộp đều chứa số bi giống nhau. Robot của Bờm trong một giây có thể chuyển được đúng một viên bi từ một ô sang một ô khác chung đỉnh với ô đó (chú ý là không được chuyển bi ra khỏi hộp).

Yêu cầu: Tìm cách điều khiển robot để chia đều số bi trong hộp ra các ô trong thời gian ít nhất. Cho biết thời gian robot hoàn thành công việc theo phương án tìm được.

Dữ liệu: Vào từ thiết bị nhập chuẩn:

  - Dòng 1 chứa ba số nguyên dương 𝑚, 𝑛, 𝑘

  - 𝑘 dòng tiếp theo, dòng thứ 𝑖 chứa ba số nguyên dương 𝑥𝑖 , 𝑦𝑖 , 𝑎𝑖.

Kết quả: Ghi ra thiết bị xuất chuẩn một số nguyên duy nhất là thời gian robot hoàn thành công việc theo phương án tìm được. Trong trường hợp robot không thể chia đều số bi trong hộp ra các ô, in ra số -1.

Ví dụ:

Bài tập 26: Tàu cao tốc

Một đất nước có 𝑛 thành phố, các thành phố được đánh số từ 1 tới 𝑛. Có 𝑚 tuyến tàu cao tốc, mỗi tuyến kết nối trực tiếp hai thành phố khác nhau theo cả hai chiều, đảm bảo từ một thành phố bất kỳ có thể đi đến một thành phố bất kỳ khác thông qua (trực tiếp hoặc gián tiếp) 𝑚 tuyến tàu cao tốc đó.

Vì kinh phí bảo trì hàng năm cho hệ thống tàu cao tốc là rất lớn, tiêu tốn một lượng lớn ngân sách của nhà nước, Bộ giao thông và Vận tải dự định sẽ loại bỏ đúng hai tuyến tàu cao tốc trong số 𝑚 tuyến (việc loại bỏ nhiều hơn hai tuyến sẽ khiến người dân phàn nàn). Hai thành phố 1 và 2 là hai thành phố trọng yếu của đất nước nên việc loại bỏ các tuyến tàu phải thỏa mãn điều kiện: từ thành phố 1 vẫn có thể đi đến được thành phố 2 thông qua các tuyến tàu không bị loại bỏ.

Yêu cầu: Bạn hãy giúp Bộ giao thông và Vận tải đếm xem có nhiêu cách loại bỏ đúng hai tuyến tàu thỏa mãn yêu cầu. Hai cách được gọi là khác nhau nếu có một tuyến tàu bị loại bỏ trong cách này nhưng không bị loại bỏ trong cách kia.

Dữ liệu: Vào từ thiết bị vào chuẩn theo khuôn dạng sau:

  • Dòng đầu tiên chứa hai số nguyên dương 𝑛 và 𝑚 (2 ≤ 𝑛 ≤ 10⁵, 𝑚 ≤ 2 × 10⁵) lần lượt là số lượng thành phố và số lượng tuyến tàu cao tốc;

  • 𝑚 dòng sau, mỗi dòng chứa hai số nguyên 𝑢 và 𝑣 (𝑢 ≤ 𝑛, 𝑣 ≤ 𝑛, 𝑢 ≠ 𝑣) cho biết có một tuyến tàu cao tốc hai chiều kết nối trực tiếp thành phố 𝑢 và thành phố 𝑣. Các số trên cùng một dòng được cách nhau bởi dấu cách.

Kết quả: Ghi ra thiết bị ra chuẩn gồm một số nguyên duy nhất là số cách loại bỏ đúng hai tuyến tàu cao tốc sao cho từ thành phố 1 vẫn đi đến được thành phố 2 thông quá các tuyến tàu cao tốc không bị loại bỏ.

Ví dụ:

Bài tập 27: Phần thưởng

An là người thắng cuộc trong cuộc thi "Tìm hiểu Đoàn Thanh niên Cộng sản Hồ Chí Minh" và được nhận phần thưởng của Ban tổ chức. Ban tổ chức chuẩn bị một bảng kích thước m x n. Các dòng của bảng được đánh số từ 1 đến m, từ trên xuống dưới, dòng i (1 <= i <= m) có trọng số là a_i. Các cột của bảng được đánh số từ 1 đến n, từ trái qua phải, cột j (1 <= j <= n) có trọng số là b_j. Ô nằm trên giao của dòng và cột được gọi là ô (i,j) và trên ô đó ghi một số nguyên có giá trị a_i + b_j (1 <= i <= m; 1 <= j <= n).

Để nhận phần thưởng, An được phép chọn một bảng con kích thước w x h chiếm trọn w x h ô của bảng và phần thưởng mà An nhận được sẽ có giá trị bằng tổng giá trị các ô nằm trong bảng con đó.

Yêu cầu: Hãy xác định tổng giá trị lớn nhất mà An có thể nhận được.

Dữ liệu:

  + Dòng thứ nhất chứa bốn số nguyên dương m, n, w, h (w <= m; h <= n);

  + Dòng thứ hai chứa m số nguyên a₁, a₂, ..., a_m (|a_i| <= 10⁶, i = 1, 2, ..., m);

  + Dòng thứ hai chứa n số nguyên b₁, b₂, ..., b_m (|b_j| <= 10⁶, j = 1, 2, ..., n);​

Kết quả: Hiển thị một số nguyên duy nhất là tổng giá trị lớn nhất mà An có thể nhận được.

Bài tập 28:

Give a positive integer n (2 <= n <= 10⁶) and the sequence of integers a₀, a₁, ..., a_n-1. A way of choosing a set of 2 indices i, j (0 <= i < j <= n-1) is said to be optimal if D = a_j - a_i reaches the maximum value. For example, given a sequence of integers {4, 2, 5, 8, 1, 7} then D to be found is 6 with i = 1 and j = 3.

Input format:

a sequence of n+1 integers n, a₀, a₁, ..., a_n-1.

Constraints

n > 1, | a_i | <= 10⁶

Output format

A number representing the value D of the optimal choice.

Sample input:

6
4
2
5
8
1
7

Sample output:

6

Bài tập 29:

A string of characters is said to be a "secure" password if its length is at least 6 and contains at least one uppercase letter ('A' -> 'Z), at least one lowercase letter ('a' -> 'z'), and at least a digit ('0' -> '9'). Given a string of characters, determine whether the string is a "secure" password or not.

Input format

A string S

Constraints

S is not empty and its length is no more than 100

Output format

A number 1 or 0, where represents secure password, 0 pressents NOT secure password.

Sample input

a1B2C3

Sample output

1

Explaination

Secure password, includes lowercase (a), uppercase (B), and digit (1)

Bài tập 30:

Bài tập 31: Biến đổi xâu

Cho xâu kí tự S, bạn được thực hiện phép biến đổi sau: Chọn hai chỉ số i và j sao cho i>j, thay kí tự ở vị trí thứ i thành kí tự ở vị trí thứ j. Ví dụ, giả sử xâu S là hanh, thì bằng cách chọn i=3 và j=2 ta có thể biến đổi xâu thành haah. Tuy nhiên, bạn không thể biến đổi từ xâu hanh thành hnnh. Cho hai xâu kí tự S và T, bạn được thực hiện phép biến đổi trên không giới hạn số lần. Bạn chỉ cần trả lời có thể biến đổi từ S thành T hay không. Input Gồm hai dòng, dòng đầu chứa xâu S và dòng thứ hai chứa xâu T. Hai xâu S và T có cùng độ dài, mỗi xâu chứa từ 1 đến 1000 ký tự và chỉ gồm các chữ cái thường. Output In ra Yes nếu không thể đổi xâu S sang xâu T, hoặc No nếu ngược lại.

Đáp án tham khảo: