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

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

1. Biểu tượng cảm xúc 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 Có nnemote trong trò chơi thẻ kỹ thuật số rất phổ biến (trò chơi này khá nổi tiếng vì vậy chúng tôi sẽ không nói tên của nó). CácTôiTôi-theo emote làm tăng hạnh phúc của đối phương bằng mộtTôimộtTôi các đơn vị (tất cả chúng ta đều biết rằng các biểu tượng cảm xúc trong trò chơi này được sử dụng để làm cho đối thủ hài lòng). Bạn chỉ có thời gian để sử dụng một số biểu tượng cảm xúc mmlần Bạn được phép sử dụng bất kỳ cảm xúc nào một lần, nhiều lần hoặc không sử dụng nó. Hạn chế duy nhất là bạn không thể sử dụng cùng một emote hơn k nhiều lần liên tiếp (nếu không đối thủ sẽ nghĩ rằng bạn đang troll anh ta). Lưu ý rằng hai biểu tượng cảm xúc i và j (i ≠ j) như vậy mà ai= aj được coi là khác nhau . Bạn phải làm cho đối thủ của bạn hạnh phúc nhất có thể. Tìm hạnh phúc tối đa có thể của đối thủ. Đầu vào Dòng đầu tiên chứa ba số nguyên n , m và k (2 ≤ n ≤ 2 ⋅ 105, 1 ≤ k ≤ m ≤ 2 ⋅ 109) - số lượng emote, số lần bạn có thể sử dụng emote và số lần tối đa bạn có thể sử dụng cùng một emote trong một hàng. Dòng thứ hai của đầu vào chứa nn số nguyên a1, a2, ... , an (1 ≤ ai≤ 109), Ở đây ai là giá trị hạnh phúc của TôiTôi-thứ emote. Đầu ra In một số nguyên - hạnh phúc tối đa của đối thủ nếu bạn sử dụng biểu tượng theo cách thỏa mãn tuyên bố vấn đề. Ví dụ đầu vào Sao chép 6 9 2 1 3 3 7 4 2 đầu ra Sao chép 54 đầu vào Sao chép 3 1000000000 1 1000000000 987654321 1000000000 đầu ra Sao chép 1000000000000000000
2. Trẻ em và đồ chơi 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 Vào ngày của trẻ em, một đứa trẻ đã nhận được một món đồ chơi từ Delayyy. Tuy nhiên, đứa trẻ nghịch ngợm đến mức không thể chờ đợi để phá hủy đồ chơi. Đồ chơi bao gồm n phần và dây thừng m . Mỗi sợi dây liên kết hai phần, nhưng mỗi cặp phần được liên kết bởi nhiều nhất một sợi dây. Để chia đồ chơi, trẻ phải loại bỏ tất cả các bộ phận của nó. Đứa trẻ có thể loại bỏ một bộ phận tại một thời điểm, và mỗi lần loại bỏ tiêu thụ một năng lượng. Hãy xác định giá trị năng lượng của phần i là v i . Đứa trẻ dành v f 1  +  v f 2  + ... +  v f k năng lượng để loại bỏ phần i trong đó f 1 ,  f 2 , ...,  f k là những phần được kết nối trực tiếp với i -th và chưa được gỡ bỏ. Giúp trẻ tìm hiểu, tổng năng lượng tối thiểu mà trẻ nên dành để loại bỏ tất cả n phần là bao nhiêu. Đầu vào Dòng đầu tiên chứa hai số nguyên n và m ( 1  n  ≤ 1000 ; 0 ≤  m  2000 ). Dòng thứ hai chứa n số 5 nguyên: v 1 ,  v 2 , ...,  v n ( 0 ≤  v i  10 ). Sau đó theo m dòng, mỗi dòng chứa hai số nguyên x i và y i , đại diện cho một sợi dây từ phần x i đến phần y i ( 1 ≤  xi ,  y i  ≤  n ; x i  ≠  y i ). Xem xét tất cả các phần được đánh số từ 1 đến n . Đầu ra Xuất ra tổng năng lượng tối thiểu mà trẻ nên dành để loại bỏ tất cả n phần của đồ chơi. Ví dụ đầu vào Sao chép 4 3 10 20 30 40 1 4 1 2 2 3 đầu ra Sao chép 40 đầu vào Sao chép 4 4 100 100 100 100 1 2
3. 2 3 2 4 3 4 đầu ra Sao chép 400 đầu vào Sao chép 7 10 40 10 20 10 20 80 40 1 5 4 7 4 5 5 2 5 7 6 4 1 6 1 3 4 3 1 4 đầu ra Sao chép 160 Làm sắc nét mảng 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 Bạn được cung cấp một mảng a1, ... , an , của n số nguyên không âm. Hãy gọi nó là sắc nét khi và chỉ khi tồn tại một số nguyên1 ≤ k ≤ n như vậy mà a1 ak + 1> .. > an. Đặc biệt, bất kỳ mảng tăng hoặc giảm nghiêm ngặt đều được làm sắc nét . Ví dụ: • Các mảng [ 4 ], [ 0 , 1 ], [ 12 , 10 , 8 ] và [ 3 , 11 , 15 , 9 , 7 , 4 ] được mài sắc; • Các mảng [ 2 , 8 , 2 , 8 , 6 , 5 ], [ 0 , 1 , 1 , 0 ] và [ 2 , 5 , 6 , 9 , 8 , 8 ] được không mài nhọn. Bạn có thể thực hiện thao tác sau bao nhiêu lần tùy ý: chọn bất kỳ phần tử tích cực nghiêm ngặt nào của mảng và giảm nó xuống một. Chính thức, bạn có thể chọn bất kỳTôiTôi (1 ≤ i ≤ n) như vậy mà ai> 0 và phân công ai: = ai- 1.
4. Cho biết nếu có thể làm cho mảng đã cho được làm sắc nét bằng cách sử dụng một số số (có thể bằng 0) của các hoạt động này. Đầ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 ≤ 15 000 ) - 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 thử nghiệm chứa một số nguyên duy nhất nn (1 ≤ n ≤ 3 ⋅ 105). Dòng thứ hai của mỗi trường hợp thử nghiệm chứa một chuỗi nn số nguyên không âm a1, ... , an (0 ≤ aai≤ 109). 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á 3 ⋅ 105. Đầu ra Đối với mỗi trường hợp thử nghiệm, hãy xuất một dòng duy nhất có chứa " Yes " (không có dấu ngoặc kép) nếu có thể làm cho mảng đã cho được làm sắc nét bằng cách sử dụng các thao tác được mô tả hoặc " No" (không có dấu ngoặc kép). Thí dụ đầu vào Sao chép 10 1 248618 3 12 10 8 6 100 11 15 9 7 8 4 0 1 1 0 2 0 0 2 0 1 2 1 0 2 1 1 3 0 1 0 3 1 0 1 đầu ra Yes Yes Yes No No Yes Yes
5. Yes Yes No Tìm đá cẩm thạch 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 Petya và Vasya đang chơi một trò chơi. Petya có n cặp kính không trong suốt, đứng thành một hàng. Vị trí của kính được lập chỉ mục với các số nguyên từ 1 đến n từ trái sang phải. Lưu ý rằng các vị trí được lập chỉ mục nhưng kính thì không. Đầu tiên Petya đặt một viên bi dưới kính ở vị trí s . Sau đó, anh ta thực hiện một số hoạt động xáo trộn (có thể bằng không). Một thao tác xáo trộn có nghĩa là di chuyển kính từ vị trí đầu tiên sang vị trí p 1 , kính từ vị trí thứ hai sang vị trí p 2 , v.v. Đó là, một kính đi từ vị trí i đến vị trí p i . Xem xét tất cả các kính đang di chuyển đồng thời trong một hoạt động xáo trộn. Khi kính được xáo trộn, đá cẩm thạch không di chuyển từ kính này sang kính khác: nó di chuyển cùng với kính ban đầu được đặt vào. Sau tất cả các thao tác xáo trộn, Petya cho Vasya thấy quả bóng đã di chuyển đến vị trí t . Nhiệm vụ của Vasya là cho biết số lượng hoạt động xáo trộn tối thiểu mà Petya đã thực hiện hoặc xác định rằng Petya đã phạm sai lầm và viên bi không thể có được từ vị trí s đến vị trí t . Đầu vào Dòng đầu tiên chứa ba số nguyên: n ,  s ,  t (1 ≤  n  ≤ 10 5 ; 1 ≤  s ,  t  ≤  n ) - số lượng kính, vị trí ban đầu và cuối cùng của quả bóng. Dòng thứ hai chứa n số nguyên được phân tách bằng dấu cách: p 1 ,  p 2 , ...,  p n (1 ≤  p i  ≤  n ) - các tham số thao tác xáo trộn. Nó được đảm bảo rằng tất cả các pi là khác biệt. Lưu ý rằng s có thể bằng t . Đầu ra Nếu viên bi có thể di chuyển từ vị trí s sang vị trí t , sau đó in trên một dòng một số nguyên không âm - số lượng tối thiểu các thao tác xáo trộn, cần thiết để đưa viên bi đến vị trí t . Nếu không thể, in số -1. Ví dụ đầu vào Sao chép 4 2 1 2 3 4 1
6. đầu ra Sao chép 3 đầu vào Sao chép 4 3 3 4 1 3 2 đầu ra Sao chép 0 đầu vào Sao chép 4 3 4 1 2 3 4 đầu ra Sao chép -1 đầu vào Sao chép 3 1 3 2 1 3 đầu ra Sao chép -1