Bài tập Queue(CTDL_GT)

Bài tập Queue(CTDL&GT)

Bài 1.Minimum String Value (Amazon). Cho xâu ký tự S[] bao gồm các ký tự in hoa [A, B, …,Z]. Ta định nghĩa giá trị của xâu S[] là tổng bình phương số lần xuất hiện mỗi ký tự trong xâu. Ví dụ với xâu S[] = “AAABBCD” ta có F(S) = 3² + 2²+ 1² + 1² = 15. Hãy tìm giá trị nhỏ nhất của xâu S[] sau khi loại bỏ K ký tự trong xâu.

Input:

·       Dòng đầu tiên đưa vào số lượng test T (T≤100).

·       Mỗi test được tổ chức thành 2 dòng. Dòng thứ nhất ghi lại số K. Dòng thứ 2 ghi lại xâu ký tự S[].

Output:

·       Đưa ra giá trị nhỏ nhất của mỗi test theo từng dòng.

Input	Output
2 2 ABCC 1 ABCC	6 3

Code tham khảo

Bài 2.Cho số tự nhiên N. Hãy tìm số nguyên dương X nhỏ nhất được tạo bởi số 9 và số 0 chia hết cho N. Ví dụ với N = 5 ta sẽ tìm ra  X = 90.

Input:

·       Dòng đầu tiên ghi lại số lượng test T (T≤100).

·       Những dòng kế tiếp mỗi dòng ghi lại một test. Mỗi test là một số tự nhiên N được ghi trên một dòng (N≤100).

Output:

·       Đưa ra theo từng dòng số X nhỏ nhất chia hết cho N tìm được .

Input	Output
2 5 7	90 9009

Code tham khảo

Bài 3.Binary Digit Numbers (BDN). Ta gọi số nguyên dương K là một số BDN nếu các chữ số trong K chỉ bao gồm các 0 hoặc 1 có nghĩa. Ví dụ số K = 1, 10, 101. Cho số tự nhiên N (N<2⁶³). Hãy cho biết có bao nhiêu số BDN nhỏ hơn N. Ví dụ N=100 ta có 4 số BDN bao gồm các số: 1,       10, 11, 100.

Input:

·       Dòng đầu tiên ghi lại số tự nhiên T là số lượng Test;

·       T dòng kế tiếp mỗi dòng ghi lại một bộ Test. Mỗi test là một số tự nhiên N.

         Output:

·      Đưa ra kết quả mỗi test theo từng dòng.

Input	Output
3 10 100 200	2 4 7

Code tham khảo

Bài 4.Số BDN của N. Ta gọi số nguyên dương K là một số BDN nếu các chữ số trong K chỉ bao gồm các 0 hoặc 1 có nghĩa. Ví dụ số K =  101 là số BDN, k=102 không phải là số BDN. Số BDN của N là số P =M´N sao cho P là số BDN. Cho số tự nhiên N (N<1000), hãy tìm số BDN nhỏ nhất của N.

Ví dụ. Với N=2, ta tìm được số BDN của N là P = 5´2=10. N = 17 ta tìm được số BDN của 17 là P = 653´17=11101.

Dữ liệu vào cho bởi file data.in theo khuôn dạng:

·       Dòng đầu tiên ghi lại số tự nhiên T là số lượng Test;

·       T dòng kế tiếp mỗi dòng ghi lại một bộ Test. Mỗi test là một số tự nhiên N.

         Kết quả thực hiện của mỗi test được ghi lại trong file ketqua.out theo từng dòng. Mỗi dòng ghi lại số các số BDN của mỗi test. Ví dụ dưới đây sẽ minh họa cho file data.in và ketqua.out của bài toán.

Input	Output
3 2 12 17	10 11100 11101

Code tham khảo

Bài 5. Minimum Operation. Cho hai số nguyên dương S và T (S, T<10000) và hai thao tác (a), (b) dưới đây:

Thao tác (a): Trừ S đi 1  (S = S-1) ;

Thao tác (b): Nhân S với 2 ( S = S*2);

Hãy dịch chuyển S thành T sao cho số lần thực hiện các thao tác (a), (b) là ít nhất. Ví dụ với    S =2, T=5 thì số các bước ít nhất để dịch chuyển S thành T thông qua 4 thao tác sau:

Thao tác (a): 2*2 = 4;

Thao tác (b): 4-1 = 3;

Thao tác (a): 3*2 = 6;

Thao tác (b): 6-1 = 5;

Input:

·       Dòng đầu tiên ghi lại số tự nhiên T là số lượng Test;

·       T dòng kế tiếp mỗi dòng ghi lại một bộ Test. Mỗi test là một bộ đôi S và T.

      Output: Đưa ra kết quả mỗi test theo từng dòng.

Input	Output
3 2 5 3 7 7 4	4 4 3

Code tham khảo

Bài 6. Minimum Step to reach 1. Cho số tự nhiên N (N<2⁶³) và hai phép biến đổi (a), (b) dưới đây.

Thao tác (a): Trừ N đi 1 (N=N-1). Ví dụ N=17, thao tác (a) biến đổi N = N-1 =16.

Thao tác (b): N = max(u,v) nếu u*v =N (u>1, v>1). Ví dụ N=16, thao tác (b) có thể biến đổi N = max(2, 8)=8 hoặc N=max(4, 4)=4.

      Chỉ được phép sử dụng hai thao tác (a) hoặc (b), hãy biến đổi N thành 1 sao số các thao tác (a), (b) được thực hiện ít nhất. Ví dụ với N=17, số các phép (a), (b) nhỏ nhất biến đổi N thành 1 là 4 bước như sau:

                     Thao tác (a): N = N-1 = 17-1 = 16

                     Thao tác (b): 16 = max(4,4) = 4

                     Thao tác (b): 4 = max(2,2) = 2

                     Thao tác (a): 2 = 2-1 = 1

Input:

·       Dòng đầu tiên ghi lại số tự nhiên T là số lượng Test;

·       T dòng kế tiếp mỗi dòng ghi lại một bộ Test. Mỗi test là một số N.

      Output:

·         Đưa ra kết quả mỗi test theo từng dòng.

Input	Output
3 17 50 100	4 5 5

Code tham khảo

Bài 7. Cho cặp số S và T là các số nguyên tố có 4 chữ số (Ví dụ S = 1033, T = 8179 là các số nguyên tố có 4 chữ số). Hãy viết chương trình tìm cách dịch chuyển S thành T thỏa mãn đồng thời những điều kiện dưới đây:

a)     Mỗi phép dịch chuyển chỉ được phép thay đổi một chữ số của số ở bước trước đó (ví dụ nếu S=1033 thì phép dịch chuyển S thành 1733 là hợp lệ);

b)     Số nhận được cũng là một số nguyên tố có 4 chữ số (ví dụ nếu S=1033 thì phép dịch chuyển S thành 1833 là không hợp lệ, và S dịch chuyển thành 1733 là hợp lệ);

c)     Số các bước dịch chuyển là ít nhất.

Ví dụ số các phép dịch chuyển ít nhất để S = 1033 thành  T = 8179 là 6 bao goomg các phép dịch chuyển như sau:        8179<- 8779<- 3779<- 3739<- 3733<- 1733<-1033.

Input:

·              Dòng đầu tiên đưa vào số lượng test T (T≤100)

·              Những dòng kế tiếp mỗi dòng đưa vào một test. Mỗi test là một bộ đôi S, T.

Output:

·       Đưa ra kết quả mỗi test theo từng dòng.

Input	Output
2 1033 8179 1033 8779	6 5

Code tham khảo
BÀI TẬP CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT(C++)

Các bài tập CTDL&GT sẽ được mình cập nhật mỗi ngày tại link này nhé.(Mình không khẳng định code tham khảo tại mỗi bài đúng 100% rất mong sự góp ý sửa đổi của mọi người😅😅.Thanks).

Nếu thấy tài liệu có ích hi vọng các bạn ủng hộ trang web bằng cách like và theo dõi địa chỉ page chính thức của Tài Liệu Blog tại đây nhé: https://www.facebook.com/TaiLieuBlog/

💰Ủng hộ blog: https://unghotoi.com/1546792457ngwn4