Đề 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

STTTÊN BÀIFILE CHƯƠNG TRÌNHFILE DỮ LIỆUFILE KẾT QUẢ
 1Chia bánhCAKES.*CAKES.INPCAKES.OUT
 2Mua SáchBOOKS.*BOOKS.INPBOOKS.OUT
 3Đếm dãy con liên tiếpCNTSEQ.*CNTSE.INPCNTSE.OUT
( Dấu * được thay thế bởi ngôn ngữ lập trình Pascal, C/C++ hoặc Python tương ứng) 

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 
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 ————-