đề thi hoc sinh giỏi nam định

SỞ GIÁO DỤC – ĐÀO TẠO
NAM ĐỊNH
KỲ THI HỌC SINH GIỎI THPT TOÀN TỈNH
NĂM HỌC 2008 - 2009
Môn: TIN HỌC Lớp 12
(Thời gian làm bài: 180 phút, không kể thời gian giao đề)

Đề thi gồm 02 trang

Lập chương trình giải các bài toán sau:

Bài 1: (6 điểm) Nhân hai phân số
Cho hai phân số
và
.
Hãy xác định 2 số nguyên dương E và F thỏa mãn 2 điều kiện sau:
+ Điều kiện 1:

+ Điều kiện 2:
là phân số tối giản
Dữ liệu vào: từ tệp văn bản NHAN.INP, có cấu trúc
+ Dòng 1 chứa hai số A và B.
+ Dòng 2 chứa hai số C và D.
( A, B, C, D là các số nguyên dương và không lớn hơn 10000)
Dữ liệu ra: kết quả đưa ra tệp văn bản NHAN.OUT
Có một dòng chứa hai số E và F tìm được thỏa mãn hai điều kiện trên.
(Trong tệp dữ liệu vào hoặc ra, các số trên cùng một dòng cách nhau ít nhất một dấu cách).

Ví dụ về dữ liệu vào/ra
NHAN.INP
NHAN.OUT

2 5
3 6
1 5


Bài 2: (7 điểm) Tìm dãy con chung
Dãy C gọi là dãy con chung của dãy A và dãy B nếu C là dãy gồm các phần tử nằm liên tiếp cả trong A và B.
Cho hai dãy số A và B, mỗi dãy đều có N phần tử (các phần tử đều nguyên dương và không quá 1000). Yêu cầu tìm dãy C là dãy con chung của A và B mà có nhiều phần tử nhất.
Dữ liệu vào: từ tệp văn bản DAYCON.INP, có cấu trúc:
Dòng 1 chứa số N (N nguyên dương và không quá 500)
Dòng 2: chứa N số thuộc dãy số A.
Dòng 3: chứa N số thuộc dãy số B.
Dữ liệu ra: đưa ra tệp văn bản DAYCON.OUT
Chứa duy nhất một số là số phần tử của dãy C thỏa mãn yêu cầu.
(Trong tệp dữ liệu vào hoặc ra, các số trên cùng một dòng cách nhau ít nhất một dấu cách).
Ví dụ về dữ liệu vào /ra:
DAYCON.INP
DAYCON.OUT

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



 (dãy con thỏa mãn: 1, 7)

Bài 3: (7 điểm) Công ty kinh doanh xăng dầu
Công ty kinh doanh xăng dầu BX hiện có N lít xăng. Công ty nhận được M yêu cầu mua xăng của khách hàng (khách hàng được đánh số từ 1 đến M), mỗi yêu cầu cần mua một lượng xăng nhất định. Nếu công ty BX không đáp ứng đủ lượng xăng cần thiết thì sẽ bị mất lòng với khách hàng. Vì lượng xăng có thể không đủ cho tất cả các yêu cầu của khách hàng nên phải từ chối một số khách hàng nào đó.
Công ty BX nhờ em tìm cách bán xăng cho các khách hàng chỉ làm mất lòng khách hàng ít nhất.
Dữ liệu vào: từ tệp văn bản BX.INP, có cấu trúc
- Dòng 1 chứa 2 số N và M.
(N và M nguyên dương, N<1 000 000, m<2 000)
- Dòng 2 chứa M số nguyên dương, số thứ I trong M số là số lít xăng mà khách hàng thứ I yêu cầu mua (mỗi yêu cầu của khách đều nguyên dương và không quá 10 000 lít).
Dữ liệu ra: Kết quả đưa ra tệp văn bản BX.OUT, theo cấu trúc
- Dòng 1: chứa số S là số lượng các khách hàng mất lòng ít nhất.
- Nếu S>0 thì dòng 2 chứa S số theo thứ tự tăng, số thứ j trong S số thể hiện khách hàng j mất lòng. Nếu có nhiều trường hợp thỏa mãn S thì chỉ cần đưa ra một trường hợp.
(Trong tệp dữ liệu vào hoặc ra, các số trên cùng một dòng cách nhau ít nhất một dấu cách).
Ví dụ về dữ liệu vào /ra:
BX.INP
BX.OUT

100 5
50 20 60 40 30
2
3 4

 (có trường hợp khác: 1 3)

Chú ý: tệp chương trình của bài 1 đặt tên là CHIA.PAS.
của bài 2 đặt tên là DAYCON.PAS.
của bài 3 đặt tên là BX.PAS.

Hết


Họ và tên thí sinh: . . . . . . . . . . . . . . . . .