Tiêu đề khoa c2409 - giaoluu.docx ✅

http://www.chuyentin.pro/ KHÓA HỌC THUẬT TOÁN, ÔN THI HSG, TIN HỌC TRẺ 2024 - 2025 ĐỀ THI GIAO LƯU CUỐI KHÓA Thời gian: 90 phút Bài 1. Xâu đối xứng Xâu đối xứng là xâu khi đọc từ trái sang phải hay từ phải sang trái đều như nhau. Ví dụ: A = ‘abccba’, ‘defed’ là các xâu đối xứng. ‘aabb’, ‘abab’ không là xâu đối xứng Nhập xâu A. Kiểm tra xâu A có đối xứng không? Input: chứa xâu A dài không quá 255 ký tự, chỉ gồm các chữ cái viết thường Output: ghi “yes” nếu xâu A đối xứng, ngược lại ghi “no” Ví dụ: Input Output abccba yes aabb no Bài 2. Dãy số Cho dãy số gồm n số nguyên a[1], a[2], …, a[n]. Yêu cầu: tìm một số nguyên bằng tổng tất cả các số còn lại. Input:  Dòng đầu ghi số n (n  10 5 )  n dòng sau, dòng thứ i ghi số a[i] (-10 9  a[i]  10 9 ) Output: Ghi giá trị số tìm được, nếu không có ghi “N” Ví dụ: Input Output 4 0 5 8 3 8 3 1 2 4 N Bài 3. Chia bánh Trong dịp sinh nhật, Thảo mời Tuấn đến nhà chơi và cùng ăn bánh pizza. Chiếc bánh pizza Thảo là hình tròn, được chia làm tám mảnh, trên mỗi mảnh có đính các chiếc nấm xinh xắn với số lượng khác nhau. Thảo biết bạn rất thích ăn nấm, nên Thảo đố Tuấn chọn nhanh bốn mảnh liên tiếp nhau của chiếc bánh sao cho tổng số nấm trên bốn mảnh đó là lớn nhất. Trong bất chợt, Tuấn bối rối chưa nghĩ ra cách nhanh nhất để chọn bốn mảnh bánh liên tiếp theo yêu cầu của Thảo. Yêu cầu: Em hãy lập trình giúp Tuấn chọn nhanh bốn mảnh liên tiếp có tổng số nấm nhiều nhất. Input: một dòng chứa 8 số nguyên a 1 , a 2 , …, a 8 (0 < a i < 60) Output: một số nguyên là tổng số nấm lớn nhất trên bốn mảnh liên tiếp.
Ví dụ: Input Output 6 2 6 5 3 3 7 2 19 Bài 4. Dãy số A Cho dãy số như sau: 10, 3, 6, 10, 6, 12, 10, 9, 18, 19, 21, 15, 19, 24, 21, 19, 27, 27, 28, 30, . . . Số thứ i của dãy số bằng tổng các chữ số của số thứ i − 1 cộng thêm vị trí i rồi lấy hai số cuối của tổng này. Ví dụ số thứ 2 là bằng 1 + 0 + 2 = 3 hay số thứ 10 là bằng 1 + 8 + 10 = 19. Yêu cầu: Nhập số tự nhiên N. Hãy in ra số hạng thứ N của dãy số và tổng của N số hạng đầu tiên của dãy. Input: Nhập số tự nhiên N với 1 ≤ N ≤ 10 14 . Output  Xuất ra số hạng thứ N của dãy số.  Tổng của N số hạng đầu tiên của dãy số. Scoring  Subtask 1 (50% số điểm): N<10 5 .  Subtask 2 (50% số điểm): N<10 14 . Example Input Output Giải thích 10 19 103 20 30 334 Bài 5. Chia mảng Một dãy B có M phần tử được gọi là dãy cân bằng khi tồn tại vị trí x (1 <= x <= M) sao cho: B 1 + B 2 + … + B x = B x + B x+1 + … + B M = 0 Cho một dãy số A có N phần tử, đếm số lượng dãy con gồm các phần tử lien tiếp của dãy số A là dãy cân bằng. Input  Dòng đầu tiên gồm số nguyên dương N (N <= 10 5 ) là số phần tử của mảng A.  Dòng tiếp theo gồm N phần tử của mảng có giá trị tuyệt đối không vượt quá 10 9 . Output: ghi một số duy nhất là số lượng dãy con liên tiếp là dãy cân bằng. Ràng buộc:  50% test có N <= 500  30% test có N <= 5000  20% test không có ràng buộc gì thêm Ví dụ: Input Output Giải thích 5 2 Có 2 dãy con cân bằng:
1 -1 1 2 0 1, -1, 1 và 0 Bài 6. Đếm cặp N người đang đứng xếp hàng chờ mua vé vào buổi hòa nhạc. Mọi người đều phát chán khi phải chờ đợi, vì vậy họ nhìn quanh xem có ai quen hay không. Hai người A và B đứng trong hàng có thể nhìn thấy nhau nếu:  Người A và người B đang đứng cạnh nhau.  Giữa người A và người B, không có ai cao hơn hẳn một trong hai người. Hãy đếm xem có bao nhiêu cặp có thể nhìn thấy nhau trong hàng. Input  Dòng đầu tiên chứa số nguyên dương N, là số người đang đứng trong hàng. (N ≤ 5.10 5 )  Mỗi dòng trong N dòng tiếp theo chứa một số nguyên là chiều cao của một người tính bằng nanomet. (Tất cả mọi người đều thấp hơn 2 31  nanomet). Output: Một số nguyên duy nhất là kết quả cần tìm. Giới hạn: Trong 75% số test 1 ≤ N ≤ 5000 Ví dụ: Input Output Giải thích 7 2 4 1 2 2 5 1  10 Các cặp có thể nhìn thấy nhau là (1, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (4, 5), (4, 6), (5, 6), (6, 7). - Chúc các em làm bài tốt – * Lớp C. Thuật toán, ôn thi. Khai giảng khóa mới ngày 06/10/2024 http://www.chuyentin.pro/2023/09/khai-giang-lop-thuat-toan-on-thi-hoc.html * Tài liệu ôn thi học sinh giỏi, tin học trẻ, tuyển sinh 10 chuyên tin http://www.chuyentin.pro/p/luyen-giai-e.html