Bài tập C++/Bài tập HSG

Bài 1. Bài toán cưa gỗ

Trong khu vườn trồng một hàng cây chạy dài gồm N cây, mỗi cây có độ cao là a₁, a₂,... a_N. Tổng cộng người ta cần lấy X mét gỗ bằng cách đặt máy sao cho lưỡi cưa ở độ cao H mét, cưa lấy các cây cao trên H mét, và những cây bằng hoặc thấp hơn thì không bị gì.

Yêu cầu: Tìm vị trí đặt lưỡi cưa hợp lí (số nguyên H) sao cho lấy được M mét và số mét gỗ dư ra là ít nhất.

Dữ liệu vào:

Dòng thứ nhất, nhập từ bàn phím hai số nguyên dương N và X, cách nhau một dấu cách.
Dòng thứ hai, nhập N số nguyên dương a_i là độ cao của mỗi cây trong hàng.

Dữ liệu ra: Xuất ra màn hình một số nguyên cho biết giá trị cần tìm.

Ví dụ minh họa: Cần lấy 7 mét gỗ từ một hàng 4 cây có độ cao tương ứng là 20; 15; 10 và 18 mét. Cần đặt lưỡi cưa ở độ cao hợp lí nhất để vừa lấy được 7 mét gỗ mà số gỗ dư ra cũng là ít nhất. Đặt ở độ cao 15 mét sẽ lấy được tổng cộng 8 mét gỗ, với dư 1 mét là dư ít nhất. Độ cao các cây còn lại sau khi bị cưa tương ứng là 15; 15; 10 và 15 mét.

Nhập	Xuất
4 7 20 15 10 18	15

Bài 2. Hàng cây thông

Trong lúc dạo chơi, An thấy hai bên đường là hai hàng thông đều tăm tắp, mỗi hàng có N cây thông. Trên mỗi cây người ta có đánh số là số tự nhiên có một chữ số. Vốn yêu thích các con số, An đã ghi lại những con số trên mỗi cây thông theo từng hàng. An nhận rằng nếu ghép các con số ghi trên mỗi cây thông ở mỗi hàng theo thứ tự từ đầu hàng đến cuối hàng thì sẽ nhận được một số tự nhiên, hai hàng là hai số tự nhiên. Lúc này, An muốn biếu tổng của hai số tự nhiên đó là bao nhiêu.

Yêu cầu: Viết chương trình tính tổng hai số tự nhiên mà An có được.

Dữ liệu vào:

Dòng thứ nhất, nhập vào số tự nhiên N thể hiện số cây thông ở mỗi hàng
Dòng thứ hai, nhập vào N số tự nhiên a_i là các số trên cây thông hàng thứ nhất theo thứ tự từ đầu đến cuối hàng
Dòng thứ hai, nhập vào N số tự nhiên b_i là các số trên cây thông hàng thứ hai theo thứ tự từ đầu đến cuối hàng
Các số nhập vào một dòng cách nhau bởi 1 khoảng trắng

Dữ liệu ra: Xuất ra màn hình kết quả tìm được.

Nhập	Xuất
5 1 2 3 2 5 4 1 1 0 2	53427

Bài 3. Trò chơi

Bạn đang tham gia một trò chơi như sau: có hai nút bấm 1 và 2. Trên nút 1 hiện số A, trên nút 2 hiện số B. Ở mỗi lượt chơi, bạn phải chọn bấm một trong hai nút và ghi được số điểm bằng con số hiện trên nút đó. Sau mỗi lần chơi, nút bạn vừa bấm sẽ giảm đi 1 đơn vị. Hỏi rằng sau N lượt chơi, tổng điểm lớn nhất bạn có thể đạt là bao nhiêu?

Dữ liệu vào:

Dòng thứ nhất, nhập vào hai số nguyên dương A, B tương ứng với số ghi trên nút 1 và 2, mỗi số cách nhau một khoảng trắng
Dòng thứ hai, nhập vào số nguyên dương N, là số lượt chơi

Dữ liệu ra: Xuất ra màn hình tổng điểm lớn nhất có thể nhận được sau hai lượt chơi.

Ví dụ minh họa: Ban đầu, nút 1 hiện số 5, nút 2 hiện số 3. Điểm thưởng lớn nhất có thể nhận được sau 2 lượt chơi là 9, bằng cách nhấn hai lần liên tiếp nút 1.

Nhập	Xuất
5 3 2	9

Bài 4. Giải mã văn bản Lời giải

Để đảm bảo tính bảo mật trong công tác truyền tin, Cục thông tin quốc gia quy định phải mã hóa bản tin gốc trước khi gửi đi bằng cách thêm các ký tự # vào các vị trí trong bản tin. Chính vì vậy, cô văn thư của công ty XYZ nhận được văn bản của cấp trên đọc không hiểu gì. Tiếp sau cô nhận được một bản hướng dẫn giải mã như sau: trong một chuỗi khi tính từ trái sang phải, nếu gặp ký tự # thì đó là dấu hiệu của yêu cầu xóa đi một ký tự đứng ngay trước vào chính nó, nếu kí tự # đứng đầu thì chỉ xóa mỗi kí tự #.

Yêu cầu: Viết chương trình giúp cô văn thư giải mã văn bản nhận được.

Dữ liệu vào: Nhập từ bàn phím chuỗi đã mã hóa trên một dòng

Dữ liệu ra: Xuất ra màn hình chuỗi đã được giải mã

Nhập	Xuất
Ch#o ch#ong mg#ae#i sj#ae#t con#g# #ngau#y nh#en kin#m	Co cong mai sat co ngay nen kim

Bài 5. In bảng số

Viết chương trình in lên màn hình bảng số có quy luật sau:

 1  3  5  7  9 11 13 15
 2  1  3  5  7  9 11 13
 4  2  1  3  5  7  9 11
 6  4  2  1  3  5  7  9
 8  6  4  2  1  3  5  7
10  8  6  4  2  1  3  5
12 10  8  6  4  2  1  3
14 12 10  8  6  4  2  1

Yêu cầu: Có sử dụng thuật toán.

Bài 6: Số siêu nguyên tố

Số siêu nguyên tố là số nguyên tố khi bỏ đi số tùy ý bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố. Ví dụ, 7331 là một số siêu nguyên tố, vì khi bỏ đi số tùy ý bên phải ta có thể nhận được các số 733, 73, 7 đều là các số nguyên tố.

Yêu cầu: Nhập vào số nguyên N, hãy viết chương trình đếm xem có bao nhiêu số siêu nguyên tố có N chữ số và liệt kê tất cả chúng.

Dữ liệu vào: Nhập vào số nguyên N

Dữ liệu ra:

Dòng thứ nhất, thông báo số lượng số siêu nguyên tố tìm được
Dòng thứ hai, in ra tất cả số đó

Nhập	Xuất
4	16 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393

Bài 7: Taxi

Trong dịp hè, các bạn học sinh dự định tổ chức đi chơi tại vịnh Hạ Long và sẽ đi bằng Taxi. Các bạn được chia thành N nhóm, nhóm thứ i gồm Si bạn, mỗi nhóm có từ 1 đến 4 người và mỗi chiếc xe taxi chở tối đa 4 hành khách. Với điều kiện là các bạn trong nhóm phải ngồi chung taxi (một taxi có thể chở nhiều hơn 1 nhóm nếu đủ chỗ) thì phải thuê ít nhất là bao nhiêu chiếc taxi?

Dữ liệu vào:

Dòng thứ nhất, nhập vào N là số lượng nhóm học sinh. (Giới hạn: 105 nhóm)
Dòng thứ hai, nhập lần lượt số học sinh của mỗi nhóm, mỗi số cách nhau bởi một dấu cách

Dữ liệu ra: Số lượng xe taxi tối thiểu để chở tất cả học sinh đến nơi.

Nhập	Xuất
5 1 2 4 3 3	4