Đề thi học sinh giỏi lớp 12 THPT tỉnh Bạc Liêu môn Tin học (Năm học 2010 – 2011) – Có đáp án Sở GD&ĐT Bạc Liêu

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

Câu 1: (6 điểm)

Một xâu S1 được gọi là xâu đối xứng nếu S1’ = S1 với S1’ là xâu nhận được từ xâu S1 khi đọc từ phải qua trái. Ví dụ: “aba” là xâu đối xứng, “abc” là xâu không đối xứng.

Cho một xâu kí tự S gồm N kí tự (1 <= N <= 100), hãy tìm cách chia S thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng.

Dữ liệu vào: PALIN.INP
+ Dòng đầu gồm 1 số nguyên: N
+ Dòng thứ hai ghi xâu S

Dữ liệu ra: PALIN.OUT
+ Dòng đầu ghi 1 số nguyên: K (số đoạn ít nhất tìm được)
+ K-1 dòng sau, mỗi dòng ghi 1 số nguyên Ti, với Ti là vị trí kết thúc của đoạn thứ i (đoạn thứ K kết thúc tại N).

Câu 2: (7 điểm) Dãy con Fibonacci

Cho một dãy các số nguyên a1, . . . , an (n <=100). Hãy tìm trong dãy a một dãy Fibonacci dài nhất.

– Dãy Fibonacci là dãy có tính chất sau:

F₀ = F₁ = 1
F_n = F_n-1 + F_n-2

Input: Daycon.inp

– Dòng đầu chứa số N (N<=100)
– Dòng 2 chứa n số nguyên (a_i <= 100000)

Output: Daycon.out

– Chứa duy nhất một dòng là dãy Fibonacci tìm được

Câu 3: (7 điểm) Dãy con cấp số cộng

Cho dãy gồm N số tự nhiên ( 2 ≤ N ≤ 1000). Hãy tìm trong dãy con dài nhất tạo thành cấp số cộng có công sai d.

Input: DAYCON.INP

– Dòng đầu tiên là số N, d

– Các dòng tiếp theo là N số trong dãy, các số cách nhau một dấu cách

Output: DAYCON.OUT

– Dòng đầu ghi số lượng phần tử trong dãy con tìm được.

– Dòng thứ 2 ghi các phần tử trong dãy con đã tìm được (sắp xếp tăng).

Download tài liệu để xem thêm chi tiết