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

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

1. Đề ôn số 26 Bai1.pas 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 d1, d2, , dn bao gồm n số nguyên. Nhiệm vụ của bạn là chia mảng này thành ba phần (một số phần có thể trống) theo cách sao cho mỗi phần tử của mảng thuộc chính xác một trong ba phần và mỗi phần tạo thành một phần phụ liên tiếp (có thể, trống) của mảng ban đầu. Đặt tổng các phần tử của phần đầu tiên là sum1, tổng các phần tử của phần thứ hai là sum2 và tổng các phần tử của phần thứ ba là s um3. Trong số tất cả các cách có thể để phân chia mảng, bạn phải chọn một cách sao cho sum1= sum3 và sum1 là tối đa có thể. Chính thức hơn, nếu phần đầu tiên của mảng chứa a các phần tử, phần thứ hai của mảng chứa b các phần tử và phần thứ ba chứa c các phần tử, sau đó: sum1=∑1≤i≤adi,sum1=∑1≤i≤adi, sum2=∑a+1≤i≤a+bdi,sum2=∑a+1≤i≤a+bdi, sum3=∑a+b+1≤i≤a+b+cdi. Tổng của một mảng trống là 00. Nhiệm vụ của bạn là tìm cách phân chia mảng sao cho sum1= sum3 và sum1 là tối đa có thể. Đầu vào Dòng đầu tiên chứa một số nguyên nn (1 ≤ n ≤ 2 ⋅ 105) - số phần tử trong mảng d. Dòng thứ hai của đầu vào chứa n số nguyên d1, d2, Lọ , dn (1 ≤ di≤ 109) - các phần tử của mảng d. Đầu ra In một số nguyên duy nhất - giá trị tối đa có thể của sum1, xem xét rằng điều kiện sum1= sum3 nhất định phải gặp. Rõ ràng, có ít nhất một cách hợp lệ để phân chia mảng tồn tại (sử dụng a = c = 0 và b = n). Ví dụ đầu vào Sao chép 5 1 3 1 1 4 đầu ra Sao chép 5 đầu vào
2. Sao chép 5 1 3 2 1 4 đầu ra Sao chép 4 đầu vào Sao chép 3 4 1 2 đầu ra Sao chép 0 Ghi chú Trong ví dụ đầu tiên, chỉ có một khả năng phân tách có thể tối đa hóa sum1: [ 1 , 3 , 1 ] , [ ] , [ 1 , 4 ] Trong ví dụ thứ hai, cách duy nhất để có sum1= 4 Là: [ 1 , 3 ] , [ 2 , 1 ] , [ 4 ][. Trong ví dụ thứ ba, chỉ có một cách để phân chia mảng: [ ] , [ 4 , 1 , 2 ] , [ ] Bai2.pas 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 Gần đây, Norge đã tìm thấy một chuỗi s = s1s2... sn bao gồm n chữ thường Latin. Như một bài tập để cải thiện tốc độ đánh máy của mình, anh quyết định gõ tất cả các chuỗi con của chuỗi S. Đúng tất cả n ( n + 1 )/2 của họ! Một chuỗi con của S là một chuỗi không trống x = s [ a ... b ] = sasa + 1... sb (1 ≤ a ≤ b ≤ n). Ví dụ: " auto " và " ton " là các chuỗi con của " automaton ". Ngay sau khi bắt đầu bài tập, Norge nhận ra rằng bàn phím của mình bị hỏng, cụ thể là, anh chỉ có thể sử dụng k Chữ cái Latinh c1, c2, ... , ck ra khỏi 26. Sau đó, Norge bắt đầu quan tâm đến việc có bao nhiêu chuỗi con S anh vẫn có thể gõ bằng bàn phím bị hỏng. Giúp anh ta tìm số này. Đầu vào Dòng đầu tiên chứa hai số nguyên cách nhau bằng dấu cách n và k (1 ≤ n ≤ 2 ⋅ 105, 1 ≤ k ≤ 26 - độ dài của chuỗi S và số lượng chữ cái Latinh vẫn có sẵn trên bàn phím. Dòng thứ hai chứa chuỗi S bao gồm chính xác n chữ thường Latin. Dòng thứ ba chứa k chữ Latinh chữ thường phân tách không gian c1, c2, ... , ck chữ cái vẫn có sẵn trên bàn phím. Đầu ra
3. In một số duy nhất - số lượng chuỗi con của S có thể được gõ chỉ bằng các chữ cái có sẵn c1, c2, ... , ck. input Copy 7 2 abacaba a b output Copy 12 input Copy 10 3 sadfaasdda f a d output Copy 21 input Copy 7 1 aaaaaaa b output Copy 0 Ghi chú Trong ví dụ đầu tiên Norge có thể in các chuỗi con s[1 2], s[2 3], s[1 3], s[1 1], s[2 2], s[3 3], s[5 6], s[6 7], s[5 7], s[5 5], s[6 6], s[7 7]. Bai3.pas 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 Gildong đang chơi một trò chơi video có tên Block Adventure . Trong Block Adventure, có n các cột của các khối trong một hàng và các cột được đánh số từ 1 đến n. Tất cả các khối có chiều cao bằng nhau. Chiều cao của cột thứ I được thể hiện là hi, đó là số khối được xếp chồng lên nhau trong cột thứ i Gildong chơi trò chơi như một nhân vật chỉ có thể đứng trên đỉnh của các cột. Lúc đầu, nhân vật đang đứng trên đỉnh của cột 1. Mục tiêu của trò chơi là đưa nhân vật lên đỉnh cột thứ n
4. Nhân vật này cũng có một chiếc túi có thể chứa vô số khối. Khi nhân vật ở trên đỉnh i- cột thứ hai, Gildong có thể thực hiện một trong ba hành động sau bao nhiêu lần tùy ý: • nếu có ít nhất một khối trên cột, hãy xóa một khối khỏi đỉnh cột I và đặt nó trong túi; • nếu có ít nhất một khối trong túi, lấy một khối ra khỏi túi và đặt nó lên trên cùng của cột thứ i; • nếu i < n và | hi + 1| ≤k, di chuyển nhân vật lên đỉnh của i + 1 cột. k là một số nguyên không âm được đưa ra vào đầu trò chơi. Lưu ý rằng chỉ có thể di chuyển đến cột tiếp theo . Trong hành động của hai loại đầu tiên, nhân vật vẫn ở trong cột thứ i và giá trị hii thay đổi. Nhân vật ban đầu có m khối trong túi. Gildong muốn biết liệu có thể giành chiến thắng trong trò chơi hay không. Giúp Gildong tìm câu trả lời cho câu hỏi của anh ấy. Đầu vào Mỗi thử nghiệm chứa một hoặc nhiều trường hợp thử nghiệm. Dòng đầu tiên chứa số lượng testtt (1 ≤ t ≤ 1000). 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 ba số nguyên nn, mmvà kk (1 ≤ n ≤ 1000, 0 ≤ m ≤ 106, 0 ≤ k ≤ 106) - số lượng cột trong trò chơi, số khối trong túi của nhân vật ở đầu và số nguyên không âm kk được mô tả trong tuyên bố. Dòng thứ hai của mỗi trường hợp thử nghiệm chứa nnsố nguyên. Các I số nguyên -th là hi (0 ≤ hi≤ 106), chiều cao ban đầu của cột thứ i Đầu ra Đối với mỗi trường hợp thử nghiệm, hãy in " YES " nếu có thể giành chiến thắng trong trò chơi. Nếu không, hãy in " NO ". Bạn có thể in từng chữ cái trong mọi trường hợp (trên hoặc dưới). Thí dụ đầu vào Sao chép 5 3 0 1 4 3 5 3 1 2 1 4 7 4 10 0 10 20 10 20 2 5 5 0 11 1 9 9 99 đầu ra Sao chép YES NO YES NO YES Ghi chú
5. Trong trường hợp đầu tiên, Gildong có thể lấy một khối từ cột 1, di chuyển đến 2-và cột, đặt khối lên 2-và cột, sau đó di chuyển đến cột thứ 3 Trong trường hợp thứ hai, Gildong phải đặt khối trong túi của mình lên 1cột thứ nhất để đi đến 2-và cột. Nhưng không thể đến 3 cột thứ-vì | h2- h3| =3>k và không có cách nào để giảm khoảng cách. Trong trường hợp thứ năm, nhân vật đã ở trên nncột thứ từ đầu để trò chơi được chiến thắng ngay lập tức. B. Cây bên đường (Phiên bản đơn giả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 Squirrel Liss thích các loại hạt. Có n cây (được đánh số từ 1 đến n từ tây sang đông) dọc theo một con phố và có một hạt ngon trên đỉnh của mỗi cây. Chiều cao của cây i là h i . Liss muốn ăn tất cả các loại hạt. Bây giờ Liss ở trên gốc của cây với số 1 . Trong một giây Liss có thể thực hiện một trong các hành động sau: • Đi lên hoặc xuống một đơn vị trên cây. • Ăn một hạt trên ngọn cây hiện tại. • Nhảy đến cây tiếp theo. Trong hành động này, chiều cao của Liss không thay đổi. Chính thức hơn, khi Liss ở độ cao h của cây i ( 1 ≤  i  ≤  n  - 1 ), cô ấy nhảy lên chiều cao h của cây i  + 1 . Hành động này không thể được thực hiện nếu h  >  h i  + 1 . Tính thời gian tối thiểu (tính bằng giây) cần thiết để ăn tất cả các loại hạt. Đầu vào Dòng đầu tiên chứa một số nguyên n ( 1   n  10 5 ) - số lượng cây. 4 N dòng tiếp theo chứa chiều cao của cây: dòng thứ i chứa số nguyên h i ( 1 ≤  h i  10 ) - chiều cao của cây với số i . Đầu ra In một số nguyên duy nhất - thời gian tối thiểu cần thiết để ăn tất cả các loại hạt trong vài giây. Ví dụ đầu vào Sao chép 2 1 2 đầu ra
6. Sao chép 5 đầu vào Sao chép 5 2 1 2 1 1 đầu ra Sao chép 14