
Đề thi Thực hành Bảng B- Khối THCS
Thời gian: 120 phút (không kể thời gian phát đề)
Tổng quan Bài thi
STT | TÊN BÀI | FILE CHƯƠNG TRÌNH | FILE DỮ LIỆU | FILE KẾT QUẢ |
1 | Chia bánh | CAKES.* | CAKES.INP | CAKES.OUT |
2 | Mua Sách | BOOKS.* | BOOKS.INP | BOOKS.OUT |
3 | Đếm dãy con liên tiếp | CNTSEQ.* | CNTSE.INP | CNTSE.OUT |
Bài 1: Chia bánh (6 điểm)
Với mong muốn kỳ thi Tin học trẻ cấp thành phố sẽ là sân chơi bổ ích và vui vẻ cho các bạn học sinh, BTC đã mua N chiếc bánh kem nhỏ xinh để thưởng cho các bạn thí sinh. Vấn đề là BTC muốn tìm ra tất cả các cách chia đều số bánh kem trên cho các bạn mà không cần phải cắt bất kỳ chiếc bánh nào.
Yêu cầu: Hãy giúp BTC tìm tất cả các cách chia cho các bạn thí sinh thỏa mãn điều kiện trên. Dữ liệu: Đọc vào từ file CAKES.INP: một dòng duy nhất chứa số nguyên N (1 ≤ N ≤ 1012); N là số nguyên.
Kết quả: Ghi ra file CAKES.OUT: Ghi ra đáp án theo thứ tự tăng dần, mỗi số trên một dòng. Ví dụ:
CAKES.INP |
6 |
CAKES.OUT |
1 2 3 6 |
Giải thích: Với 6 chiếc bánh, BTC có các cách chia đều như sau: 1 bạn (6 ), 2 bạn (mỗi bạn 3); 3 bạn (mỗi bạn 2 ); 6 bạn ( mỗi bạn 1).
Bài 2: Mua sách (7 điểm)
Trong khi đợi BTC khai mạc hội thi, Nam ghé vào 1 hiệu sách gần trường để mua sách. Hiệu sách đặc biệt này bán n cuốn sách khác nhau. Người bán hàng luôn ghi rõ giá tiền và số trang của mỗi cuốn sách tương ứng trên kệ. Với số tiền đang có, Nam đã quyết định rằng tổng số tiền mua sách của Nam sẽ nhiều nhất là x..
Yêu cầu: Hãy giúp Nam tính xem với quyết định của cậu thì số trang sách tối đa Nam có thể mua là bao nhiêu? Nam chỉ mua mỗi cuốn sách nhiều nhất một lần.
Dữ liệu: Đọc vào từ file BOOKS.INP
∙ Dòng đầu tiên chứa hai số nguyên n(1 ≤ n ≤ 1000) và x (1 ≤ x ≤ 105): tương ứng với số lượng sách và tổng số tiền tối đa.
∙ Dòng tiếp theo chứa n số nguyên ℎ1, ℎ2, … , ℎn(1 ≤ ℎi ≤ 1000): tương ứng với giá của mỗi cuốn sách.
∙ Dòng cuối cùng chứa n số nguyên s1, s2, … , sn(1 ≤ ℎi, si ≤ 1000): tương ứng với số trang của mỗi cuốn sách.
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ả: Ghi ra file BOOKS.OUT: một số nguyên là số trang sách nhiều nhất mà Nam có thể mua theo yêu cầu.
Ví dụ:
BOOKS.INP |
4 13 5 8 4 3 6 12 8 2 |
BOOKS.OUT |
20 |
Giải thích: Nam có thể mua quyển sách 2 và 3. Giá của chúng là 4+8 = 12 và số trang là 12+8=20.
Bài 3: Đếm dãy con liên tiếp (7 điểm)
Cho dãy số A có n số nguyên a1, a2, … , an. Một dãy con liên tiếp các số hạng của dãy A là dãy các số hạng từ số hạng ai đến số hạng aj(1 ≤ i ≤ j ≤ n).
Yêu cầu: Hãy cho biết dãy A có bao nhiêu dãy con liên tiếp mà giá trị tuyệt đối của tổng các số hạng trong dãy con đó lớn hơn một số nguyên dương S cho trước.
Dữ liệu: Vào từ file văn bản CNTSEQ.INP:
∙ Dòng thứ nhất chứa hai số nguyên dương n và S (n ≤ 105, S ≤ 1014). ∙ Dòng thứ hai chứa n số nguyên a1, a2, . . , an (|ai| ≤ 109).
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ả: Ghi ra file văn bản CNTSEQ.OUT trên một dòng, một số nguyên duy nhất là số dãy con liên tiếp thỏa mãn yêu cầu của bài toán.
Ví dụ:
CNTSEQ.INP |
4 4 5 -2 8 -6 |
CNTSEQ.OUT |
6 |
Giải thích: Trong ví dụ có 6 dãy con thỏa mãn yêu cầu là:{5},{8},{−6},{−2; 8}, {5; −2; 8} và {5; −2; 8; −6}.
Ràng buộc:
∙ Có 50% số test ứng với 50% số điểm của bài có n ≤ 100.
∙ Có 30% test khác ứng với 30% số điểm của bài có n ≤ 103.
∙ Có 20% test còn lại ứng với 20% số điểm của bài có n ≤ 105.
————- HẾT ————-