Tải đề trắc nghiệm tại đây:
TỔNG QUAN BÀI THI
| Tên bài | File nguồn | File Input | File Output | Bộ nhớ tối đa | Thời gian |
| DÃY NGOẶC | Bai1.* | Bai1.INP | Bai1.OUT | 1024Mb | 1 giây |
| FIBONACCI | Bai2.* | Bai2.INP | Bai2.OUT | 1024Mb | 1 giây |
| LỄ HỘI | Bai3.* | Bai3.INP | Bai3.OUT | 1024Mb | 1 giây |
Phần mở rộng .* được thay thế bằng Cpp, Py ứng với các ngôn ngữ lập trình C++, Python.
HÃY LẬP TRÌNH GIẢI CÁC BÀI TOÁN SAU:
Bài 1. (5.0 điểm). DÃY NGOẶC
Người ta định nghĩa một dãy ngoặc đúng theo đệ quy như sau:
– Xâu A là xâu rỗng là một dãy ngoặc đúng
– Nếu xâu A là dãy ngoặc đúng thì (A) cũng là dãy ngoặc đúng
– Nếu xâu A và xâu B là dãy ngoặc đúng thì AB cũng là dãy ngoặc đúng.
Còn những xâu chứa những ký tự khác “(” và “)” được gọi là xâu không hợp lệ.
Ví dụ:
S = “(A()B)” là dãy “KHONG HOP LE” vì chứa chữ cái A và B
S = “()()(())” là dãy ngoặc “DUNG”
S = “()())” là dãy ngoặc “KHONG DUNG”
Cho xâu S. Hãy kiểm tra xâu S là dãy ngoặc “DUNG”, “KHONG DUNG” hay là xâu “KHONG HOP LE”
INPUT: Bai1.INP:
- Một xâu S chứa tối đa 106 phần tử
OUTPUT: Bai1.OUT:
- Thông báo “KHONG HOP LE” nếu xâu không hợp lệ
- Thông báo “DUNG” nếu xâu đúng
- Thông báo “KHONG DUNG” nếu xâu không đúng
Ví dụ:
| Bai1.INP | Bai1.OUT |
| (A()B) | KHONG HOP LE |
| ()()(()) | DUNG |
| ((()) | KHONG DUNG |
Bài 2 (4.0 điểm). FIBONACCI
Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó.
Dãy: 1, 1, 2, 3, 5, 8, 13, … là dãy Fibonacci.
Cho dãy a gồm N phần tử được đánh chỉ số từ 1 đến N.
Yêu cầu: Em hãy lập trình đếm số cách chia dãy a thành các dãy con gồm các phần tử liên tiếp sao cho tổng của mỗi dãy con là một số Fibonacci.
Dữ liệu vào:Vào từ file văn bản Bai2.INP
– Dòng đầu tiên chứa số nguyên N (
).
– Dòng tiếp theo chứa n số nguyên 
.
Dữ liệu ra: Ghi ra file Bai2.OUT một dòng duy nhất chứa một số nguyên là phần dư của số cách chia sau khi chia cho (109 + 7).
Ràng buộc:
– Có 30% test tương ứng 30% số điểm của bài với N≤20;
– Có 30% test tương ứng 30% số điểm của bài với N≤103;
– Có 40% test tương ứng với 40% số điểm của bài: Không có ràng buộc gì thêm.
Ví dụ:
| Bai2.INP | Bai2.OUT |
| 5 2 5 3 1 2 | 5 |
Giải thích: Có 5 cách chia là:
.
.- .
.
.
Bài 3. (3.0 điểm). LỄ HỘI
Trên trục đường chính của thị xã Cửa Lò có 
tòa nhà, được đánh số theo thứ tự từ 
đến 
, tòa nhà thứ 
có chiều cao là một số nguyên dương 
. Để chuẩn bị cho lẽ hội bắn pháo hoa năm nay, thị xã lập kế hoạch treo đèn lồng trang trí cho các tòa nhà. Hai tòa nhà liền kề và 
mất chi phí 
(
là hằng số). Chi phí của trục đườnglà tổng chi phí của các tòa nhà kề nhau, tức là 
. Thị xã Cửa Lò đẹp nhất khi các con đường đều đẹp nhất. Tuy nhiên, do nguồn kinh phí có hạn, lãnh đạo thị xã quyết định chọn giải pháp cho tu sửa nâng chiều cao một số ngôi nhà để tiết kiệm chi phí, cụ thể nếu tòa nhà nâng chiều cao thêm (đơn vị, 
) thì thị xã Cửa Lò phải mất một khoản chi phí là 
(có phương án không nâng chiều cao của các tòa nếu đã đạt chi phí tối ưu).
Yêu cầu: Cho biết 
và các chiều cao 
, bạn hãy giúp thị xã Cửa Lò tính chi phí thấp nhất khi thực hiện theo kế hoạch.
Dữ liệu: Vào từ file văn bản Bai3.INP
- Dòng đầu tiên chứa hai số nguyên
; - Mỗi dòng trong dòng sau chứa một số nguyên
.
Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.
Kết quả: Đưa ra file văn bản Bai3.OUT một số nguyên S là chi phí thấp nhất mà thị xã phải trả.
Ví dụ:
| Bai3.INP | Bai3.OUT |
| 5 2 2 3 5 1 4 | 15 |
Giải thích: Nâng tòa nhà thêm , nâng tòa nhà thêm . Khi đó chiều cao các tòa nhà lần lượt là: 
. Tổng chi phí là: 
Ràng buộc:
- Có 30% số test ứng với 30% số điểm của bài với
; 
; - Có 40% số test ứng với 40% số điểm của bài với
; 
; - Có 30% số test ứng với 30% số điểm của bài với ;
.
—————————HẾT—————————
