Đề HSG Tin học

SỞ GIÁO DỤC & ĐÀO TẠO
LÂM ĐỒNG

ĐỀ THI DỰ BỊ
(Đề thi có 02 trang, gồm 3 bài)
KÌ THI CHỌN HỌC SINH GIỎI CẤP TỈNH
NĂM HỌC 2011 - 2012

Môn : TIN HỌC - THCS
Thời gian : 150 phút (không kể thời gian giao đề)
Ngày thi : 18/2/2012


Cấu trúc đề thi:
STT
Tên bài
Tên file bài làm
Tên file INPUT
Tên file OUTPUT

1
SỐ SIÊU NGUYÊN TỐ
SIEUNT.PAS
SIEUNT.INP
SIEUNT.OUT

2
CÁC THANH GỖ
THANHGO.PAS
THANHGO.INP
THANHGO.OUT

3
XẾP LỊCH LÀM BÀI
LICH.PAS
LICH.INP
LICH.OUT


Bài 1: (6 điểm) SỐ SIÊU NGUYÊN TỐ
Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tuỳ ý các chữ số bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố.
Ví dụ : 7331 là một số siêu nguyên tố có 4 chữ số vì 733, 73, 7 cũng là các số nguyên tố.
Em hãy viết chương trình tìm các số siêu nguyên tố có N chữ số (0 < N <10) và số lượng các số tìm được.
Dữ liệu vào: cho trong File SIEUNT.INP chứa số N.
Kết quả: ghi ra file SIEUNT.OUT gồm các dòng:
- Dòng 1: số lượng các số siêu nguyên tố có N chữ số.
- Dòng tiếp theo liệt kê các số siêu nguyên tố tìm được.
Ví dụ :

SIEUNT.INP
SIEUNT.OUT

4
16
2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393


Bài 2 (7 điểm): CÁC THANH GỖ
Trong một buổi cắm trại của lớp, bạn An mua N thanh gỗ có độ dài mỗi thanh là L. Khi cắm trại, các bạn của An cưa các thanh gỗ ra một cách ngẫu nhiên (có độ dài là số nguyên).
Về sau các bạn có ý định gắn các mẩu con để khôi phục lại các thanh gỗ ban đầu nhưng lại quên mất độ dài L. Họ đã quyết định nối lại các thanh gỗ sao cho chúng có độ dài bằng nhau.
Hãy giúp họ chọn cách nối sao cho chúng có độ dài như nhau và càng ngắn càng tốt.
Dữ liệu vào: cho trong file văn bản THANHGO.INP:
- Dòng đầu ghi số N (N(50) là số lượng các mẩu gỗ.
- N dòng tiếp theo mỗi dòng ghi số nguyên Li (1 ( Li ( 100, 1 ( i ( N) thể hiện độ dài của mẩu gỗ thứ i.
Kết quả: Ghi ra file văn bản THANHGO.OUT
- Dòng đầu tiên ghi độ dài ngắn nhất tìm được.
- Trên mỗi dòng ghi số hiệu các mẩu gỗ dùng để ghép thành thanh gỗ đó.
Ví dụ:
THANHGO.INP
THANHGO.OUT

10
2
3
5
2
7
4
6
1
3
3
9
1 2 6
3 8 9
4 5
7 10



Bài 3: (7 điểm) XẾP LỊCH LÀM BÀI
Một học sinh cần làm N bài tập được đánh số từ 1 đến N (1 ( N ( 100). Mỗi một bài tập i làm trong khoảng thời gian là Ai (1 ( i ( N, 1 ( Ai ( 100). Thời gian tối đa của một buổi là L (1 ( L ( 150). Bài tập i phải được giải trước bài tập i + 1. Trong một buổi có thể bố trí giải một hay nhiều bài tập.
Hãy xếp lịch giải hết các bài tập sao cho số buổi ít nhất .
Dữ liệu vào: từ file LICH.INP gồm:
- Dòng đầu là số N
- Dòng tiếp theo là L
- Dòng cuối cùng là N số thể hiện A1. A2,..., An
Kết quả: ghi ra file LICH.OUT chứa số buổi của lịch hoặc thông báo “Không xếp lịch được”.
Ví dụ :
LICH.INP
LICH.OUT

10
120
60 60 5 30 10 10 20 30 80 60
4



----------HẾT----------





Họ và tên thí sinh: Số báo danh:
Giám thị 1: Ký tên:
Giám thị 2: Ký tên: