Đề thi học sinh giỏi lớp 11 THPT tỉnh Quảng Bình năm học 2012 - 2013 môn Tin học - Có đáp án

MÔN THI: TIN HỌC
Thời gian làm bài: 180 phút (không kể thời gian giao đề)
--------------------------------------------------------------------------------

Sử dụng ngôn ngữ lập trình Turbo Pascal để lập trình giải các bài toán sau:

Câu 1: (3,0 điểm) Tìm số TIMSO.PAS

Cho số nguyên dương X, khi đảo ngược trật tự các chữ số của X ta sẽ thu được một số nguyên dương Y, Y được gọi là số đảo ngược của X.

Ví dụ: X = 613 thì Y = 316 là số đảo ngược của X.

Số nguyên dương Y được gọi là số nguyên tố nếu nó chỉ có hai ước số là 1 và chính nó, số 1 không phải là số nguyên tố.

Cho hai số nguyên dương P và Q (1 ≤ P ≤ Q ≤ 2.10⁹; Q - P ≤ 10⁵).

Yêu cầu: Hãy tìm tất cả các số nguyên dương X nằm thỏa mãn P ≤ X ≤ Q và số đảo ngược của số X là số nguyên tố.

Dữ liệu vào: Cho trong file văn bản TIMSO.INP có cấu trúc như sau:

- Dòng 1: Ghi hai số nguyên dương P Q, hai 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 TIMSO.OUT trên nhiều dòng, mỗi dòng ghi một số nguyên X tìm dược.

Câu 2: (3,5 điểm) Tính tổng TONG.PAS

Cho hai số nguyên dương M và N, M có p chữ số và N có q chữ số.

Yêu cầu: Tính tổng của hai số M và N.

Dữ liệu vào: Cho trong file văn bản TONG.INP có cấu trúc như sau:

- Dòng 1: Ghi số nguyên dương p là số lượng chữ số của M (1 ≤ p ≤ 30000).

- Dòng 2: Ghi p chữ số của M theo thứ tự từ trái sang phải, các chữ số được ghi cách nhau ít nhất một dấu cách.

- Dòng 3: Ghi số nguyên dương q là số lượng chữ số của N (1 ≤ q ≤ 30000).

- Dòng 4: Ghi q chữ số của N theo thứ tự từ trái sang phải, các chữ 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 TONG.OUT theo cấu trúc như sau:

- Dòng 1: Ghi số nguyên dương k là số lượng chữ số của tổng tìm được.

- Dòng 2: Ghi k chữ số của tổng tìm được theo thứ tự từ trái sang phải, các chữ số được ghi cách nhau ít nhất một dấu cách.

Câu 3: (3,5 điểm) Dãy con chung dài nhất DAYCON.PAS

Cho dãy số nguyên A gồm N phần tử a1, a2, ..., aN và dãy số nguyên B gồm M phần tử b1, b2, ..., bM. Các phần tử trong một dãy số có giá trị khác nhau từng đôi một.

(1 ≤ ai, bj ≤ 2.10⁹; 1 ≤ N ≤ 100; 1 ≤ i ≤ N; 1 ≤ M ≤ 100; 1 ≤ j ≤ M).

Dãy C được gọi là dãy con của dãy A nếu dãy C nhận được từ dãy A bằng cách xóa đi một số phần tử và giữ nguyên thứ tự của các phần tử còn lại.

Nếu dãy C là dãy con của dãy A và cũng là dãy con của dãy B thì dãy C được gọi là dãy con chung của hai dãy A và B.

Yêu cầu: Hãy tìm dãy C là dãy con chung của hai dãy A và B sao cho số lượng phần tử của dãy C là lớn nhất.

Dữ liệu vào: Cho trong file văn bản DAYCON.INP có cấu trúc như sau:

- Dòng 1: Ghi số nguyên dương N là số lượng phần tử của dãy A.

- Dòng 2: Ghi N số nguyên là giá trị của các phần tử trong dãy A, các số được ghi cách nhau ít nhất một dấu cách.

- Dòng 3: Ghi số nguyên dương M là số lượng phần tử của dãy B.

- Dòng 4: Ghi M số nguyên là giá trị của các phần tử trong dãy B, 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 DAYCON.OUT theo cấu trúc như sau:

- Dòng 1: Ghi số nguyên dương K là số lượng phần tử của dãy C.

- Dòng 2: Ghi K số nguyên là giá trị của các phần tử trong dãy C, các số được ghi cách nhau một dấu cách.

- Dòng 3: Ghi K số nguyên dương lần lượt là chỉ số của các phần tử trong dãy A tương ứng với các giá trị của phần tử đó trong dãy C, các số được ghi cách nhau một dấu cách.

- Dòng 4: Ghi K số nguyên dương lần lượt là chỉ số của các phần tử trong dãy B tương ứng với các giá trị của phần tử đó trong dãy C, các số được ghi cách nhau một dấu cách.