Đề thi học sinh giỏi lớp 12 THPT tỉnh Bến Tre năm 2012 – 2013 môn Tin học

Bài 1 (6 điểm): Nhóm bạn thân (Tên file chương trình BAI1.PAS)

Trong giờ hoạt động ngoại khóa, cô giáo chủ nhiệm lớp đã tổ chức phỏng vấn và ghi nhận mối quan hệ giữa các học sinh trong lớp vào bảng vuông A có N hàng x N cột; với N là sĩ số của lớp (N ≤ 50). Quy ước cách ghi như sau:

– Các học sinh được đánh thứ tự từ 1 đến N

– Căn cứ vào danh sách học sinh, có thể tra được tên học sinh nếu biết số thứ tự của học sinh đó.

– Ô A[i, j] trong bảng bằng 1 có nghĩa là học sinh thứ i chơi thân với học sinh thứ j (dĩ nhiên A[j; i] cũng bằng 1) với 1 ≤ i, j ≤ N.

* Yêu cầu: Anh (chị) hãy viết chương trình giúp cô chủ nhiệm tìm các kết quả sau:

1. Xác định số bạn thân của mỗi học sinh trong lớp.

2. In ra tên của một học sinh có ít bạn thân nhất.

3. Nếu học sinh A thân với B, học sinh B thân với C, học sinh C thân với D… thì ta gọi A, B, C, D… là một nhóm bạn. Hãy giúp cô giáo xác định trong lớp có bao nhiêu nhóm bạn như vậy.

* Dữ liệu vào: Cho trong file văn bản KETBAN.INP. Hàng đầu tiên ghi giá trị của N. N hàng kế tiếp biểu diễn bảng vuông A; các số trên đường chéo chính bằng 1. Các số cách nhau ít nhất 1 khoảng trắng. N hàng tiếp theo ghi nhận danh sách học sinh trong lớp, mỗi hàng gồm số thứ tự học sinh, sau số thứ tự là tên của học sinh; tên của học sinh là 1 chuỗi kí tự liên tục (từ A đến Z hoặc từ a đến z), không có khoảng trắng. Số thứ tự và tên cách nhau bởi dấu “-“.

* Dữ liệu ra: Ghi vào file văn bản KETBAN.OUT. Hàng đầu tiên là N số, biểu diễn số bạn thân của N học sinh. Hàng thứ hai ghi tên của một học sinh có ít bạn thân nhất. Hàng thứ ba ghi số nhóm bạn trong lớp.

Bài 2 (7 điểm): Bảo trì Robot (Tên file chươn trình BAI2.PAS)

Trong khu mỏ trên đảo có các robot được đánh số thứ tự liên tục từ a đến b (1 ≤ a, b ≤ 10⁴). Vì điều kiện thời tiết xấu nên chỉ có 1 lô hàng dầu bôi trơn được chở đến trong tuần để bảo trì định kỳ các robot. Lô hàng này không đủ cho tất cả các robot, người ta quyết định tổ chức một cuộc “lô tô” để phân phối số dầu bôi trơn đó: dùng máy tính đưa ra dãy số nguyên A gồm n số (1 ≤ n ≤ 10²) và số nguyên k (0 ≤ k ≤ n); những robot nào có số thứ tự chia hết cho ít nhất k số trong dãy số nguyên A thì được trọn bảo trì.

* Yêu cầu: Hãy đếm số lượng robot được sử dụng dầu bôi trơn để bảo trì định kỳ.

* Dữ liệu vào: trong file BAOTRI.INP. Dòng đầu ghi hai n, k; dòng tiếp theo ghi n số nguyên dương A[1]..A[n] (0 ≤ A[i] ≤ 10⁴); dòng cuối ghi hai số a, b. Các số cách nhau ít nhất 1 khoảng trắng.

* Dữ liệu ra: ghi vào file BAOTRI.OUT ghi số lượng robot được chọn để bảo trì.

Bài 3 (7 điểm): Tổng bằng nhau (Tên file chương trình BAI3.PAS)

Cho dãy số A gồm N số nguyên a₁, a₂, a₃,…, a_N và một số nguyên K (N ≤ 10; 1 < K < N; 1 ≤ a[i] ≤ 100 với 1 ≤ i ≤ N). Hãy đưa ra một cách chia dãy số thành K nhóm có tổng bằng nhau.

* Dữ liệu vào trong file văn bản TBN.INP. Hàng đầu tiên ghi hai số N, K. Các hàng tiếp theo ghi N số nguyên của dãy. Các số cách nhau ít nhất 1 khoảng trắng hoặc xuống hàng.

* Kết quả: ghi ra file văn bản TBN.OUT gồm K hàng, mỗi hàng ghi giá trị các số trong nhóm thứ j (1 ≤ j ≤ K); các số cách nhau ít nhất 1 khoảng trắng. Nếu không có lời giải thì ghi ký hiệu “-” vào File kết quả.

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