Title on toan quoc 2023 - bang a - de bai.docx ✅

1. đề 4 Bài 1. NENSO Nén số Phép nén số là một trong những kỹ thuật bảo vệ dữ liệu. Phép nén một số nguyên là tính tổng các chữ số của nó, sau một số lần sử dụng phép nén thì số còn lại chỉ có một chữ số và không nén được nữa, khi đó ta gọi số đó là số nén tối giản. Ví dụ số 284, sau phép nén lần thứ nhất ta được 2 + 8 + 4 = 14, sau phép nén lần thứ hai ta được 1 + 4 = 5. Khi đó số nén tối giản của 284 là 5. Yêu cầu: Cho một số nguyên N (0 < N ≤ 10 9 ). Hãy tìm số nén tối giản của N. Input: ghi số nguyên dương N. Output: ghi một số nguyên duy nhất là số nén tối giản của N. Input Output 121 4 57871 1 Bài 2. TROCHOI Trò chơi Trong dịp liên hoan cuối năm, lớp của Khôi tổ chức trò chơi. Có hai đội chơi, đội 1 có mã số là một số nguyên dương x, đội 2 có mã số là một số nguyên dương y. Ban tổ chức trò chơi đưa ra hai số nguyên dương m, n (m ≤ n). Nhiệm vụ của mỗi đội là tìm số lượng số thuộc đoạn [m; n] cùng chia hết cho mã số của cả hai đội. Ban tổ chức trò chơi muốn có đáp án chính xác của nhiệm vụ trên để kiểm tra kết quả của hai đội. Yêu cầu: tìm số lượng số thuộc đoạn [m; n] cùng chia hết cho x, y. Input: chứa bốn số nguyên dương m, n, x, y (2 ≤ m, n ≤ 10 12 ; 2 ≤ x, y ≤ 10 9 ). Output: ghi số lượng số thỏa mãn yêu cầu bài toán trên. Input Output 20 100 5 6 3 Giới hạn:  60% test có 1 ≤ n – m ≤ 10 8 .  40% test có 10 8 < n – m ≤ 10 12 . Bài 3. PNT Số phản nguyên tố Số nguyên dương N gọi là số phản nguyên tố nếu bản thân N và các số tạo thành từ việc xóa đi những chứ số bên phải của N đều không phải là số nguyên tố. Ví dụ: - Số 9426 là số phản nguyên tố vì 9426; 942; 94; 9 đều không phải là số nguyên tố. - Số 2752 không phải là số phản nguyên tố vì 3752; 375 không phải là số nguyên tố nhưng 37 và 3 là số nguyên tố. Yêu cầu: Kiểm tra các số nguyên dương a, b, c có phải là số phẩn nguyên tố hay không? Input: gồm ba số nguyên a, b, c (1 ≤ a, b, c ≤ 10 9 ), mỗi số cách nhau một khoẳng trắng. Output: gồm 3 dòng có cấu trúc như sau:  Dòng 1: ghi 1 nếu a là số phản nguyên tố, ghi 0 nếu a không là số phản nguyên tố.  Dòng 2: ghi 1 nếu b là số phản nguyên tố, ghi 0 nếu b không là số phản nguyên tố.  Dòng 3: ghi 1 nếu c là số phản nguyên tố, ghi 0 nếu c không là số phản nguyên tố.
Input Output 33 292 46 0 0 1 174 68 290 0 1 0 Giới hạn: 40% test có 1 ≤ a, b, c ≤ 100; 40% test có 10 3 < a, b, c < 10 6 ; 20 % test có 10 7 < a, b, c ≤ 10 9 . Bài 4. FLAG Trò chơi cắm cờ Ban chấp hành Đoàn trường PTNK dự định tổ chức một trò chơi vận động và có tính chất chiến thuật dành riềng cho các học sinh lớp chuyên Tin trong dịp đón học sinh mới năm 2014-2015. Để tổ chức trò chơi các anh chị trong Ban chấp hành đoàn trường chuẩn bị một số khu đất hình vuông rời nhau, bốn góc của mỗi khu đất có khoan một lỗ nhỏ để cắm cờ. Tại một số góc cắm sẵn một lá cờ và mỗi khu đất có ít nhất một lá cờ được cắm. Người chơi được phép rút một lá cờ bất kì cắm vào một góc trống của khu đất nào đó, Mỗi lần thực hiện động tác này được tính là một lượt chơi. Nhiệm vụ của bạn là tìm một phương án chơi sao cho số khu đất có đủ bốn lá cờ ở bốn góc là nhiều nhất đồng thời số lượt chơi là ít nhất. Yêu cầu: Với một trạng thái trò chơi cho trước, hãy xác định số lượt chơi ít nhất để nhận được nhiều nhất các khu đất có đủ 4 lá cờ Input: ghi 3 số a 1 , a 2 , a 3 với a 1 là số khu đất chỉ cắm một lá cờ, a 2 là số khu đất chỉ cắm đúng 2 lá cờ và a 3 là số khu đất cắm đúng 3 lá cờ. (0 ≤ a 1 , a 2 , a 3 ≤ 10 9 ) Output: ghi số lượt chơi ít nhất tìm được Giới hạn: 15/20 test có 0 ≤ a 1 , a 2 , a 3 ≤ 10 5 . Ví dụ: Input Output Giải thích: 4 2 3 5 bạn phải cần ít nhất 5 lượt chơi để hình thành được 4 khu đất nà 4 góc đều có cờ. Một trong các phương án đó như sau: Rút 3 lá cờ ở 3 khu đất chỉ có 1 lá cờ cắm vào 3 khu đất đã có sẵn 3 lá cờ để được 3 khu đất đủ 4 lá cờ. Rút 2 lá cờ ở khu đất có 2 lá cờ cắm vào khu đất còn lại có 2 lá cờ thu được khu đát thứ 4 có 4 lá cờ. tổng cộng cần 5 lượt chơi. 2. đề 5 Bài 5. STICKERS Stickers Bài tâp thủ công của Nam là dùng các sticker để tạo thành một dãy số S theo một nghĩa nào đó. Mỗi sticker là 1 chữ số có giá trị từ 0 đến 9. Có 10 loại sticker tương ứng như hình bên dưới.
Để tiết kiệm, Nam không mua mới mà thu nhặt các sticker từ anh trai để lại. Trong quá trình thu nhặt, Nam nhận thấy cặp (2, 5) có thể thay thế cho nhau bằng cách lật ngược lại, cặp (6, 9) cũng có tính chất tương tự. Các sticker thu nhặt từ anh trai được mô tả bởi dãy số T. Do giáo viên yêu cầu tạo thật nhiều dãy số S nên Nam muốn biết trước với số lượng sticker thu nhặt được thì có thể tạo tối đa bao nhiêu dãy số S. Yêu cầu: cho 2 dãy số T và S gồm không quá 10 5 các chữ số có giá trị từ 0 đến 9. Tính số lượng dãy số S có thể tạo được nhiều nhất bằng cách sử dụng các chữ số từ dãy số T. Input:  Dòng đầu tiên chứa dãy số chữ T  Dòng thứ hai chứa dãy số chữ S. Output: Ghi số lượng dãy số S tạo được nhiều nhất. Input Output Giải thích 4444223 445 2 668888 899 1 Bài 6. CHINHPHUONG Số chính phương Một số nguyên dương được gọi là số chính phương nếu căn bậc hai của nó là một số nguyên dương. Hay nói cách khác, bình phương của một số nguyên dương được gọi là một số chính phương. Ví du: 9 là số chính phương vì (hay 3 2 = 9, nên 9 là số chính phương) nhưng 10 thì không phải là số chính phương vì . Yêu cầu: Hãy cho biết từ X tới Y (kể cả X và Y) có tất cả bao nhiêu số chính phương? Input: ghi hai số nguyên ương X và Y được ghi trên một dòng và phân cách nhau bởi dấu cách (1 ≤ X ≤ Y ≤ 10 9 ) Output: ghi số lượng các số chính phương tìm được. Input Output Giải thích 2 10 2 Từ 2 đến 10 có hai số chính phương là 4 và 9 Giới hạn: 80% test có X ≤ Y ≤ 10 6 ; 20% test có X ≤ Y ≤ 10 9 . Bài 7. NUMBER1 Chữ số thứ K Tí là học sinh rất thông minh. Trong giờ toán, Tí luôn hoàn thành rất nhanh tất cả các bài tập được giao, sau đó chọc ngoáy các bạn. Để tránh cho Tí làm ảnh hưởng các bạn, cô giáo thường giao thêm cho Tí bài tập triêng. Bài tập hôm nay cô giáo ra là: Tìm chữ số thứ K của một số tự nhiên rất lớn tính từ trái sang phải. Số tự nhiên rất lớn này được tạo ra bằng cách ghép các số tự nhiên liên tiếp 1, 2, 3, 4, 5, … lại với nhau. Ví dụ: một số tự nhiên rất lớn được tạo ra theo cách trên 1234567891011121314151617181920212223242526272829303132333435… Với K = 10, chữ số thứ 10 của số tự nhiên trên là 1 Với mỗi số K cho trước, Tí đều tìm được chữ số thứ K của số tự nhiên rất lớn trên, nhưng tính toán rất lâu mới được kết quả. Yêu cầu: Em hãy lập trình giúp Tí tìm nhanh chữ số thứ K. Input: một dòng chứa số nguyên dương K (K < 10 9 )