Chon doi tuyen QG Pascal 4

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (111 KB, 3 trang )

(1)<div class='page_container' data-page=1>

Bộ giáo dục và Đào tạo

thi chọn đội tuyển Tin học Quốc gia

Thời gian làm bài: 300 phút

Ngày thi thứ hai: 5-5-2002

Tổng quan thi ngy th HAI

Tên bài Tên chơng trình Tên file dữ liệu Tên file kết quả
Bài 4 Qui trình sản xuất PROCESS.PAS PROCESS .INP PROCESS.OUT

Bài 5 Tuần tra PATROL.PAS PATROL.INP PATROL.OUT

Bµi 6 Th»ng Bêm SMAX.PAS SMAX.INP SMAX.OUT

H·y lập trình giải các bài toán sau đây:

Bài 4. Qui trình sản xuất

Vic sản xuất các loại sản phẩm trên dây chuyền sản xuất của một nhà máy Quốc phòng đ ợc tiến
hành theo các qui trình xác định theo một khung chuẩn. Quy trình sản xuất một sản phẩm là dãy các
cơng đoạn độc lập, mỗi cơng đoạn đợc kí hiệu bằng một chữ cái Latinh thờng từ ‘a’ đến ‘z’. Các cơng
đoạn trong một quy trình khơng nhất thiết phải khác nhau. Khung chuẩn để xác định qui trình sản xuất
mỗi loại sản phẩm trên dây chuyền sản xuất của nhà máy bao gồm:

 Các chữ cái Latinh thờng, xác định các công đoạn cần thực hiện,
 Các dấu ngoặc vuông mở [ và ngoặc vng đóng ].

Các công đoạn đặt trong một cặp dấu ngoặc vng mở và đóng tơng ứng có thể đợc thực hiện hay bỏ
qua tuỳ theo loại sản phẩm cần sản xuất. Ví dụ, theo khung chuẩn a[bc[d]]e[f] chỉ có thể xác định tất cả
6 qui trình sản xuất: ae, aef, abce, abcef, abcde, abcdef. Vì là nhà máy Quốc phịng nên chỉ có Giám đốc

đợc biết khung chuẩn.

Với chủ trơng huy động mọi tiềm năng trong nớc để phát triển kinh tế Quốc dân, Bộ quốc phòng cho
phép nhà máy sản xuất các sản phẩm dân sự. Bộ phận kế hoạch đệ trình các qui trình sản xuất của một số
loại sản phẩm mới. Giám đốc phải xét sự phù hợp với khung chuẩn của các qui trình này. Ví dụ, với
khung chuẩn đã nêu, qui trình abcef là phù hợp, cịn qui trình adef thì khơng.

u cầu: Cho M qui trình, hãy xác định các qui trình phù hợp với khung chuẩn.
Dữ liu: Vo t file vn bn PROCESS.INP:

Dòng đầu ghi khung chuẩn (gồm không quá 500 kí tự),

Dũng th hai ghi số nguyên M (1 <M 10) là số qui trình đề xuất,

 M dịng tiếp theo, mỗi dịng ghi một qui trình đề xuất, gồm khơng q 400 kí tự. Các qui trình đ
-ợc đánh số từ 1 đến M theo trình tự ghi trong file.

KÕt qu¶: Ghi ra file văn bản PROCESS.OUT:

Dòng đầu ghi số nguyên K là số qui trình phù hợp,

Nếu K>0 thì dòng thứ 2 chứa K số nguyên là các số hiệu của các qui trình phù hợp. Hai số liên
tiếp cách nhau ít nhất một dấu cách. Nếu K=0 thì dòng này chứa một số 0.

Ví dụ:

PROCESS.INP PROCESS .OUT

a[bc[d]]e[f]
2

adef
abcef

1
2

Bài 5. TuÇn tra

Tại Nha trang, ngay trong thành phố có một bể tắm nớc khống nóng tự nhiên, đợc dẫn từ
trên núi xuống. Từ nguồn, nớc đợc dẫn theo các đoạn ống nớc, qua các bể nớc trung gian để xử
lí trớc khi đổ vào bể tắm. Các bể nớc khác nhau đều ở các độ cao khác nhau và đợc đánh số thứ
tự bắt đầu từ 1 (là nguồn nớc) đến N (là bể tắm). Nớc chảy từ bể ở cao hơn (có số hiệu nhỏ hơn)
xuống bể ở thấp hơn (có số hiệu lớn hơn) nếu có đoạn ống nớc nối trực tiếp chúng. Nh vậy nớc
từ nguồn có thể chảy theo các đoạn ống nớc khác nhau tạo thành một tuyến nớc đổ vào bể tắm.
Mỗi bể nớc có ít nhất một đoạn ống nớc dẫn nớc vào và một đoạn ống nớc dẫn nớc ra.

</div>
(2)<div class='page_container' data-page=2>

Vì là nớc khống q hiếm nên các đoạn ống nớc phải đợc tuần tra thờng xuyên. Hàng ngày,
Ban quản lí phải điều động cán bộ đi tuần tra và trả tiền bồi dỡng cho họ. Một lợt đi tuần tra
phải xuất phát từ nguồn, theo các đoạn ống nớc của cùng một tuyến nớc nào đó và kết thúc tại
bể tắm. Ban quản lý phải trả cho một lợt tuần tra một khoản tiền là:

T  <số đoạn ống nớc trên tuyến nớc tuần tra> đồng.

Yêu cầu: Hãy giúp Ban quản lí tổ chức tuần tra sao cho mỗi đoạn ống nớc phải đợc tuần tra ít
nhất hai lợt và tổng số tiền phải trả là ớt nht.

Dữ liệu: Vào từ file văn bản PATROL.INP:

Dòng đầu chứa 2 số nguyên dơng N, T tơng ứng là số lợng các bể nớc và số tiền bồi

d-ỡng cho một lợt ngời tuần tra đi qua một đoạn ống nớc (1 < N, T 100)

Mỗi dòng trong N-1 dòng tiếp theo ghi dãy các số nguyên. Các số trong dòng (i+1) xác
định số hiệu các bể nớc có đoạn ống dẫn nớc trực tiếp từ bể thứ i. Số thứ nhất k trong
dòng là số lợng các bể nớc đó và k số tiếp theo là các số hiệu của chúng.

Hai số liên tiếp trên cùng một dòng đợc ghi cách nhau một dấu cách.

Kết quả: Ghi ra file văn bản PATROL.OUT gồm một số là tổng số tiền ít nhất tìm đợc.
Ví dụ:

PATROL.INP PATROL.OUT

10 2 
3 3 2 4 
1 3

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

</div>
(3)<div class='page_container' data-page=3>

Bµi 6

.

Th»ng Bêm

Bờm vừa thắng Phú ông trong một lần thách đố. Phú ông nghĩ ra một cách trả tiền thua cuộc và
nói với Bờm: “Ta cho phép nhà ngơi đợc lựa chọn để thu hoạch lúa từ các thửa ruộng trong cánh
đồng của ta, bao nhiêu tuỳ thích, nhng khơng đợc thu hoạch lúa ở hai thửa có chung bờ”. Biết

rằng: trên bản đồ, cánh đồng của Phú ơng có dạng một đa giác lồi n đỉnh  = M1M2...Mn đợc

chia ra làm n-2 thửa ruộng có dạng hình tam giác với 3 đỉnh là ba đỉnh của đa giác lồi . Hai
thửa ruộng đợc gọi là có chung bờ nếu hai tam giác tơng ứng có chung cạnh. Hình vẽ minh hoạ
cho thấy cánh đồng của Phú ông là một đa giác 6 đỉnh đợc chia ra làm 4 thửa ruộng (tam giác).
Mặt khác, năng suất lúa ở các thửa ruộng trên cánh đồng là nh nhau. Vì vậy muốn thu hoạch
đ-ợc nhiều lúa nhất, Bờm cần tìm cách chọn các thửa ruộng trong cánh đồng với tổng diện tích là
lớn nhất.

Yêu cầu: Hãy giúp Bờm cách chọn các thửa ruộng trong cánh đồng của Phú ông sao cho tổng
diện tích của các thửa ruộng đợc chọn là ln nht.

Dữ liệu: Vào từ file văn bản có tên SMAX.INP:

Dòng đầu tiên chứa số nguyên dơng n (n  500);

 Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên xi , yi là toạ ca nh Mi ca

đa giác lồi , (|xi| 10000, |yi|  10000), i =1, 2, ..., n.

 Dòng thứ j trong số n-3 dòng tiếp theo chứa hai chỉ số của hai đỉnh của đa giác là hai
đầu mút của một đờng chéo (bờ của thửa ruộng) phân chia đa giác (cánh đồng) thành n
-2 tam giác (thửa ruộng).

Hai số liên tiếp trên cùng một dòng đợc ghi cách nhau bởi dấu cách.
Kết quả: Ghi ra file văn bản SMAX.OUT:

 Dòng đầu tiên chứa số nguyên dơng p là số lợng thửa ruộng và số thực S đợc ghi với 3
chữ số sau dấu phảy là tổng diện tích lớn nhất của các thửa ruộng mà Bờm chọn;

 Dòng thứ j trong số p dòng tiếp theo ghi chỉ số của 3 đỉnh của đa giác là ba đỉnh của
thửa ruộng thứ j mà Bờm cần chọn, j = 1, 2, ..., p.

Ví dụ:

SMAX.INP SMAX.OUT Hình vẽ minh hoạ

6
5 11
9 10
12 7
9 4
5 3
3 7
1 3
3 5
1 5

</div>