Đề thi HSG 12 tỉnh Cà Mau 2008-2009

SÔÛ GIAÙO DUÏC VAØ ÑAØO TAÏO KYØ THI CHOÏN HOÏC SINH GIOÛI LÔÙP 12 TÆNH CAØ MAU

CAØ MAU NAÊM HOÏC 2008-2009

- Moân: Tinhoïc

- Ngaøy thi: 07-12-2008

- Thôøi gian: 180 phuùt

Baøi1: (6 ñieåm)

Ñeå maõ hoùa moät vaên baûn goàm toaøn chöõ caùi tieáng Anh ngöôøi ta coù theå laøm nhö sau:

Xeáp baûng chöõ caùi theo voøng troøn, sau ñoù thay moãi kí töï baèng kí töï ñöùng sau noù n vò trí

trong baûng voøng troøn. Ví duï vôùi n =7 thì “anh” ñöôïc maõ hoùa thaønh “huo”.

Baïn haõy laäp chöông trình nhaäp soá töï nhieân n, sau ñoù

- Maõ hoùa moät vaên baûn (xaâu kí töï)

- Giaûi maõ moät vaên baûn ñaõ maõ hoùa

Baøi 2: (7 ñieåm)

Coù X ñòa ñieåm daân cö ñaùnh soá töø 1 ñeán X. Giöõa Y caëp ñòa ñieåm trong soá X ñòa ñieåm

noùi treân coù tuyeán ñöôøng noái chuùng. Caàn xaây döïng moät trung taâm dòch vuï toång hôïp taïi

moät ñòa ñieåm hoaëc laø truøng vôùi moät soá caùc ñòa ñieåm daân cö hay laø naèm treân tuyeán

ñöôøng noái hai ñòa ñieåm naøo ñoù, sao cho toång khoaûng caùch töø trung taâm dòch vuï ñeán X

ñòa ñieåm daân cö laø nhoû nhaát. Ta goïi khoaûng caùch hai ñòa ñieåm laø ñoä daøi ñöôøng ñi ngaén

nhaát noái chuùng. Giaû söû raèng X ñòa ñieåm treân lieân thoâng vôùi nhau.

Döõ lieäu: Vaøo töø file vaên baûn BAI1.INP goàm Y+1 doøng

- Doøng 1 chöùa hai soá X vaø Y

- Doøng n+1 (1<=n<=Y) ghi 3 soá nguyeân döông: hai soá ñaàu laø chæ soá cuûa hai ñòa

ñieåm daân cö ñöôïc noái nhau bôûi tuyeán ñöôøng naøy, coøn soá thöù ba laø ñoä daøi cuûa

tuyeán ñöôøng.

Döõ lieäu laø caùc soá nguyeân döông

Keát quaû: Xuaát ra maøn hình thoâng baùo vò trí trung taâm dòch vuï laø toång khoaûng caùch töø

trung taâm dòch vuï ñeán caùc ñòa ñieåm daân cö.

Neáu ñieåm tìm ñöôïc naèm treân tuyeán ñöôøng thì caàn chæ roõ hai ñaàu cuûa tuyeán ñöôøng vaø

khoaûng caùch töø ñòa ñieåm xaây döïng ñeán ñaàu thöù nhaát.

Baøi 3: (7 ñieåm)

Coù n thaønh phoá ñöôïc ñaùnh soá töø 1 ñeán n. Maïng löôùi giao thoâng giöõa caùc thaønh phoá laø

caùc ñöôøng moät chieàu. Treân ñöôøng ñi (neáu coù) töø thaønh phoá i ñeán thaønh phoá j, ngöôøi ta

khoâng ñöôïc mang quaù a[i,j] ñôn vò haøng. Neáu khoâng coù ñöôøng ñi töø thaønh phoá i ñeán

thaønh phoá j thì xem nhö a[i,j]=0. Caàn vaän chuyeån haøng töø thaønh phoá s ñeán thaønh phoá d.

haõy laäp keá hoaïch vaän chuyeån sao cho toång khoái löôïng haøng vaän chuyeån laø nhieàu nhaát.

Döõ lieäu: vaøo file vaên baûn Bai2.inp goàm n+1 doøng

- Doøng 1: Goàm 3 soá nguyeân döông n, s, d

- Doøng i+1 (1<=i<=n): Ghi n soá A[i,1], A[i,2],. . . ,A[i,n]

Keát quaû: Xuaát ra maøn hình goàm n+1 doøng

- Doøng 1: Ghi toång löôïng haøng vaän chuyeån.

- Doøng i+1 (1<=i<=n): Ghi n soá F[i,1], F[i,2], . . . ,A[i,n] trong ñoù F[i,j] öùng vôùi

löôïng haøng vaän chuyeån töø thaønh phoá i ñeán thaønh phoá j

Caùc soá treân cuøng moät doøng ghi caùch nhau ít nhaát moät daáu caùch.

Heát