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

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

1. A. Vé may mắn 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 rất thích những con số may mắn. Mọi người đều biết rằng số may mắn là số nguyên dương có bản ghi thập phân chỉ chứa các chữ số may mắn 4 và 7 . Ví dụ, số 47 , 744 , 4 là may mắn và 5 , 17 , 467 thì không. Petya rất thích vé. Như chúng ta biết, mỗi vé có một số là số nguyên dương. Độ dài của nó bằng n ( n luôn luôn chẵn). Petya gọi một vé may mắn nếu số của vé là số may mắn và tổng các chữ số trong nửa đầu (tổng của n  / 2 chữ số đầu tiên ) bằng tổng các chữ số trong nửa sau (tổng của n  / cuối 2 chữ số). Kiểm tra xem vé đã cho là may mắn. Đầu vào Dòng đầu tiên chứa số nguyên n chẵn (2  n  50) - độ dài của số vé cần kiểm tra. Dòng thứ hai chứa một số nguyên có độ dài bằng chính xác n - số vé. Số có thể chứa số không hàng đầu. Đầu ra Trên dòng đầu tiên in " CÓ " nếu số vé đã cho là may mắn. Nếu không, hãy in " KHÔNG " (không có dấu ngoặc kép). Ví dụ đầu vào Sao chép 2 47 đầu ra Sao chép KHÔNG đầu vào Sao chép 4 4738 đầu ra Sao chép KHÔNG đầu vào Sao chép 4 4774 đầu ra
2. Sao chép ĐÚNG Ghi chú Trong mẫu đầu tiên, tổng các chữ số trong nửa đầu không bằng tổng các chữ số trong nửa sau ( 4 ≠ 7 ). Trong mẫu thứ hai, số vé không phải là số may mắn. B. Vòng tròn số 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 nhận n số a1, a2, ... , an. Là nó có thể sắp xếp chúng theo một vòng tròn theo cách như vậy mà mỗi số là đúng ít hơn tổng của các nước láng giềng? Ví dụ, cho mảng [ 1 , 4 , 5 , 6 , 7 , 8 ]], sự sắp xếp bên trái là hợp lệ, trong khi sự sắp xếp bên phải thì không, như 5 ≥ 4 + 1 vaf 8 > 1 + 6 Đầu vào Dòng đầu tiên chứa một số nguyên nn (3 ≤ n ≤ 105) - số lượng số. Dòng thứ hai chứa nn số nguyên a1, a2, ... , an (1 ≤ ai≤ 109) - những con số. Các số đã cho không nhất thiết phải khác biệt (nghĩa là trùng lặp được cho phép). Đầu ra Nếu không có giải pháp, hãy xuất " KHÔNG " trong dòng đầu tiên. Nếu có giải pháp, hãy xuất " CÓ " trong dòng đầu tiên. Trong đầu ra dòng thứ hainnsố - các phần tử của mảng theo thứ tự chúng sẽ nằm trong vòng tròn. Phần tử đầu tiên và cuối cùng bạn xuất ra
3. được coi là hàng xóm trong vòng tròn. Nếu có nhiều giải pháp, hãy đưa ra bất kỳ giải pháp nào. Bạn có thể in vòng tròn bắt đầu với bất kỳ yếu tố nào. Ví dụ đầu vào Sao chép 3 2 4 3 đầu ra Sao chép ĐÚNG 4 2 3 đầu vào Sao chép 5 1 2 3 4 4 đầu ra Sao chép ĐÚNG 4 4 2 1 3 đầu vào Sao chép 3 13 8 5 đầu ra Sao chép KHÔNG đầu vào Sao chép 4 1 10 100 1000 đầu ra Sao chép KHÔNG Ghi chú Một trong những sắp xếp có thể được hiển thị trong ví dụ đầu tiên: 4 < 2 + 3 2 < 4 + 3 3 < 4 + 2 Một trong những sắp xếp có thể được hiển thị trong ví dụ thứ hai. Dù chúng ta sắp xếp thế nào 13 , 8 , 5 trong một vòng tròn trong ví dụ thứ ba, 13 sẽ có số 8 và 5 như hàng xóm, nhưng 13 ≥ 8 + 5
4. Không có giải pháp trong ví dụ thứ tư. B. Cấu trúc Suffix 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 Bizon the Champion không chỉ là một con bò rừng. Anh ấy cũng là một người yêu thích của nhóm "Bizons". Tại một cuộc thi, "Bizons" gặp phải vấn đề sau: "Bạn được cung cấp hai từ riêng biệt (chuỗi các chữ cái tiếng Anh), s và t . Bạn cần chuyển từ s thành từ t ". Nhiệm vụ này có vẻ đơn giản đối với các chàng trai vì họ biết rõ cấu trúc dữ liệu hậu tố. Bizon Senior thích hậu tố tự động. Bằng cách áp dụng nó một lần vào một chuỗi, anh ta có thể xóa khỏi chuỗi này bất kỳ ký tự đơn nào. Bizon Middle biết hậu tố mảng tốt. Bằng cách áp dụng nó một lần vào một chuỗi, anh ta có thể hoán đổi bất kỳ hai ký tự của chuỗi này. Các chàng trai không biết gì về cây hậu tố, nhưng nó có thể giúp họ làm được nhiều hơn thế. Bizon the Champion tự hỏi liệu "Bizons" có thể giải quyết vấn đề hay không. Có lẽ, giải pháp không yêu cầu cả cấu trúc dữ liệu. Tìm hiểu xem các chàng trai có thể giải quyết vấn đề và nếu họ có thể, làm thế nào để họ làm điều đó? Họ có thể giải quyết nó chỉ bằng cách sử dụng hậu tố automaton hoặc chỉ với việc sử dụng mảng hậu tố hoặc họ cần cả hai cấu trúc? Lưu ý rằng bất kỳ cấu trúc nào cũng có thể được sử dụng không giới hạn số lần, các cấu trúc có thể được sử dụng theo bất kỳ thứ tự nào. Đầu vào Dòng đầu tiên chứa một từ không trống s . Dòng thứ hai chứa một từ không trống t . Từ s và t khác nhau. Mỗi từ chỉ bao gồm các chữ cái tiếng Anh viết thường. Mỗi từ chứa tối đa 100 chữ cái. Đầu ra Trong dòng đơn in câu trả lời cho vấn đề. In " cần cây " (không có dấu ngoặc kép) nếu từ s không thể chuyển thành từ t ngay cả khi sử dụng cả mảng hậu tố và hậu tố tự động. In " automaton " (không có dấu ngoặc kép) nếu bạn chỉ cần hậu tố automaton để giải quyết vấn đề. In " mảng " (không có dấu ngoặc kép) nếu bạn chỉ cần mảng hậu tố để giải quyết vấn đề. In " cả hai " (không có dấu ngoặc kép), nếu bạn cần cả hai cấu trúc dữ liệu để giải quyết vấn đề. Điều được đảm bảo rằng nếu bạn có thể giải quyết vấn đề chỉ bằng cách sử dụng mảng hậu tố, thì không thể giải quyết vấn đề này chỉ bằng cách sử dụng hậu tố tự động. Điều này cũng đúng với hậu tố automaton. Examples
5. input Copy automaton tomat output Copy automaton input Copy array arary output Copy array input Copy both hot output Copy both input Copy need tree output Copy need tree B. Mảng khô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, a2, ... , an. Trong một thao tác, bạn có thể chọn hai yếu tố ai và ajj (i ≠ j) và giảm từng cái một. Bạn cần kiểm tra xem có thể làm cho tất cả các yếu tố bằng không hay không. Đầu vào Dòng đầu tiên chứa một số nguyên nn (2 ≤ n ≤ 105) - kích thước của mảng. Dòng thứ hai chứa nn số nguyên a1, a2, ... , an (1 ≤ ai≤ 109) - các phần tử của mảng. Đầu ra
6. In " CÓ " nếu có thể làm cho tất cả các yếu tố bằng không, nếu không thì in " KHÔNG ". Ví dụ đầu vào Sao chép 4 1 1 2 2 đầu ra Sao chép ĐÚNG đầu vào Sao chép 6 1 2 3 4 5 6 đầu ra Sao chép KHÔNG Ghi chú Trong ví dụ đầu tiên, bạn có thể làm cho tất cả các phần tử bằng 0 trong 3 hoạt động: • Giảm bớt a1 và a2, • Giảm bớt a3 và a4, • Giảm bớt a3 và a4 Trong ví dụ thứ hai, người ta có thể chỉ ra rằng không thể làm cho tất cả các phần tử bằng 0