đề thi hsg nghệ an 2016-2017

Tổng quan bài thi:

Chú ý: Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là ngôn ngữ lập trình PASCAL hoặc ngôn ngữ lập trình C++

Hãy lập trình giải các bài toán sau:

Bài 1 (6.0 điểm):   PERFECT

Trong một buổi học toán, Bông được học khái niệm về số có tính chất đặc biệt: Đó là số hoàn hảo. Số A được gọi là số hoàn hảo nếu:

A = B1 + B2 + … + Bk trong đó Bi là ước của A và Bi < A với .

Ví dụ: Số 6 là số hoàn hảo vì nó có tổng các ước 1 + 2 + 3 = 6, số 8 không phải là số hoàn hảo vì 1 + 2 + 4 = 7, (7≠ 8).

Yêu cầu: Cho dãy số a1, a2, ..., an. Hãy giúp Bông đếm xem trong dãy có bao nhiêu số có tổng các chữ số là số hoàn hảo.

Dữ liệu vào: Từ file văn bản PERFECT.INP gồm:

- Dòng đầu tiên là số nguyên dương n (n ≤ 100).

- Dòng thứ 2 ghi n số nguyên  a1, a2, ..., an  (0 ≤ ai ≤ 109).     

Kết quả: Ghi ra file văn bản PERFECT.OUT gồm: Một số duy nhất là kết quả của bài toán.

Ví dụ:

Bài 2 (6.0 điểm):   PALIN

 Một xâu S được gọi là xâu đối xứng nếu S = S' với S' là xâu nhận được từ xâu S khi đọc từ phải qua trái.

 Ví dụ: Xâu 'aba' là xâu đối xứng, còn xâu 'abc' là xâu không đối xứng.

 Cho một xâu S gồm n kí tự (1 ≤ n ≤ 100)

Yêu cầu: Hãy tìm cách chia xâu 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: Từ file văn bản PALIN.INP gồm:

- Dòng đầu gồm một số nguyên n là độ dài của xâu S.

- Dòng thứ hai là nội dung xâu S.

Kết quả: Ghi ra file văn bản PALIN.OUT gồm:

 - Dòng đầu ghi một số nguyên k (số đoạn ít nhất tìm được).

 - K dòng sau, mỗi dòng ghi một số nguyên ti, với ti là vị trí kết thúc của đoạn thứ i.

Ví dụ:

Bài 3 (4.0 điểm):    SEQ

     Cho dãy số gồm n số nguyên a1, a2, …, an và 2 số nguyên không âm L, R (L ≤ R).

Yêu cầu: Đếm số cặp (i, j) thỏa mãn điều kiện: i ≤ j và L ≤ |ai+…+aj| ≤ R .

Dữ liệu vào: Từ file văn bản SEQ.INP gồm:

 - Dòng đầu tiên chứa 3 số nguyên n, L, R (n ≤ 105 ; 0 ≤ L ≤ R  ≤ 109)

 - Dòng thứ hai chứa n số nguyên dương a1, a2,…, an (ai ≤ 109)

Kết quả: Ghi ra file văn bản SEQ.OUT gồm một số nguyên duy nhất là số lượng cặp (i, j) đếm được.

 Ví dụ: 

Hạn chế:  - Có 50% số test ứng với 0 < n ≤ 103

  - Có 50% số test ứng với 103 < n ≤ 105

Bài 4 (4.0 điểm):  GN

Người ta đo độ giống nhau của hai xâu X, Y có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số i thỏa mãn X[i] = Y[i].

Ví dụ: X = 'avbc'; Y = 'avvv' có độ giống nhau bằng 2.

Cho một xâu S có độ dài n và một xâu T có độ dài m (m n), độ giống nhau giữa xâu S và xâu T là tổng số độ giống nhau giữa xâu T và mọi xâu con gồm các kí tự liên tiếp của S có độ dài m.

Yêu cầu: Cho hai xâu S và T. Tính độ giống nhau giữa xâu S và xâu T.

Dữ liệu vào: Từ file văn bản GN.INP như sau:

• Dòng đầu ghi xâu T.
• Dòng thứ 2 ghi xâu S.

Các kí tự trong hai xâu thuộc 'a' .. 'z' và có độ dài không quá 2.106 kí tự.

Kết quả: Ghi ra file văn bản GN.OUT gồm một số nguyên duy nhất là độ giống nhau giữa xâu S và xâu T.

Ví dụ:

Hạn chế:  - Có 25% số test ứng với 0 < n ≤ 102

  - Có 25% số test ứng với 102 < n ≤ 104

- Có 50% số test ứng với 104 < n ≤ 2.106

-------------------------(Hết) -------------------------

Họ và tên thí sinh: ......................................................... Số báo danh: ..........................