Bài tập ôn tập Olympic Tin học

Bài 1 (4,0 điểm). Khởi động chương trình PASCAL, viết chương trình nhập số tự nhiên n sao cho 5 < n ≤100, nếu nhập sai yêu cầu nhập lại khi nào nhập đúng thì tính tổng sn: 1.2 2.3 3.4 n.(n 1) S ... n 3.4 4.5 5.6 (n 2)(n 3) Bài 2 (6,0 điểm). Viết chương trình trên ngơn ngữ lập trình PASCAL, nhập vào hai số tự nhiên x, y sao cho chương trình chỉ cho nhập các số tự nhiên x, y thỏa mãn 4 x < 53 và 59 < y 121. - In ra màn hình các số lẻ chia hết cho 3 trong khoảng từ x đến y và đếm cĩ bao nhiêu số như vậy? - In ra màn hình các số chính phương m sao cho x < m < y và đếm cĩ bao nhiêu số m? Bài 3 (4,0 điểm). Lập chương trình PASCAL thực hiện yêu cầu sau: Anh Việt đi chợ mua một mặt hàng cĩ giá trị là N đồng. Trong túi anh Việt cĩ nhiều tờ tiền với mệnh giá là 100 đồng, 200 đồng và 1000 đồng. Anh Việt cĩ thể cĩ nhiều cách trả tiền để mua mặt hàng đĩ (anh Việt chỉ dùng các tờ tiền mà anh cĩ sẵn. Anh khơng đưa thừa tiền cho người bán vì người bán khơng cĩ tiền trả lại). Yêu cầu: nhập vào từ bàn phím số N (N nguyên và 2<N<100 000); đưa ra màn hình tất cả các cách trả tiền của anh Việt thỏa mãn. (Mỗi cách trả tiền trên một dịng, nếu khơng cĩ cách trả tiền thì khơng cần thơng báo gì; ch­¬ng tr×nh kh«ng cÇn kiĨm tra d÷ liƯu vµo tõ bµn phÝm). Bài 4 ( 6,0 điểm). Khởi động chương trình PASCAL, viết chương trình nhập vào một dãy số nguyên n phần tử, n nhập từ bàn phím. - In ra màn hình dãy số vừa nhập xếp theo thứ tự tăng dần. - In ra màn hình các số nguyên tố trong dãy số vừa nhập và đếm xem đã nhập vào bao nhiêu số nguyên tố. Bài 2: (7 điểm) TỔNG CÁC SỐ FIBONACI Dãy Fibonaci là dãy gồm các số: 1, 1, 2, 3, 5, 8, .... được xác định bởi cơng thức sau: F1=1, F2=1, Fi=Fi-1+Fi-2 với i>2. Em hãy biểu diễn một số tự nhiên N thành tổng của ít nhất các số Fibonaci khác nhau. Dữ liệu vào: cho file FIBO.INP chứa số N (N ≤ 2000000000) Dữ liệu ra: ghi ra file FIBO.OUT biểu diễn số N thành tổng của ít nhất các số Fibonaci khác nhau. Ví dụ: FIBO.INP FIBO.OUT 129 129 = 89 + 34 + 5 + 1 Hoặc FIBO.INP FIBO.OUT 8 8 = 8 Bài 3: (7 điểm) CHỌN PHẦN THƯỞNG Trong kỳ thi học sinh giỏi mơn Tin học, em là người đạt giải đặc biệt. Ban tổ chức cho phép em chọn các phần thưởng cho mình. Các phần thưởng xếp thành một dãy được đánh số từ 1 đến N (0 ≤ N ≤ 10000), phần thưởng thứ i cĩ giá trị là ai (1 ≤ ai ≤ 100). Em được phép chọn các phần thưởng cho mình theo nguyên tắc khơng chọn 3 phần thưởng liên tiếp nhau trong dãy. Viết chương trình để máy tính hướng dẫn em chọn các phần thưởng sao cho tổng giá trị của các phần thưởng nhận được là lớn nhất. Dữ liệu vào: cho file PTHUONG.INP gồm các dịng: - Dịng đầu tiên là số phần thưởng N - N dịng tiếp theo lần lượt là giá trị của các phần thưởng. Dữ liệu ra: ghi ra file PTHUONG.OUT gồm các dịng: - Dịng đầu tiên ghi tổng giá trị lớn nhất của các phần thưởng đã chọn - Dịng tiếp theo ghi vị trí của các phần thưởng đã chọn theo thứ tự tăng dần. Ví dụ: PTHUONG.INP PTHUONG.OUT 5 23 6 1 2 4 5 9 1 3 5 Hoặc PTHUONG.INP PTHUONG.OUT 7 32 6 1 2 4 6 7 9 1 3 5 10 4 Câu 1: (3,0 điểm) Phần thưởng PT.PAS Trong cuộc thi giải tốn qua mạng internet mỗi học sinh đều cĩ số điểm tích lũy riêng của mình. Số điểm tích lũy của mỗi học sinh là một số nguyên dương K (0 < K ≤ 2 109). Đội tuyển của trường THCS Tài Năng cĩ N học sinh tham gia dự thi (2 ≤ N ≤ 100). Tại buổi gặp mặt trước kỳ thi cấp tỉnh, thầy hiệu trưởng quyết định thưởng cho các học sinh trong đội tuyển Q triệu đồng, biết rằng điểm tích lũy của mỗi học sinh đều chia hết cho Q. Yêu cầu: Hãy tìm số nguyên dương Q lớn nhất. Dữ liệu vào: Cho trong file văn bản PT.INP cĩ cấu trúc như sau: - Dịng 1: Ghi số nguyên dương N là số lượng học sinh. - Dịng 2: Ghi N số nguyên dương lần lượt là điểm tích lũy của N học sinh, các số được ghi cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra file văn bản PT.OUT theo cấu trúc như sau: - Dịng 1: Ghi số nguyên dương Q tìm được. Ví dụ: PT.INP PT.OUT 5 3 15 24 45 36 27 Thời gian thực hiện chương trình khơng quá 1 giây cho mỗi bộ dữ liệu vào. Câu 2: (3,5 điểm) Mật khẩu MK.PAS Cu Tí thường xuyên tham gia thi lập trình trên mạng. Vì đạt được thành tích cao nên Tí được gửi tặng một phần mềm diệt virus. Nhà sản xuất phần mềm cung cấp cho Tí một mã số là một số nguyên dương N cĩ khơng quá 255 chữ số. Để cài đặt được phần mềm, Tí phải nhập vào mật khẩu của phần mềm. Mật khẩu là một số nguyên dương M được tạo ra bằng cách tính tổng giá trị các chữ số của N. Yêu cầu: Hãy tìm số nguyên dương M. Dữ liệu vào: Cho trong file văn bản MK.INP cĩ cấu trúc như sau: - Dịng 1: Ghi số nguyên dương N. Dữ liệu ra: Ghi ra file văn bản MK.OUT theo cấu trúc như sau: - Dịng 1: Ghi số nguyên dương M tìm được. Ví dụ: MK.INP MK.OUT 84915388247 59 Câu 3: (3,5 điểm) Tần suất TS.PAS Cho tập hợp S cĩ N phần tử nguyên dương {s1, s2, , sN}. (1 ≤ N ≤ 32000; 0 < si ≤ 32000; 1 ≤ i ≤ N) Yêu cầu: Hãy liệt kê các phần tử trong S cĩ số lần xuất hiện lớn hơn một lần. Dữ liệu vào: Cho trong file văn bản TS.INP cĩ cấu trúc như sau: - Dịng 1: Ghi số nguyên dương N. - Dịng 2: Ghi N số nguyên dương là giá trị các phần tử của tập hợp S, các số được ghi cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra file văn bản TS.OUT trên nhiều dịng, dịng thứ i ghi 2 số si di, hai số cách nhau một dấu cách. Trong đĩ si là phần tử xuất hiện trong S lớn hơn một lần và di tương ứng là số lần si xuất hiện. Ví dụ: TS.INP TS.OUT 7 3 2 2 5 5 3 5 3 9 5 3 Tạo Folder mang tên là số báo danh của thí sinh và lưu theo đường dẫn: D:\SBD_K9. Các file trong bài được đặt tên lần lượt là BAI1.PAS, BAI2.PAS, BAI3.PAS và lưu vào Folder vừa tạo. Bài 1 (3 điểm): Hai số tự nhiên n, m được gọi là nguyên tố tương đương nếu chúng cĩ chung các ước số nguyên tố. Hãy viết chương trình nhập vào hai số n, m và kiểm tra chúng cĩ là nguyên tố tương đương với nhau hay khơng. Ví dụ: số 75 và số 15 là nguyên tố tương đương vì chúng cĩ cùng các ước số nguyên tố là 3 và 5. Bài 2 (3 điểm): Cho hệ phương trình bậc nhất hai ẩn: ax by c (I) a ' x b ' y c ' Hãy viết chương trình giải hệ phương trình trên, đồng thời xác định vị trí tương đối của hai đường thẳng d: ax+by=c và d’=a’x+b’y =c’ đã tạo nên hệ phương trình (I). Bài 3 (4 điểm): Cho hai xâu X, Y chứa các kí tự số từ 0 đến 9 và được biểu diễn như sau: X = x1, x2, x3 xn ; Y= y1, y2, y3 ym (n,m 250 ). Hãy viết chương trình tạo ra xâu ST thoả mãn các điều kiện sau: - Gồm các kí tự số vừa cĩ mặt ở xâu X, vừa cĩ mặt ở xâu Y; - Các kí tự số trong xâu ST chỉ xuất hiện duy nhất một lần; - Giá trị xâu ST nhận được là một số đạt giá trị lớn nhất. Dữ liệu vào cho bởi file INPUT.INP chứa giá trị xâu X và xâu Y, mỗi xâu nằm trên một dịng. Dữ liệu ra chứa ở file OUTPUT.OUT là số lớn nhất nhận được. Ví dụ: Xâu X= ‘19012304’; xâu Y= ‘034012’, kết quả là 43210.