Đề ôn tập môn Tin học THCS - Đề số 59 - Năm học 2024-2025

Nội dung tài liệu: Đề ôn tập môn Tin học THCS - Đề số 59 - Năm học 2024-2025

1. Sinh nhật của Motarack giới hạn thời gian cho mỗi bài kiểm tra 2 giây giới hạn bộ nhớ cho mỗi bài kiểm tra 256 megabyte đầu vào đầu vào tiêu chuẩn đầu ra đầu ra tiêu chuẩn Dark sẽ tham dự sinh nhật của Motarack. Dark quyết định rằng món quà anh sẽ tặng cho Motarack là một mảngmộtmột của nn số nguyên không âm. Dark tạo ra mảng đó 1000 năm trước, vì vậy một số yếu tố trong mảng đó biến mất. Dark biết rằng Motarack ghét phải nhìn thấy một mảng có hai yếu tố liền kề với sự khác biệt tuyệt đối cao giữa chúng. Anh ta không có nhiều thời gian nên anh ta muốn chọn một số nguyênkk (0 ≤ k ≤ 109) và thay thế tất cả các phần tử bị thiếu trong mảng mộtmột với kk. Để cho m là sự khác biệt tuyệt đối tối đa giữa tất cả các yếu tố liền kề (tức là giá trị tối đa của | ai- ai + 1| cho tất cả 1 ≤ i ≤ n - 1) trong mảng a sau khi Dark thay thế tất cả các yếu tố còn thiếu bằng k. Tối nên chọn một số nguyên k vậy nên m được giảm thiểu. Bạn có thể giúp anh ta? Đầu vào Đầu vào bao gồm nhiều trường hợp thử nghiệm. Dòng đầu tiên chứa một số nguyêntt (1 ≤ t ≤ 104) - số lượng các trường hợp thử nghiệm. Mô tả các trường hợp thử nghiệm sau đây. Dòng đầu tiên của mỗi trường hợp kiểm tra chứa một số nguyên nn (2 ≤ n ≤ 105) - kích thước của mảng a. Dòng thứ hai của mỗi trường hợp thử nghiệm chứa n số nguyên a1, a2, ... , an(- 1 ≤ ai≤ 109). Nếu ai= - 1, sau đó số nguyên –thu I bị thiếu. Nó được đảm bảo rằng ít nhất một số nguyên bị thiếu trong mọi trường hợp thử nghiệm. Nó được đảm bảo, rằng tổng của nn cho tất cả các trường hợp thử nghiệm không vượt quá 4 ⋅ 105. Đầu ra In các câu trả lời cho từng trường hợp kiểm tra theo định dạng sau: Bạn nên in hai số nguyên, giá trị tối thiểu có thể là mm và một số nguyên k (0 ≤ k ≤ 109 làm cho sự khác biệt tuyệt đối tối đa giữa các phần tử liền kề trong mảng mộtmột tương đương với mm. Đảm bảo rằng sau khi thay thế tất cả các yếu tố còn thiếu bằng kk, sự khác biệt tuyệt đối tối đa giữa các yếu tố liền kề trở thành m. Nếu có nhiều hơn một có thể kk, bạn có thể in bất kỳ trong số họ. Thí dụ đầu vào Sao chép 7 5 -1 10 -1 12 -1 5 -1 40 35 -1 35 6
2. -1 -1 9 -1 3 -1 2 -1 -1 2 0 -1 4 1 -1 3 -1 7 1 -1 7 5 2 -1 5 đầu ra Sao chép 1 11 5 35 3 6 0 42 0 0 1 2 3 4 Câu thơ cho ông già Noel giới hạn thời gian cho mỗi bài kiểm tra 1 giây giới hạn bộ nhớ cho mỗi bài kiểm tra 256 megabyte đầu vào đầu vào tiêu chuẩn đầu ra đầu ra tiêu chuẩn Năm mới sắp tới! Vasya đã chuẩn bị một câu thơ mừng năm mới và muốn đọc thuộc lòng trước ông già Noel. Câu thơ của Vasya chứa nncác bộ phận. Nó cần ai giây để đọc phần thứ i Vasya không thể thay đổi thứ tự các phần trong câu thơ: trước hết anh ta đọc phần đó a1 giây, thứ hai - phần mất a2 giây, và như vậy. Sau khi đọc thuộc lòng câu thơ, Vasya sẽ nhận được số lượng quà bằng với số phần mà anh ta đọc thuộc lòng. Vasya có thể bỏ qua tối đa một phần của câu thơ trong khi đọc nó (nếu anh ta bỏ qua nhiều phần, thì Santa chắc chắn sẽ chú ý đến nó). Santa sẽ lắng nghe câu thơ của Vasya không hơn SSgiây Ví dụ, nếu s = 10, a = [ 100 , 9 , 1 , 1 ] ]và Vasya bỏ qua phần đầu tiên của câu thơ, sau đó anh ta nhận được hai món quà. Lưu ý rằng có thể đọc thuộc toàn bộ câu (nếu có đủ thời gian). Xác định phần nào Vasya cần bỏ qua để có được số lượng quà tặng tối đa có thể. Nếu Vasya không nên bỏ qua bất cứ điều gì, in 0 . Nếu có nhiều câu trả lời, hãy in bất kỳ câu trả lời nào. Bạn phải xử lý tt trường hợp kiểm tra.
3. Đầu vào Dòng đầu tiên chứa một số nguyên t (1 ≤ t ≤ 100) - số lượng các trường hợp thử nghiệm. Dòng đầu tiên của mỗi trường hợp thử nghiệm chứa hai số nguyên n và S (1 ≤ n ≤ 105, 1 ≤ s ≤ 109) - số phần trong câu thơ và số giây tối đa ông già Noel sẽ nghe Vasya, tương ứng. Dòng thứ hai của mỗi trường hợp thử nghiệm chứa n số nguyên a1, a2, ... , an (1 ≤ ai≤ 109) - thời gian cần thiết để đọc thuộc từng phần của câu thơ. Nó được đảm bảo rằng tổng của nn trên tất cả các trường hợp thử nghiệm không vượt quá 105. Đầu ra Đối với mỗi trường hợp thử nghiệm, hãy in một số nguyên - số phần mà Vasya cần bỏ qua để có được số lượng quà tặng tối đa. Nếu Vasya không nên bỏ qua bất kỳ phần nào, hãy in 0 . Thí dụ đầu vào Sao chép 3 7 11 2 9 1 3 18 1 4 4 35 11 9 10 7 1 8 5 đầu ra Sao chép 2 1 0 Bắt A giới hạn thời gian cho mỗi bài kiểm tra 1 giây giới hạn bộ nhớ cho mỗi bài kiểm tra 256 megabyte đầu vào đầu vào tiêu chuẩn đầu ra đầu ra tiêu chuẩn Lưu ý của người dịch: trong hệ thống phân loại phổ biến nhất của Nga, có bốn loại: 5, 4, 3, 2, càng cao càng tốt, tương ứng với A, B, C và F tương ứng trong hệ thống phân loại của Mỹ. Học kỳ sắp kết thúc và học sinh bắt đầu nghĩ về điểm số của mình. Hôm nay, một giáo sư nói với các sinh viên của mình rằng các điểm cho khóa học của anh ta sẽ được đưa ra tự động - anh ta sẽ tính trung bình đơn giản (trung bình số học) của tất cả các lớp được đưa ra cho phòng thí nghiệm làm việc theo thuật ngữ này và làm tròn đến số nguyên gần nhất. Việc làm tròn sẽ được thực hiện có lợi cho học sinh -4,5 sẽ được làm tròn lên 5 (như trong ví dụ 3), nhưng 4,4 sẽ được làm tròn xuống 4.
4. Điều này không tốt cho Vasya, người không nghĩ rằng những công việc trong phòng thí nghiệm đó sẽ ảnh hưởng đến bất cứ điều gì, vì vậy anh ta có thể nhận được điểm kém hơn 5 (thậm chí có thể sợ hãi 2). Tuy nhiên, giáo sư cho phép anh ta làm lại một số tác phẩm của Vasya để chọn tăng điểm trung bình. Vasya muốn làm lại càng ít phòng thí nghiệm càng tốt để có được 5 cho khóa học Tất nhiên, Vasya sẽ nhận được 5 cho phòng thí nghiệm làm việc, anh chọn làm lại. Giúp Vasya - tính toán số lượng công việc phòng thí nghiệm tối thiểu Vasya phải làm lại. Đầu vào Dòng đầu tiên chứa một số nguyên n - số điểm của Vasya (1 ≤ n ≤ 100). Dòng thứ hai chứa nn số nguyên từ 2 đến 5 - Điểm của Vasya cho phòng thí nghiệm của anh ấy hoạt động. Đầu ra Xuất ra một số nguyên duy nhất - số lượng phòng thí nghiệm tối thiểu mà Vasya phải làm lại. Có thể thấy rằng Vasya luôn có thể làm lại đủ các công việc trong phòng thí nghiệm để có được một 5. Ví dụ đầu vào Sao chép 3 4 4 4 đầu ra Sao chép 2 đầu vào Sao chép 4 5 4 5 5 đầu ra Sao chép 0 đầu vào Sao chép 4 5 3 3 5 đầu ra Sao chép 1
5. Thực hành của Polycarp giới hạn thời gian cho mỗi bài kiểm tra 2 giây giới hạn bộ nhớ cho mỗi bài kiểm tra 256 megabyte đầu vào đầu vào tiêu chuẩn đầu ra đầu ra tiêu chuẩn Polycarp đang thực hành kỹ năng giải quyết vấn đề của mình. Anh ấy có một danh sách n vấn đề khó khăn a1, a2, ... , an, tương ứng. Kế hoạch của anh ấy là luyện tập cho chính xác k ngày Mỗi ngày anh phải giải quyết ít nhất một vấn đề từ danh sách của mình. Polycarp giải quyết các vấn đề theo thứ tự chúng được đưa ra trong danh sách của mình, anh ta không thể bỏ qua bất kỳ vấn đề nào trong danh sách của mình. Anh phải giải quyết tất cả.nn vấn đề chính xác k ngày Do đó, mỗi ngày Polycarp giải quyết một chuỗi các vấn đề (liên tiếp) liên tục từ đầu danh sách. Anh ta không thể bỏ qua vấn đề hoặc giải quyết chúng nhiều lần. Kết quả là, trong k ngày anh sẽ giải quyết tất cả n các vấn đề. Các lợi nhuận của j- ngày thực hành của Polycarp là tối đa trong số tất cả những khó khăn của vấn đề Polycarp giải quyết trong thời gian j-tháng ngày (tức là nếu anh ta giải quyết vấn đề với các chỉ số từ L đến R trong một ngày, sau đó lợi nhuận của ngày là tối đa L ≤ i ≤ R). Các tổng lợi nhuận thực hành của ông là tổng của lợi nhuận trên khắp k ngày thực tập của mình. Bạn muốn giúp Polycarp có được tổng lợi nhuận tối đa có thể trên tất cả các cách hợp lệ để giải quyết vấn đề. Nhiệm vụ của bạn là phân phối tất cảnn vấn đề giữa kkngày thỏa mãn các điều kiện trên theo cách như vậy, tổng lợi nhuận là tối đa. Ví dụ, nếu n = 8 , k = 3 và a = [ 5 , 4 , 2 , 6 , 5 , 1 , 9 , 2 ], một trong những phân phối có thể có với tổng lợi nhuận tối đa là:[ 5 , 4 , 2 ] , [ 6 , 5 ] , [ 1 , 9 , 2 ] . Ở đây tổng lợi nhuận bằng 5 + 6 + 9 = 20. Đầu vào Dòng đầu tiên chứa hai số nguyên n và k (1 ≤ k ≤ n ≤ 2000) số lượng các vấn đề và số ngày, tương ứng. Dòng thứ hai của đầu vào chứa nn số nguyên a1, a2, ... , an (1 ≤ ai≤ 2000) - những khó khăn của các vấn đề trong danh sách của Polycarp, theo thứ tự chúng được đặt trong danh sách (tức là theo thứ tự Polycarp sẽ giải quyết chúng). Đầu ra Trong dòng đầu tiên của đầu ra in tổng lợi nhuận tối đa có thể . Trong dòng thứ hai in chính xác k những số nguyên dương t1, t2, .. , tk phải bằng n), Ở đâu tj có nghĩa là số lượng vấn đề Polycarp sẽ giải quyết trong jj-thứ ngày để đạt được tổng lợi nhuận tối đa có thể thực hành của mình. Nếu có nhiều câu trả lời có thể, bạn có thể in bất kỳ câu trả lời nào. Ví dụ đầu vào Sao chép
6. 8 3 5 4 2 6 5 1 9 2 đầu ra Sao chép 20 3 2 3 đầu vào Sao chép 5 1 1 1 1 1 1 đầu ra Sao chép 1 5 đầu vào Sao chép 4 2 1 2000 2000 2 đầu ra Sao chép 4000 2 2