Bài tập Queue(CTDL_GT)
Bài tập Queue(CTDL>)
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) = 32 + 22
+ 12 + 12 = 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.
Code tham khảo
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
|
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.
Code tham khảo
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
|
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<263). 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.
Code tham khảo
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
|
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.
Code tham khảo
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
|
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<263) 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
|
BÀI TẬP CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT(C++)
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/
Nhận xét