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

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

1. De on so 51 Đào tạo đa khoa 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 muốn đào tạo trước một cuộc thi lập trình khác. Trong ngày đầu tiên đào tạo, anh ấy nên giải quyết chính xác 1 vấn đề, trong ngày thứ hai - chính xác 2 vấn đề, trong ngày thứ ba - chính xác 3 vấn đề, và như vậy. Trong thời gian k-ngày anh nên giải quyết. k các vấn đề. Polycarp có một danh sách n các cuộc thi, cuộc thi thứ i năm bao gồm ai các vấn đề. Trong mỗi ngày, Polycarp phải chọn chính xác một trong những cuộc thi mà anh chưa giải quyết và giải quyết nó. Anh ấy giải quyết chính xác k vấn đề từ cuộc thi này . Các vấn đề khác được loại bỏ từ nó. Nếu không có cuộc thi bao gồm ít nhất k vấn đề mà Polycarp chưa giải quyết được trong thời gian k-ngày thứ hai, rồi Polycarp dừng tập luyện. Polycarp có thể đào tạo bao nhiêu ngày nếu anh ấy chọn các cuộc thi một cách tối ưu? Đầu vào Dòng đầu tiên chứa một số nguyên n (1≤n≤2⋅105) - số lượng cuộc thi. Dòng thứ hai của đầu vào chứa nn số nguyên a1, a2, ... , an (1≤ai≤2⋅105) - số lượng sự cố trong cuộc thi thứ i Đầu ra In một số nguyên - số ngày tối đa Polycarp có thể đào tạo nếu anh ta chọn các cuộc thi một cách tối ưu. Ví dụ đầu vào Sao chép 4 3 1 4 1 đầu ra Sao chép 3 đầu vào Sao chép 3 1 1 1 đầu ra Sao chép 1
2. đầu vào Sao chép 5 1 1 1 2 2 đầu ra Sao chép 2 Lạ 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 Bạn được cung cấp một mảng mộtmột chiều dài nn. Bạn cũng được cung cấp một tập hợp các vị trí riêng biệt p1, p2, ... , pm, Ở đâu 1 ≤ pi< n . Vị trí pi có nghĩa là bạn có thể trao đổi các yếu tố a [ pi] và a[ pi+ 1 ]. Bạn có thể áp dụng thao tác này bất kỳ số lần cho mỗi vị trí nhất định . Nhiệm vụ của bạn là xác định xem có thể sắp xếp mảng ban đầu theo thứ tự không giảm hay không (a1≤ at2≤ ⋯ ≤ an chỉ sử dụng giao dịch hoán đổi. Ví dụ, nếu a = [ 3 , 2 , 1 ] và p = [ 1 , 2 ], sau đó chúng ta có thể trao đổi các phần tử đầu tiên a [ 2 ] và a [ 3 ] (vì vị trí 2 được chứa trong tập đã cho p). Chúng tôi nhận được mảng a = [ 3 , 1 , 2 ]. Sau đó, chúng tôi trao đổi a [ 1 ] và a [ 2 ] (Chức vụ 1 cũng được chứa trong p). Chúng tôi nhận được mảng a = [ 1 , 3 , 2 ]. Cuối cùng, chúng tôi trao đổi a[ 2 ] và a[ 3 ] một lần nữa và nhận được mảng a = [ 1 , 2 , 3 ], được sắp xếp theo thứ tự không giảm. Bạn có thể thấy rằng nếu a = [ 4 , 1 , 2 , 3 ] và p = [ 3 , 2 ] sau đó bạn không thể sắp xếp mảng. Bạn phải trả lời tt trường hợp kiểm tra độc lập. Đầu vào Dòng đầu tiên chứa một số nguyên tt (1 ≤ t ≤ 100) - số lượng các trường hợp thử nghiệm. Sau đó tttrường hợp kiểm tra làm theo. Dòng đầu tiên của mỗi trường hợp thử nghiệm chứa hai số nguyênnn và mm (1 ≤ m < n ≤ 100) - số phần tử trong mộtmột và số lượng phần tử trong p. Dòng thứ hai của trường hợp thử nghiệm chứa n số nguyên a1, a2, ... , an (1≤ai≤100). Dòng thứ ba của trường hợp thử nghiệm chứamm số nguyên p1, p2, ... , pm (1≤pi<n, tất cả pi là khác biệt) - tập hợp các vị trí được mô tả trong báo cáo vấn đề. Đầu ra Đối với mỗi trường hợp thử nghiệm, hãy in câu trả lời - "YES" (không có dấu ngoặc kép) nếu bạn có thể sắp xếp mảng ban đầu theo thứ tự không giảm (a1≤ a2≤ ⋯ ≤ an) chỉ sử dụng giao dịch hoán đổi. Nếu không, hãy in " NO ". Thí dụ đầu vào Sao chép
3. 6 3 2 3 2 1 1 2 4 2 4 1 2 3 3 2 5 1 1 2 3 4 5 1 4 2 2 1 4 3 1 3 4 2 4 3 2 1 1 3 5 2 2 1 2 3 3 1 4 đầu ra Sao chép YES NO YES YES NO YES Dố trên bảng 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 Một số số tự nhiên đã được viết trên bảng. Tổng các chữ số của nó không nhỏ hơn k . Nhưng bạn đã bị phân tâm một chút và ai đó đã thay đổi số này thành n , thay thế một số chữ số bằng số khác. Người ta biết rằng độ dài của số không thay đổi. Bạn phải tìm số chữ số tối thiểu trong đó hai số này có thể khác nhau. Đầu vào Dòng đầu tiên chứa số nguyên k ( 1  k  10 9 ). Dòng thứ hai chứa số nguyên n ( 1 ≤  n  <10 100000 ).
4. Không có số 0 đứng đầu trong n . Nó được đảm bảo rằng tình huống này là có thể. Đầu ra In số chữ số tối thiểu trong đó số ban đầu và n có thể khác nhau. Ví dụ đầu vào Sao chép 3 11 đầu ra Sao chép 1 đầu vào Sao chép 3 99 đầu ra Sao chép 0 Tin đồ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 Vova tự hứa với mình rằng anh sẽ không bao giờ chơi game trên máy tính ... Nhưng gần đây Firestorm - một công ty phát triển game nổi tiếng - đã xuất bản trò chơi mới nhất của họ, World of Farcraft, và nó đã trở nên thực sự phổ biến. Tất nhiên, Vova bắt đầu chơi nó. Bây giờ anh ta cố gắng để giải quyết một nhiệm vụ. Nhiệm vụ là đi đến một khu định cư có tên Overcity và lan truyền một tin đồn trong đó. Vova biết rằng có n nhân vật trong Overcity. Một số nhân vật là bạn bè của nhau và họ chia sẻ thông tin họ có được. Vova cũng biết rằng anh ta có thể mua chuộc từng nhân vật để anh ta hoặc cô ta bắt đầu lan truyền tin đồn; Nhân vật thứ i muốn c i gold để đổi lấy việc lan truyền tin đồn. Khi một nhân vật nghe tin đồn, anh ta nói với tất cả bạn bè của mình và họ bắt đầu truyền bá tin đồn cho bạn bè của họ (miễn phí), v.v. Nhiệm vụ kết thúc khi tất cả n nhân vật biết tin đồn. Số lượng vàng tối thiểu mà Vova cần phải bỏ ra để hoàn thành nhiệm vụ là bao nhiêu?
5. Hãy xem các ghi chú nếu bạn nghĩ rằng bạn chưa hiểu vấn đề hoàn toàn. Đầu vào Dòng đầu tiên chứa hai số nguyên n và m ( 1  n  10 5 , 0 ≤  m  ≤ 10 5 ) - số lượng ký tự trong Overcity và số lượng bạn bè. 9 Dòng thứ hai chứa n số nguyên c i ( 0 ≤  c i  ≤ 10 ) - số lượng ký tự vàng thứ i yêu cầu bắt đầu lan truyền tin đồn. Sau đó m dòng tiếp theo, mỗi dòng chứa một cặp số ( x i ,  y i ) đại diện cho các ký tự x i và y i là bạn bè ( 1 ≤  x i ,  y i  ≤  n , x i  ≠  y i ). Nó được đảm bảo rằng mỗi cặp được liệt kê nhiều nhất một lần. Đầu ra In một số - số lượng vàng Vova tối thiểu phải bỏ ra để hoàn thành nhiệm vụ. Ví dụ đầu vào Sao chép 5 2 2 5 3 4 8 1 4 4 5 đầu ra Sao chép 10 đầu vào Sao chép 10 0 1 2 3 4 5 6 7 8 9 10 đầu ra Sao chép 55 đầu vào Sao chép 10 5 1 6 2 7 3 8 4 9 5 10 1 2 3 4 5 6 7 8 9 10 đầu ra Sao chép 15