SKKN Giúp học sinh lựa chọn và cài đặt chương trình tối ưu khi giải một số dạng bài tập về dãy con nhằm nâng cao chất lượng học sinh giỏi môn tin học ở trường THPT

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ
TRƯỜNG THPT ĐẶNG THAI MAI
SÁNG KIẾN KINH NGHIỆM
ĐỀ TÀI
GIÚP HỌC SINH LỰA CHỌN VÀ CÀI ĐẶT CHƯƠNG TRÌNH 
TỐI ƯU KHI GIẢI MỘT SỐ DẠNG BÀI TẬP VỀ DÃY CON NHẰM NÂNG CAO CHẤT LƯỢNG HỌC SINH GIỎI 
MÔN TIN HỌC Ở TRƯỜNG THPT
Người thực hiện: Hoàng Thị Mai
Chức vụ: Giáo viên
SKKN thuộc lĩnh vực: Tin học
THANH HOÁ NĂM 2016
1. MỞ ĐẦU
1.1. Lý do chọn đề tài
Cùng với công tác bồi dưỡng học sinh thi Đại học – Cao đẳng thì công tác bồi dưỡng học sinh giỏi là một công tác mũi nhọn của nhà trường. Thông qua kết quả học sinh giỏi phần nào khẳng định được vị thế của trường so với các trường bạn trong huyện nói riêng và trong tỉnh nói chung. 
Tuy nhiên chất lượng học sinh giỏi môn Tin học của trường từ năm học 2013 – 2014 trở về trước còn thấp, chưa có học sinh nào đạt được giải học sinh giỏi môn Tin học cấp tỉnh, mặc dù một số năm vẫn có học sinh tham gia thi. Chất lượng học sinh giỏi môn Tin học còn thấp như vậy, phần vì năng lực học sinh (do chất lượng đầu vào của học sinh thấp) phần vì phương pháp giảng dạy của giáo viên chưa phù hợp. Do đó việc nâng cao chất lượng học sinh giỏi môn Tin học là cần thiết và cấp bách nhằm góp thêm vào thành tích chung của nhà trường.
Mặt khác, trong quá trình dạy bồi dưỡng học sinh giỏi tôi gặp rất nhiều bài toán về dãy con. Đây là dạng bài tập khó thường xuất hiện trong các đề thi học sinh giỏi môn Tin học. Rất nhiều học sinh khi gặp dạng bài tập này bị mất điểm hoặc điểm không cao. Nguyên nhân có thể nhiều nhưng trong đó có hai nguyên nhân cơ bản là: chương trình cho kết quả output sai hoặc chương trình cho kết quả output đúng với các bộ input có dữ liệu nhỏ nhưng với những bộ input có dữ liệu lớn thì chương trình chạy quá thời gian quy định là 1giây/1test (mặc dù kết quả output vẫn đúng). 
Trên thực tế đã có một số tài liệu đề cập đến các bài tập về dãy con, nhưng các tài liệu này mới chỉ đưa ra thuật toán và chương trình giải một số bài tập cụ thể làm ví dụ minh họa cho một kỹ thuật lập trình nào đó khi nghiên cứu mà chưa khái quát dạng, chưa phân tích sâu cách tư duy, cách lựa chọn và cài đặt chương trình tối ưu. Các chương trình mà một số tài liệu đưa ra rất khó hiểu và phức tạp không phù hợp năng lực học sinh Trường THPT Đặng Thai Mai. Khi nghiên cứu các tài liệu này, không chỉ học sinh mà ngay cả giáo viên còn lúng túng, mơ hồ, áp dụng một cách máy móc mà chưa biết nên chọn cách làm nào? Cách làm nào tối ưu hơn?
Với mong muốn giúp học sinh giải quyết tốt hơn các bài tập về dãy con và hiểu biết sâu sắc hơn cách giải các bài tập này, tôi đã dày công nghiên cứu, phân dạng các bài tập dãy con, trăn trở để tìm ra nhiều cách làm khác nhau, đánh giá độ phức tạp, đo thời gian thực hiện chương trình, để so sánh tìm ra chương trình tối ưu nhất và dễ hiểu nhất trong các chương trình đã đưa ra. Từ đó nâng cao chất lượng bồi dưỡng học sinh giỏi môn Tin học.
Từ những lý do trên tôi đã mạnh dạn trình bày sáng kiến kinh nghiệm: “Giúp học sinh lựa chọn và cài đặt chương trình tối ưu khi giải một số dạng bài tập về dãy con nhằm nâng cao chất lượng học sinh giỏi môn Tin học ở trường THPT”.
1.2. Mục đích nghiên cứu
Đề tài này nghiên cứu nhằm giúp học sinh giải quyết tốt các bài toán về dãy con từ đó đổi mới cách tư duy lập trình, để khi đứng trước một bài toán cần giải quyết ngoài việc tìm ra thuật toán để cài đặt chương trình thì học sinh sẽ biết cách so sánh, đánh giá hiệu quả của thời gian thực hiện chương trình (hay còn gọi là độ phức tạp của thuật toán) và lựa chọn được chương trình phù hợp nhằm nâng cao chất lượng học sinh giỏi.
1.3. Đối tượng nghiên cứu
Sáng kiến kinh nghiệm có đối tượng nghiên cứu là các bài toán về dãy con, được nghiên cứu ở nhiều cách làm, xét trên nhiều phương diện như: độ phức tạp, kết quả output, thời gian thực hiện chương trình.
1.4. Phương pháp nghiên cứu
Để trình bày sáng kiến kinh nghiệm này, tôi đã sử dụng phối kết hợp nhiều phương pháp như: nghiên cứu tài liệu, thuyết trình, quan sát, điều tra cơ bản, thực nghiệm so sánh, phân tích kết quả thực nghiệm,  phù hợp với môn học thuộc lĩnh vực Tin học.
2. NỘI DUNG NGHIÊN CỨU
2.1. Cơ sở lý luận
Nghị quyết hội nghị Trung ương VIII khóa XI chỉ đạo: “Giáo dục và đạo tạo là Quốc sách hàng đầu, là sự nghiệp của Đảng và Nhà nước và của toàn dân. Đầu tư cho giáo dục là đầu tư phát triển, được ưu tiên đi trước cho các chương trình, kế hoạch phát triển KT-XH; phát triển giáo dục và đạo tạo là nâng cao dân trí, đạo tạo nhân lực, bồi dưỡng nhân tài. Chuyển mạnh quá trình giáo dục từ chủ yếu trang bị kiến thức sang phát triển toàn diện năng lực và phẩm chất người học. Học đi đôi với hành, lý luận gắn với thực tiễn, giáo dục nhà trường kết hợp với giáo dục gia đình và giáo dục xã hội”.
Nghị quyết hội nghị Trung ương VIII khóa XI đề ra mục tiêu: “Đối với giáo dục phổ thông tập trung phát triển trí tuệ, thể chất, hình thành phẩm chất, năng lực công dân, phát hiện và bồi dưỡng năng khiếu, định hướng nghề nghiệp cho học sinh. Nâng cao chất lượng giáo dục toàn diện, chú trọng giáo dục lý tưởng truyền thống đạo đức, lối sống, ngoại ngữ, tin học, năng lực và kỹ năng thực hành, vận dụng kiến thức vào thực tiễn, phát triển khả năng sáng tạo và tự học, khuyến khích học tập suốt đời, hoàn thành đào tạo giáo dục phổ thông giai đoạn sau 2015”.
Căn cứ vào mục tiêu của môn Tin học, là phải cung cấp những tri thức cơ bản, làm nền tảng để học sinh có thể tiếp tục đi sâu vào tìm hiểu và xây dựng khoa học Tin học hoặc tiếp thu những tri thức của các lĩnh vực kĩ thuật công nghệ tiên tiến, nhất là các lĩnh vực của công nghệ thông tin. 
Môn Tin học, cũng như mọi môn học khác, căn cứ vào mục tiêu trên để xác định ra nhiệm vụ cụ thể của môn học, tổ chức hoạt động đào tạo góp phần thực hiện mục tiêu giáo dục mà Đảng và nhà nước đề ra.
Nếu học sinh thực hiện tốt việc lựa chọn và cài đặt chương trình tối ưu khi giải các bài tập về dãy con nói riêng và các bài tập lập trình nói chung thì chất lượng học sinh giỏi sẽ được nâng cao. 
2.2. Thực trạng
2.2.1. Giới thiệu khái quát về trường
Trường THPT Đặng Thai Mai được thành lập ngày: 20/08/2001, theo quyết định số: 2109/QĐ-UB của Chủ tịch UBND Tỉnh Thanh Hoá. Trường nằm ngay trên đường quốc lộ 1A, thuộc km 12 từ thành phố Thanh Hóa xuống phía Nam, thuộc địa bàn xã Quảng Bình, huyện Quảng Xương, tỉnh Thanh Hóa, nơi đa số phụ huynh học sinh làm nông nghiệp, điều kiện kinh tế còn gặp nhiều khó khăn. Các em học sinh ít có điều kiện tiếp xúc với máy tính ở nhà. Ban đầu trường hoạt động theo mô hình trường bán công, chất lượng đầu vào của học sinh thấp, chủ yếu là học sinh trung bình, yếu. Mặc dù ngày 31 tháng 5 năm 2010 chủ tịch tỉnh Thanh hóa có quyết định chuyển đổi trường THPT Đặng Thai Mai sang hình thức công lập nhưng chất lượng đầu vào của học sinh vẫn còn thấp so với các trường trong huyện.
Trường hiện có 25 lớp, đã trang bị 2 phòng học thực hành Tin học, có lắp đặt máy chiếu, đảm bảo cơ sở vật chất đầy đủ cho việc học môn Tin học của nhà trường.
Trong những năm gần đây nhà trường cũng đã có nhiều thành tích nổi bật như: Năm học 2013 – 2014 được UBND Tỉnh Thanh Hóa tặng bằng khen - QĐ số 3645/QĐ- UBND, ngày 30/10/2014. Năm học 2014 - 2015 đón cờ thi đua của UBND Tỉnh về đơn vị dẫn đầu, QĐ số 3335/QĐ UBND tỉnh Thanh Hoá ngày 1/9/2015,...
Môn Tin học là môn học đặc thù có nhiều kiến thức khó như lập trình pascal ở lớp 11 (đây là kiến thức thi học sinh giỏi tỉnh môn Tin học) nhưng thường bị xem nhẹ, bị xem là “môn phụ”. Học sinh – phụ huynh chưa mặn mà, chưa quan tâm đúng mực tới môn học nên việc lựa chọn và bồi dưỡng học sinh giỏi là vô cùng khó khăn.
2.2.2 Thực trạng trước khi nghiên cứu
Năm 2013 – 2014 tôi có phối hợp cùng một giáo viên khác tham gia công tác bồi dưỡng học sinh giỏi tỉnh môn Tin học, cũng là năm đầu tiên tôi tham gia công tác bồi dưỡng học sinh giỏi, việc dạy đội tuyển của tôi chủ yếu dựa trên những kiến thức cơ bản của sách giáo khoa, chưa chú trọng nhiều đến cải tiến chương trình tối ưu hơn để chương trình chạy nhanh hơn và chủ yếu là định hướng cho học sinh tìm ra được thuật toán (cách làm) để chương trình cho ra được kết quả mà thôi. 
Chính vì vậy khi giải quyết các bài toán về dãy con nói riêng và các bài tập lập trình pascal khác nói chung, học sinh và ngay cả giáo viên thường chỉ làm việc với các bộ input có dữ liệu nhỏ dễ nhìn thấy kết quả output và thường không xét đến trường hợp input đặc biệt hay các input có dữ liệu lớn. Dẫn đến bị mất điểm trong bài thi học sinh giỏi.
Đối với thi học sinh giỏi, dù kết quả output của 2 thí sinh có giống hệt nhau với cùng một bộ input, nhưng việc chênh lệch về thời gian quyết định thí sinh có thể chiến thắng hay thất bại (yêu cầu thời gian xử lí chương trình không quá 1 giây/1 test).
Trong các kì thi học sinh giỏi gần đây, với cấu trúc đề 3 câu tương ứng với số điểm 6, 7, 7, trong đó chỉ có không quá 50% các dữ liệu input là nhỏ vừa tầm thì việc thí sinh dù có làm hết cả 3 câu trong đề thì nguy cơ thất bại vẫn rất cao.
Bảng điểm các lần thi khảo sát chất lượng học sinh giỏi về chuyên đề dãy con (do tôi tự tổ chức) năm học 2013 – 2014 khi chưa thực hiện đề tài: 
Họ tên
Điểm lần 1
Điểm lần 2
Điểm lần 3
Điểm lần 4
Phạm Hà Uyên
2/10
3/10
2/10
3/10
Lê Đình Miền
3/10
3/10
4/10
4/10
Do đó kết quả học sinh giỏi năm 2013- 2014 chưa được như mong muốn, có 2 em học sinh tham gia thi học sinh giỏi Tin của trường thất bại không có em nào đạt giải (mặc dù khi đi thi về các em rất phấn khởi vì nghỉ mình làm bài tốt, đúng vậy bài làm các em đều cho kết quả đúng trong khoảng thời gian cho phép nhỏ hơn 1 giây nhưng với bộ input có dữ liệu nhỏ còn bộ input có dữ liệu lớn thì bài làm vẫn cho kết quả đúng nhưng thời gian chạy chương trình quá 1giây, nghĩa là bộ test có dữ liệu lớn các em bị mất điểm).
Vấn đề đặt ra, là làm thế nào để lấy được điểm với các bộ input có dữ liệu lớn. Muốn vậy cần phải lựa chọn và cài đặt được chương trình hiệu quả (tối ưu). Chương trình hiệu quả là chương trình giải quyết được những bộ input có dữ liệu lớn, chính xác, dung lượng sử dụng bộ nhớ nhỏ, thời gian thực chương trình ngắn,... Nhưng trong phạm vi sáng kiến kinh nghiệm của mình, tôi chỉ nghiên cứu về tiêu chí thời gian thực hiện chương trình để lựa chọn chương trình tối ưu, đây là tiêu chí quan trọng nhất và được người ta quan tâm nhiều. Ngoài ra, tôi cũng ưu tiên lựa chọn chương trình ngắn gọn, dễ hiểu phù hợp với năng lực học sinh trường tôi.
Thời gian thực hiện chương trình không chỉ phụ thuộc vào thuật toán mà còn phụ thuộc vào cấu hình máy tính, kĩ xảo người lập trình, kích thước và tính chất của dữ liệu vào,...Để cụ thể và tường minh hơn tôi có sử dụng phần mềm Themis để đo thời gian thực hiện của các chương trình với các bộ test cụ thể (có file test kèm theo). Các kết quả được tôi thử nghiệm trên máy tính laptop ASUS, Ram 2GB, Processor AMDE-450 APU 1.65HZ. 
2.3. Các biện pháp sử dụng để giải quyết vấn đề
2.3.1. Cơ sở lý thuyết
2.3.1.1. Dãy con liên tiếp
Dãy con liên tiếp là dãy gồm các phần tử liên tiếp thuộc một dãy cho trước (dãy mẹ).
Ví dụ: Cho dãy A gồm 4 số nguyên {3,1,2,-6}. Dãy số {2}; {1,2}; {3,1,2}; {3,1,2,-6};  được gọi là các dãy con liên tiếp của dãy A. 
2.3.1.2. Dãy con có thể chọn không liên tiếp
Dãy con có thể chọn không liên tiếp là dãy thu được sau khi xóa một số phần tử (có thể không xóa phần tử nào) của một dãy cho trước (dãy mẹ) và giữ nguyên thứ tự các phần tử còn lại trong dãy.
Ví dụ: Cho dãy B gồm 5 số nguyên {3,1,2,-6, 9}. Dãy số {2}; {1,2}; {3,2}; {3,2,-6}; {3,1,2,-6,9};  được gọi là các dãy con có thể chọn không liên tiếp của dãy A. 
2.3.1.3. Độ phức tạp của thuật toán
Giả sử ta có hai thuật toán P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3). Khi n > 20 thì T1 < T2. Sở dĩ như vậy là do tỷ suất tăng của T1 nhỏ hơn tỷ suất tăng của T2. Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình thay vì xét chính bản thân thời gian thực hiện.
Cho một hàm T(n), T(n) gọi là có độ phức tạp f(n) nếu tồn tại các hằng C, N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0 (tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n) là O(f(n)) (đọc là “ô của f(n)”).
Các hàm thể hiện độ phức tạp có các dạng thường gặp sau: log2n, n, nlog2n, n2, n3, 2n, n!, nn. 
Trong cách viết, ta thường dùng logn thay thế cho log2n cho gọn.
Khi ta nói đến độ phức tạp của thuật toán là ta nói đến hiệu quả thời gian thực hiện chương trình nên có thể xem việc xác định thời gian thực hiện chương trình chính là xác định độ phức tạp của thuật toán.
2.3.2. Biện pháp lựa chọn và cài đặt chương trình tối ưu khi giải một số dạng bài tập về dãy con
Đối với mỗi dạng bài tập về dãy con tôi đưa ra một bài toán ví dụ, mỗi bài toán ví dụ tôi trình bày từ 2 hoặc 3 cách (cả cách làm của học sinh và cách làm tôi định hướng cho học sinh làm). Với phương châm của tôi “ mưa dầm thấm lâu” tôi ko hướng dẫn học sinh cách làm tối ưu ngay mà khi phát vấn một dạng bài tập mới mà tôi yêu cầu học sinh làm theo các trình tự sau:
Bước 1: Xác định bài toán
Bước 2: Suy nghĩ tìm ra thuật toán, viết chương trình (trên môi trường Free Pascal), tính độ phức tạp (Có thể nhiều cách).
Bước 3: Trao đổi cách làm của mình với bạn để tìm cái hay cái dở.
Bước 4: Sử dụng phần mềm Themis-chấm bài tự động để chấm cách làm của mình (với 10 bộ test giáo viên đã xây dựng sẵn, mỗi bộ test cấu hình là 1 điểm, thời gian chạy không quá 1 giây).
Bước 5: Nhận xét sự tối ưu của thuật toán.
Bước 6: Giáo viên định hướng cách làm tối ưu hơn (nếu có).
Bước 7: Sử dụng phần mềm Themis để chấm tất cả các cách đã viết chương trình.
Bước 8: Dựa vào kết quả, lựa chọn chương trình có độ phức tạp nhỏ nhất, thời gian thực hiện mỗi test nhỏ nhất và chương trình ngắn gọn dễ hiểu nhất.
Bước 9: Lập trình giải các bài tập tương tương với cách đã lựa chọn.
2.3.2.1. Bài tập về dãy con liên tiếp
2.3.2.1.1. Dạng 1: Các dãy con không chung nhau bất kỳ phần tử nào của dãy mẹ 
Các dãy con không chung nhau bất kỳ phần tử nào của dãy mẹ nghĩa là những phần tử của dãy mẹ đã thuộc dãy con thỏa mãn này thì không thuộc các dãy con thỏa mãn khác.
Ví dụ: Dãy mẹ gồm 7 phần tử {2, 5, -9, -6, 0, -7, -5}. Dãy con {-9, -6}; {-7, -5} là các dãy con liên tiếp không chung nhau bất kỳ phần tử nào của dãy mẹ. 
Lưu ý: Dạng bài tập này áp dụng cho cả trường hợp một phần tử đầu của dãy này trùng với một phần tử cuối của dãy kia.
2.3.2.1.1.1. Bài toán cơ bản: Cho một dãy A gồm N số nguyên (hoặc số thực) {a1, a2,, aN}. Dãy con ai, ai+1,, aj (1≤i≤j≤N) là dãy được tạo từ các phần tử liên tiếp của dãy A bắt đầu từ phần tử i và kết thúc ở phần tử j. Hãy tìm độ dài dãy con, số lượng dãy con, liệt kê chỉ số các dãy con, liệt kê giá trị các phần tử dãy con thõa mãn một điều kiện nào đó. (Độ dài dãy con là số lượng phần tử dãy con)
Để giải dạng bài tập này ta có thể sử dụng nhiều thuật toán như: thuật toán vét cạn các dãy con hoặc duyệt qua các phần tử của dãy hoặc sử dụng phương pháp quy hoạch động. Đối với dạng bài tập này tôi định hướng cho học sinh lựa chọn thuật toán duyệt qua các phần tử của dãy hoặc quy hoạch động.
Mô hình thuật toán:
Cách 1. Sử dụng phương pháp duyệt qua các phần tử của dãy:
- Duyệt qua tất cả các phần tử của dãy nếu:
	 + Thỏa mãn điều kiện, tăng độ dài thêm 1, ngược lại: 
Nếu dãy con đang xét cần lưu thì: lưu lại độ dài, chỉ số đầu của dãy, xác định lại độ dài, chỉ số đầu của dãy mới.
Nếu dãy con đang xét không cần lưu thì: lưu lại độ dài, chỉ số đầu của dãy mới.
Cách 2. Sử dụng phương pháp quy hoạch động. (Đây là cách tôi định hướng cho học sinh làm)
- Gọi f[i] là độ dài dãy con thỏa mãn điều kiện có phần tử cuối là a[i], i=1..n
- Gán giá trị độ dài dãy con trong trường hợp đơn giản: f[0]:=0; f[1]:=1.
- Tính f[i] nhờ các giá trị bài toán con đã tính từ trước như f[i-1], f[i-2],...
- Kết quả bài toán là sự tổng hợp kết quả từ các bài toán con f[i] (i=1,2,...,n)
2.3.2.1.1.2. Bài toán ví dụ
Cho một dãy A gồm N số nguyên {a1, a2,, aN}. Dãy con ai, ai+1,, aj (1≤i≤j≤N) là dãy được tạo từ các phần tử liên tiếp của dãy A bắt đầu từ phần tử i và kết thúc ở phần tử j.
Yêu cầu: Hãy tìm độ dài và liệt kê giá trị mỗi phần tử của dãy con dài nhất tạo thành cấp số cộng có công sai d.
Dữ liệu vào: File văn bản dayconcsc.inp gồm:
	- Dòng đầu ghi giá trị N, d (2≤N≤10000; 0≤d≤500 ).
	- Dòng sau gồm N số nguyên{a1, a2,, aN} (-106≤ai≤106) mỗi số cách nhau một dấu cách.
Dữ liệu ra: File văn bản dayconcsc.out gồm
- Dòng đầu ghi độ dài dãy con và số dãy con thỏa mãn.
- Dòng tiếp theo ghi giá trị các phần tử dãy con.
(Chú ý: Nếu không có dãy con nào thỏa mãn thì ghi 0)
Ví dụ:
Dayconcsc.inp
Dayconcsc.out
9 4
1 7 2 6 10 6 1 5 9
3 2
2 6 10
1 5 9
Cách 1: Khi gặp bài toán này thông thường học sinh sẽ sử dụng phương pháp vét cạn các dãy con như sau: 
Mô hình thuật toán:
For i:=1 to n do
 For j:=1 to n-i+1 do
 Begin
 {Xét tất cả các dãy con bắt đầu từ vị trí i có độ dài j}
 end;
hoặc 	For k:=1 to n do
 For j:=1 to n-k+1 do
	begin
	 j:=i+k-1;
	 {Xét tất cả các dãy con bắt đầu từ vị trí i đến vị trí j với độ dài k}
	 end;
Cài đặt chương trình:
Program c1_dayconcsc;
Type km=array[0..10001] of longint;
Const fi='dayconcsc.inp'; fo='dayconcsc.out';
Var a,cs:km; dmax,i,j,n,k,d:longint;
Procedure inday(b:km;m,l:longint);
Var i:integer;
Begin for i:=m to m+l-1 do write(b[i],' '); writeln;
End;
Function kt(b:km;m,l:integer):boolean;
Var i:integer;
Begin for i:=m to m+l-2 do
 if b[i+1]-b[i]d then exit(false); exit(true);
End;
BEGIN
 assign(input,fi);reset(input); assign(output,fo);rewrite(output);
 readln(n,d); for i:=1 to n do read(a[i]);
 {tim do dai va chi so dau day con thoa man}
 dmax:=0; k:=0;
 for i:=1 to n-1 do
 for j:=2 to n-i+1 do
 if kt(a,i,j) then
 begin
 if j>dmax then begin dmax:=j;k:=0; end;
 if j=dmax then begin k:=k+1;cs[k]:=i; end;
 end;
 {in ket qua}
 if dmax=0 then write('0')
 else begin writeln(dmax,' ',k);
 for i:=1 to k do inday(a,cs[i],dmax);
 end; close(input); close(output);
END.
Sử dụng phần mềm Themis – chấm bài tự động. Ta đo được thời gian thực hiện mỗi test cụ thể như sau: (có file test và code kèm theo)
Cách 
1
Độ phức tạp
Test01 (giây)
Test02
(giây)
Test03
(giây)
Test04
(giây)
Test05
(giây)
Test06
(giây)
Test07
(giây)
Test08
(giây)
Test09
(giây)
Test10
(giây)
0(n2)
0.1924
0.1074
0.2583
0.2691
6.9301
89.9473
>100
>100
>100
>100
Với cách này chỉ lấy được 40% số điểm câu này. Vì một số test có dữ liệu lớn chạy quá thời gian.
Cách 2: Thuật toán duyệt qua các phần tử của dãy mẹ.
Mô hình thuật toán:
- Khởi tạo: dmax=1; dem=1; dau=1; a[n+1]=a[n]+d+1;k=0;
{Biến dmax lưu độ dài max dãy, biến dau lưu giá trị đầu mỗi dãy, biến k lưu số lượng dãy con thỏa mãn}
- For i:=1 to n do
 	 Nếu a[i+1]-a[i]=d thì tăng biến dem, ngược lại:
	 Nếu dem>dmax thì begin dmax=dem;k=1;dem=1;cs[k]=dau;dau=i+1; 
end, ngược lại:
	 Nếu dem=dmax thì begin inc(k);cs[k]=dau;dau=i+1;dem=1; 
 end, ngược lai: begin dem=1; dau=i+1; end;
Cài đặt chương trình:
Program c2_dayconcsc;
Const fi='dayconcsc.inp'; fo='dayconcsc.out';
Var a,cs:array[0..10001] of longint;dmax,dem,i,j,n,dau,k,d:longint;
BEGIN
 assign(input,fi);reset(input);assign(output,fo);rewrite(output);
 readln(n,d); for i:=1 to n do read(a[i]);
 {tim do dai dmax va chi so dau cac day con thoa man}
 k:=0;dm