Đề thi chọn HSG tỉnh Nghệ An môn Tin học lớp 12 năm học 2013 - 2014  (Bấm vào liên kết phía dưới để tải xuống)

Đề thi chọn HSG tỉnh Nghệ An môn Tin học lớp 12 năm học 2013 - 2014. Gồm có 4 bài, Bài 1: LAPTRINH.PAS, Bài 2: DOANMAX.PAS, Bài 3: XOASO.PAS, Bài 4: MAHOA.PAS. Trong tài liệu có cả hướng dẫn giải và mã nguồn đáp án.

Đề thi chọn HSG tỉnh Nghệ An môn Tin học lớp 12 năm học 2013 - 2014

Bài 1. (7 điểm) LAPTRINH
Trong cuộc thi lập trình có N bài thi giải đúng yêu cầu đặt ra. Ban tổ chức quyết định trao giải phần
thưởng đặc biệt cho bài thi tốt nhất, đó là bài thi có thời gian chạy chương trình ít nhất. Cho biết bài thi
thứ i (1<=i<=N) có thời gian chạy là một số nguyên A (Tính theo đơn vị Centisecond, 1 Centisecond =  1/100 giây).
Yêu cầu: Hãy cho biết thời gian của bài thi được trao thưởng và có bao nhiêu bài thi được trao thưởng.
Dữ liệu: Vào từ file văn bản LAPTRINH.INP
- Dòng 1 chứa số nguyên dương N (N<=100).
- Dòng 1 chứa N số nguyên
Kết quả: Ghi ra file văn bản LAPTRINH.OUT
- Dòng thứ 1 chứa một số nguyên là thời gian ít nhất tìm được.
- Dòng thứ 2 chứa một số nguyên là số bài thi cùng đạt thời gian ít nhất

Bài 2. (5 điểm) ĐOẠN MAX
Cho chuỗi ký tự S gồm các chữ cái in hoa (A…Z) với độ dài không vượt quá 10. Yêu cầu: Hãy tìm đoạn con các kí tự liên tiếp dài nhất sao cho không có kí tự nào xuất hiện nhiều hơn một lần. Trong trường hợp có nhiều hơn một đoạn con có cùng chiều dài dài nhất, hãy chỉ ra đoạn xuất hiện đâu tiên trong chuỗi S.
Dữ liệu: Vào từ văn bản DOANMAX.INP:
- Gồm một dòng duy nhất chứa chuỗi S.
Kết quả: Ghi ra file văn bản DOANMAX.OUT
- chổ một dòng duy nhất chứa số nguyên P và L tương ứng là vị trí và chiệu dài của đoạn con dài nhất tìm được.
Bài 3. (5 điểm) XOÁ SỐ.
Cho dãy số nguyên không âm A. Người ta muốn chọn 2 chỉ số i, j sao cho 1<=i<=j<=N và xoá khỏi dãy 2 số để tổng giá trị các số còn lại trong dãy là số chẵn.
Yêu cầu: Hãy đếm số lượng cách chọn 2 chỉ số i, j thoả mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau.
Bài 4. MÃ HOÁ
Nam rất thích thú với việc mã hoá dữ liệu. Trong buổi thảo luận ở lớp Nam đã trình bày một ý tưởng rất thú vị rằng bạn ấy vừa phát minh ra một cách mã hoá mới, có thể mã các thông tin mà không ai có thể giải mã. Cách mã hoá đó là: Với một số nguyên N, xoá các chữa số từ con số này bằng mọi cách có thể, ta sẽ nhận được các số mới. Một số cách xoá mà số mới thu được có giá trị bằng số cũ đó là khi ta xoá các chữ số 0 bên trái. Hãy tìm tổng của tất cả các con số mới thu được. Tổng này chính là mã hoá của N.
Một bạn trong lớp đã có ý kiến “Mình nghĩ cách mã hoá của cậu trên máy tính sẽ thực hiện mất nhiều thời gian với số có nhiều chữ số, chẳng hạn só có 100 chữ số. Không thể chờ để có một mã số cho số có 100 chữ số. Cách mã hoá này của bạn không thể được áp dụng trên thực tế”. Nam đã trả lời “không, không, không”. Ngày mai mình sẽ đưa ra chương trình thực hiện cách mã hoá này, và sẽ mã hoá cho số có 100 chữ số trong thời gian không quá 1 giây” câu trả lời của Nam được cả lớp rất hoan nghênh. Bạn hãy
giúp Nam viết chương trình đó.
Yêu cầu: Cho số nguyên N (1<=N<=10 ) và xác định số nguyên S là mã hoá của N theo phương pháp mã hoá của Nam.
Dữ liệu: Vào từ file văn bản MAHOA.INP
Chỉ một dòng duy nhất chứa số nguyên N (chữ số bên trái các chữ số của N là khác 0).
Kết quả: Đua ra file văn bản MAHOA.OUT
- Chỉ một số duy nhất là số nguyên S tìm được.
HƯỚNG DẪN GIẢI
(Chú ý: Hướng dẫn không phải là đáp án của Sở, chỉ là hướng dẫn tham khảo, giải theo cách hiểu
biết của cá nhân. Vì thế có thể không chính xác và cũng do làm trong thời gian ngắn nên có thể mắc một
số lỗi nào đó)
Câu 1. Câu này thì chắc các bạn đều biết cách giải. Và sẽ lấy được điểm tối đa 7 điểm.

Câu 2. Đề bài cho là XÂU nhưng lại có số lượng phần tử không vượt quá 10 . Trong khi đó xâu chỉ có tối đa 255 ký tự. Vì vậy nếu bạn khai báo là Xâu thì chỉ lấy được 80% test tức là 4 điểm. Vậy làm thế nào để lấy được 100% test, bạn phải khai báo và xử lý dạng Mảng các ký tự. Thuật toán thì vẫn không có gì là khó vì nó gần giống bài Tìm đoạn đơn điệu dài nhất, duy chỉ khác nhau điểm dừng mà thôi.

Câu 3. Câu này nếu bạn xét tất cả mọi trường hợp i, j thì chắc chắn không thể lưu mảng với 1 triệu phần tử được. Và vòng lặp cũng rất lớn. Còn nếu bạn chỉ cần lấy 50% như trong đề thì hoàn toàn có thể vét cạn các trường hợp bằng cánh
1. Đầu tiên tính tổng các phần tử vào biến T (tính 1 lần).
2. Thử tất cả các trường hợp

Nhưng để lấy được 100% test thì ta chú ý rằng.
- Gọi SL là số phần tử lẽ, SN là số phần tử chẵn  SL có giá trị lẽ thì ta có Tổng là số lẽ, ngược lại
SL có giá trị chẵn thì Tổng sẽ được số Chẵn.
Vì vậy
TH1: Nếu SL là số lẽ cần xoá 1 số lẽ và một số chẵn số cách xoá là SL*SN.
2 2
TH2: Nếu SL là số chẵn cần xoá 2 số lẽ hoặc 2 số chẵn Sẽ có (SL -SL + SN -SN) cách xoá
(Các bạn nhóm dãy số thành 2 nhóm sẽ nhận thấy được điều đó).
Vậy bài toán của ta trở thành bải toán Đếm số lượng phần tử Lẽ và số lượng phần tử chẵn.

Câu 4. Câu này thực tế mình chưa nghĩa ra thuật toán nào khác ngoài thuật toán Sinh xâu nhị phân.
-B1: Đọc số trong tệp vào một xâu hoặc biến mảng ký tự.
Giả sử độ dài số đó là N.
Thì ta sẽ có 2 cách xoá. Nên ta dùng thuật toán sinh ra xâu nhị nhân N bít từ
- B2: tạo xâu SD là xâu đầu tiên sẽ là: 00…00
- B3: tạo xâu SC là xâu cuối cùng sẽ là:11.11
Sẽ có 2 xâu như thế
- B4: Ta sẽ cho SD chạy tới SC.
- B5: Với mỗi giá trị của xâu SD ta lấy ra một sô. Bằng cách: Nếu SD[i]=’1’ thì giữ nguyên chữ số
thứ i trong số ta đọc vào.
Khi đó chương trình sẽ là

 

Tải xuống để xem tài liệu hoàn chỉnh - Chia sẻ cho bạn bè nếu trang web có ích với bạn!
Nguồn tài liệu:

Bạn cũng có thể quan tâm:

Bài tập môn Tin học lớp Lớp 12
Mời bạn tham gia hỏi - đáp
Thư viện bài tập © 2014 -2017 - Liên hệ - Giới thiệu - Bản quyền - Chính sách bảo mật - Sitemap