Đề luyện thi học sinh giỏi cấp tỉnh môn Tin học Lớp 11 - Đề 11

Nội dung text: Đề luyện thi học sinh giỏi cấp tỉnh môn Tin học Lớp 11 - Đề 11

1. ĐỀ 11 (*) ĐỀ LUYỆN THI HSG CẤP TỈNH MÔN: TIN HỌC (Tổng hợp từ nhiều nguồn) Thời gian: 150 phút (không kể thời gian phát đề) TỔNG QUAN ĐỀ THI Bài File bài làm File dữ liệu File kết quả Điểm Bài 1: Ba số nguyên THREEINT.* THREEINT.INP THREEINT.OUT 6 Bài 2: Người giao hàng DELIVERY.* DELIVERY.INP DELIVERY.OUT 7 Bài 3: Lò cò JUMP.* JUMP.INP JUMP.OUT 7 Bài 1: Ba số nguyên Cho ba số nguyên A, B, C. Bạn có thể thực hiện các thao tác sau số lần tùy ý: chọn một trong ba số A, B, C và tăng hoặc giảm nó đi 1 đơn vị. ❖ Yêu cầu: Tìm số thao tác ít nhất để tạo ra một dãy A, B, C là cấp số cộng, tức là dãy thỏa mãn điều kiện B – A = C – B hoặc 2 * B = A + C. ❖ Dữ liệu vào: file THREEINT.INP - Dòng đầu tiên chứa một số nguyên T – số lượng truy vấn. - T dòng tiếp theo, mỗi dòng chứa ba số nguyên A, B, C. ❖ Dữ liệu ra: file THREEINT.OUT - Với mỗi bộ test, in ra một dòng chứa một số nguyên – số thao tác ít nhất. ❖ Ràng buộc: - 1 ≤ T ≤ 104 - -109 ≤ A, B, C ≤ 109 THREEINT.INP THREEINT.OUT Giải thích 5 0 - Testcase 1: Không cần dùng thao tác -5 0 5 7 nào bởi 0 - (-5) = 5 - 0 -5 7 6 105 -Testcase 2: Chúng ta có thể tạo cấp số -10 -100 20 2 cộng trong 7 thao tác: thêm 1 vào A = - 1 -1 1 8 5 và giảm 1 sáu lần vào B = 7 51 23 10 Bài 2: Người giao hàng An và Bình là hai người giao hàng duy nhất của Highland Coffee. Hôm này, quán nhận được N đơn hàng. Biết rằng, số tiền hoa hồng của mỗi đơn hàng có thể khác nhau khi được giao bởi An hoặc Bình. Cụ thể hơn, nếu An nhận đơn hàng thứ i, anh ta nhận được Ai đồng, và nếu Bình nhận đơn hàng này, anh ấy nhận được Bi đồng. Họ quyết định rằng họ tự phân phối các đơn đặt hàng sao cho tổng số tiền hoa hồng của hai người đạt tối đa có thể. Một đơn hàng chỉ được xử lý bởi một người. Ngoài ra, do hạn chế thời gian nên An không thể nhận nhiều hơn X đơn hàng và Bình không thể nhận nhiều hơn Y đơn hàng. Đảm bảo rằng X + Y lớn hơn hoặc bằng N, nghĩa là tất cả đơn hàng có thể được xử lý bới An và Bình. Vui lòng tìm ra tổng số tiền hoa hồng tối đa có thể của An và Bình khi xử lý tất cả các đơn hàng. ❖ Dữ liệu vào: file DELIVERY.INP - Dòng đầu tiên chứa ba số N, X, Y. (1 ≤ N ≤ 105; 1 ≤ X, Y ≤ N; X + Y ≤ N) 4 - Dòng thứ 2 chứa N số nguyên. Số nguyên thứ i đại diện cho Ai. (1 ≤ Ai ≤ 10 ) WEBSITE Trang 1/2 – ĐỀ 11
2. 4 - Dòng thứ 3 chứa N số nguyên. Số nguyên thứ i đại diện cho Bi. (1 ≤ Bi ≤ 10 ) ❖ Dữ liệu ra: file DELIVERY.OUT - In ra kết quả của bài toán. DELIVERY.INP DELIVERY.OUT Giải thích 5 3 3 21 Bình nhận 3 đơn hàng đầu 1 2 3 4 5 tiên (hoặc 2), An nhận 5 4 3 2 1 các đơn hàng còn lại. Bài 3: Lò cò Nhảy lò cò là trò chơi dân gian của Việt Nam. Người trên hành tinh X cũng rất thích trò chơi này và họ đã cải biên trò chơi này như sau: Trên mặt phẳng vẽ n vòng tròn được đánh số từ 1 đến n. Tại vòng tròn i người ta điền số nguyên dương ai . Hai số trên hai vòng tròn tùy ý không nhất thiết phải khác nhau. Tiếp đến người ta vẽ các mũi tên, mỗi mũi tên hướng từ một vòng tròn đến một vòng tròn khác. Quy tắc vẽ mũi tên là: Nếu có ba số ai, aj, ak thỏa mãn ak = ai + aj thì vẽ mũi tên hướng từ vòng tròn i đến vòng tròn k và mũi tên hướng từ vòng tròn j đến vòng tròn k. Người chơi chỉ được di chuyển từ một vòng tròn đến một vòng tròn khác nếu có mũi tên xuất phát từ một trong số các vòng tròn, di chyển theo cách mũi tên đã vẽ để đi đến các vòng tròn khác. Người thắng cuộc sẽ là người tìm được cách di chuyển qua nhiều vòng tròn nhất. Ví dụ: Với 5 vòng tròn và các số trong vòng tròn là 1, 2, 8, 3, 5, trò chơi được trình bày trong hình dưới đây: Khi đó có thể di chuyển được nhiều nhất qua 4 vòng tròn (tương ứng với đường di chuyển được tô đậm trên hình vẽ). ❖ Yêu cầu: Hãy xác định xem trong trò chơi mô tả ở trên, nhiều nhất có thể di chuyển được qua bao nhiêu vòng tròn? ❖ Dữ liệu vào: file JUMP.INP - Dòng đầu tiên chứa số nguyên n (3 ≤ n ≤ 1000); 9 - Dòng thứ hai chứa dãy số nguyên dương a1 , a2 , , an (ai ≤ 10 , i=1, 2 , , n). Hai số liên tiếp trên một dòng cách nhau một khoảng trắng. ❖ Dữ liệu ra: file JUMP.OUT - In ra số vòng tròn trên đường di chuyển tìm được. JUMP.INP JUMP.OUT 5 4 1 2 8 3 5 WEBSITE Trang 2/2 – ĐỀ 11