Đề 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

Vndoc.com xin gửi đến các bạn: Đề 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.

Đề thi học sinh giỏi môn Tin học:

SỞ GIÁO DỤC VÀ ĐÀO TẠO BẠC LIÊU (Đề thi chính thức)

KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 VÒNG TỈNH NĂM HỌC: 2010 - 2011

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).