ĐỀ SỐ 1

Bài 1. Số nguyên tố

In ra file SONT.TXT tất cả các số nguyên tố không lớn hơn n (n nhập từ bàn phím và <= 60000).

Bài 2. Hệ đếm

Trong một cuộc truy tìm một xe ôtô chở hàng lậu, nguồn tin đầu tiên cho biết: số của biển xe là số có 3 chữ số đối xứng (một số có n chữ số trong một hệ đếm nào đó được gọi là đối xứng nếu chữ số thứ 1 giống với chữ số thứ n, chữ số thứ 2 giống với chữ số thứ n-1, ...). Sau đó cảnh sát nhận được thêm thông tin: số biển số là một số nguyên tố. Cảnh sát dựa vào dự đoán của một chuyên gia tin học đưa ra sau khi phân tích các nguồn tin và xác định tập các số có thể là số của biển số: biển số nếu viết trong hệ nhị phân cũng là một số đối xứng. Nhờ vậy mà cảnh sát đã bắt đúng đối tượng. Hãy cho biết các số mà chuyên gia tin học đã xác định mà số biển xe mà ông ta đã dự đoán đúng.

ĐỀ SỐ 2

Bài 1. Tính giá trị biểu thức

Cho hai số thực c và d. Tính:

trong đó x1-nghiệm lớn, x2-nghiệm bé của phương trình:

x2-3x-cd=0

Bài 2. Quan hệ

Có N người mang tên tương ứng là 1, 2, ..., N và tình trạng quen biết của N người này được cho bởi mảng đối xứng A[1..N,1..N] trong đó A[i,j]=A[j,i]=1 nếu i quen j và bằng 0 nếu i không quen j. Hãy xét xem liệu có thể chia N người đó thành 2 nhóm mà trong mỗi nhóm hai người bất kì đều không quen nhau?

Dữ liệu vào được cho bởi file QUANHE.INP trong đó dòng thứ nhất ghi số nguyên dương N<=100, trong N dòng tiếp theo, dòng thứ i ghi N số A[i,1], ..., A[i,N].

Kết quả ghi ra file QUANHE.OUT như sau:

- Nếu không có thể , ghi dòng chữ KHONG THE

- Nếu có thể, ghi ra hai dòng, dòng thứ nhất tên những người thuộc nhóm 1, dòng thứ hai tên những người thuộc nhóm 2.

ĐỀ SỐ 3

Bài 1. Phân số

Viết chương trình nhập một số thực dương R và một số nguyên dương MAX. Hãy tìm trong số các phân số có dạng P/Q với Q<=MAX phân số gần số R nhất.

Bài 2. Kiến thiết xâu văn bản

Hãy lập chương trình đưa ra file XVB.TXT theo thứ tự từ điển tất cả các dăy có độ dài không lớn hơn n cho trước và được xây dựng từ các chữ số 1,2,3 sao cho trong mỗi dãy không có bất kì hai dãy con liền kề nào giống nhau. Cho biết có cả thảy bao nhiêu dãy như vậy.

Nói rằng, hai dãy a1...ap và b1...bq là được sắp theo thứ tự từ điển và kí hiệu: a1a2...ap<b1b2...bq, nếu: Tồn tại i≥1 mà ai<bi và đồng thời với mọi 1≤j≤i thì aj=bj hoặc là nếu q>p thì với mọi 1≤j≤p ta có aj=bj.

ĐỀ SỐ 4

Bài 1. Điểm trên mặt phẳng

Cho các số thực a, b, c, d, e, f, g, h. Biết rằng hai điểm (e,f) và (g,h) khác nhau và các điểm (a,b); (c,d) không nằm trên đường thẳng l đi qua hai điểm (e,f) và (g,h). Đường thẳng l chia mặt phẳng làm hai nửa mặt phẳng . Hai điểm (a,b) và (c,d) có vị trí như thế nào so với đường thẳng l?

Bài 2. Chia vật

Có bao nhiêu cách chia M vật cho N người sao cho sao cho người trước không ít hơn người sau.

M,N nhập từ bàn phím. Kết quả đưa ra file văn bản.

ĐỀ SỐ 5

Bài 1. Tìm nghiệm phương trình siêu việt

Tìm nghiệm của phương trình siêu việt sau:

f(x) = 0 với f(x) = x3 + ex

trong khoảng [-1,0] với độ chính xác 10-6.

Bài 2. Đặt phép tính

Cho số tự nhiên n. Hãy đặt các dấu + hoặc - vào giữa các chữ số nào đó của 1,2,3,4,5,6,7,8,9 viết theo thứ tự đã cho để tạo ra một biểu thức có giá trị bằng n.

Ví dụ cho n=122 thì kết quả có thể nhận được là: 12+34-5-6+78+9

Nếu không tìm được các dãy như vậy thì hãy cho thông báo.

ĐỀ SỐ 6

Bài 1. Trò chơi bốc sỏi

Có một đống sỏi gồm số lượng nguyên không âm viên sỏi. Mỗi đối thủ trong một lần bốc phải bốc thực sự một số (≥1) viên sỏi ra khỏi đống sỏi: số sỏi tối đa được bốc bị hạn chế bởi một lượng tối đa nào đó. Ai bốc cuối cùng sẽ giành chiến thắng. Hãy xây dựng chương trình cho phép thể hiện trò chơi trên trong đó một đấu thủ là máy tính và chương trình thể hiện chiến thuật thắng cho máy tính.

Bài 2. Chu trình đơn hoạch

Một chu trình được gọi là đơn hoạch nếu có thể vẽ nó bằng chỉ một nét mà không phải nhấc bút khỏi giấy và nét cuối cùng quay trở về đỉnh xuất phát.

Một đồ thị gồm có n đỉnh có thể biểu diễn bằng một ma trận vuông cấp n, đó là ma trận nối - phần tử aij của ma trận bằng 1 nếu đỉnh i được nối với đỉnh j bằng một cạnh nào đó không chứa các đỉnh khác và bằng 0 trong trường hợp ngược lại (i,j = 1,...,n). Đồ thị được cho bởi file 'DOTHI.TXT'.

Cho ma trận nối của một đường có n đỉnh. Hỏi có tồn tại một chu trình hoạch đơn hay không? Nếu có hãy chỉ ra dãy số hiệu các đỉnh theo thứ tự đi qua khi vẽ.

ĐỀ SỐ 7

Bài 1. Phân tích số

Lập chương trình tính số cách phân tích số tự nhiên n>1 thành tổng các số tự nhiên nhỏ hơn nó. In ra tất cả các cách phân tích đó (mỗi phân tích chỉ kể đúng một lần, ví dụ 4+3+1 và 1+4+3 chỉ là một phân tích).

Bài 2. Chia kẹo

Có n gói kẹo, N<=200, các gói kẹo được đánh số từ 1 đến N, gói kẹo thứ i có A[i] cái kẹo, các số A[1], ..., A[N] đều nguyên dương và không quá 200. Hãy tìm một cách chia các gói kẹo làm hai nhóm sao cho tổng số kẹo trong các nhóm sai khác nhau ít nhất.

Dữ liệu vào được cho bởi file KEO.INP trong đó dòng thứ nhất ghi số N và trong các dòng tiếp theo, mỗi dòng ghi 10 số lần lượt từ A[1] đến A[N].

Kết quả ghi ra file KEO.OUT như sau: dòng thứ nhất ghi số kẹo chênh lệch giữa hai nhóm, tiếp theo là một nhóm dòng ghi số hiệu các gói kẹo thuộc nhóm thứ nhất, mỗi dòng ghi 20 số hiệu, cuối cùng là một nhóm dòng ghi số hiệu các gói kẹo thuộc nhóm thứ hai, mỗi dòng ghi 20 số hiệu.

ĐỀ SỐ 8

Bài 1. Cân một vật

Cho n quả cân với khối lượng tương ứng d1,...,dn. Cho vật với khối lượng bất kì. Hỏi có cân được vật đó trên bàn cân hai đĩa với các quả cân trên hay không?

Cho biết các trọng lượng đó đều là nguyên.

Bài 2. Ghép xâu

Cho N xâu kí tự A1, A2, ..., An, n<=100, độ dài mỗi xâu Ai không quá 10, và một xâu kí tự S. Hãy tìm mọi cách biểu diễn S dưới dạng ghép của các xâu kí tự Ai, mỗi xâuSi có thể xuất hiện trong biểu diễn đó nhiều lần.

Dữ liệu vào được cho bởi file XAU.INP trong đó dòng thứ nhất ghi xâu S, dòng thứ hai ghi số N, trong N dòng tiếp theo, dòng thứ i ghi xâu Ai.

Kết quả ghi ra file XAU.OUT như sau:

- Nếu không có biểu diễn, ghi dòng chữ KHONG CO

- Nếu có biểu diễn, ghi mỗi biểu diễn trên một dòng theo quy cách như ví dụ.

Ví dụ:

XAU.INP XAU.OUT

Abcdef

11

ab

cd

ef

abc

def

a

c

d

f A[1]A[2]A[3]

A[1]A[2]A[10]A[11]

A[1]A[8]A[5]

A[1]A[8]A[9]A[3]

A[1]A[8]A[9]A[10]A[11]

A[4]A[5]

A[4]A[9]A[3]

A[4]A[9]A[10]A[11]

A[6]A[7]A[2]A[3]

A[6]A[7]A[2]A[2]A[10]A[11]

A[6]A[7]A[8]A[5]

A[6]A[7]A[8]A[9]A[3]

A[6]A[7]A[8]A[9]A[10]A[11]

ĐỀ SỐ 9

Bài 1. Đường đi ngắn nhất

Cho một đồ thị N đỉnh, N<=100, có ma trận trọng số không âm C và với mọi i,j, C[i,j]<=100. Cho trước hai đỉnh u và v. Hãy tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v.

Dữ liệu vào cho bởi file DOTHI.INP trong đó dòng thứ nhất ghi ba số N, u, v. Trong N dòng tiếp theo, dòng thứ i ghi N số C[i,1], ..., C[i,N].

Kết quả ghi ra file DOTHI.OUT như sau: dòng thứ nhất ghi độ dài đường đi ngắn nhất từ u đến v; trong các dòng tiếp theo, mỗi dòng ghi một đỉnh của đường đi từ u đến v lần lượt theo thứ tự trên hành trình từ u đến v.

Bài 2. Dãy số

Cho một dãy số, hãy xóa đi một số để dãy còn lại là một dãy đơn điệu tăng dài nhất.

Ví dụ: 5 15 6 2 11 4 5 6 15

 2 4 5 6 15

ĐỀ SỐ 10

Bài 1. Giai thừa

Tính n! (N<=10000). N nhập từ bàn phím. Kết quả ghi ra file văn bản.

Bài 2. Biến đổi xâu

Viết chương trình làm các việc sau:

1. Nhập từ bàn phím hai xâu kí tự S1 và S2.

2. Ta có thể dùng một trong ba loại phép biến đổi sau:

BD1: xoá một kí tự nào đó trong xâu.

BD2: thêm một kí tự nào đó vào một vị trí nào đó của xâu.

BD3: thay một kí tự nào đó trong xâu bằng một kí tự khác.

Hãy thông báo ra file OUT.TXT liệu có thể dùng một số phép biến đổi thuộc ba loại trên để biến đổi S1 thành S2 không, quy cách thông báo như sâu: ví dụ S1=tsgldds, thì ta phải thông báo như sau:

Biến đổi được

ptslddf - xoá p/1 => tslddf

tslddf - thêm g/3 => tsglddf

tsglddf - thay f/7/s => tsgldds

3. Trong trường hợp biến đổi được, hãy tìm cách dùng ít phép biến đổi nhất và thông báo tiếp vào file OUT.TXT theo quy cách như trên.

ĐỀ SỐ 11

Bài 1. Mã đi tuần

Một con mã xuất phát từ một ô bàn cờ 8x8, hỏi con mã đó có thể đi hết cả bàn cờ mà không đi lặp lại ô đã đi qua hay không?

Chỉ cần đưa ra một cách đi. Kết quả ghi vào file RESULT.TXT.

Bài 2. Sắp xếp

Để quản lý nhân sự ở một tỉnh nọ có khoảng 1 triệu người, hãy sắp xếp tuổi của dân cư ở đây theo thứ tự từ nhỏ đến lớn. Biết rằng tuổi ở đây chỉ nằm trong khoảng từ 1 đến 100.

Tuổi của dân cư được cho vào từ file TUOI.INP viết liên tiếp nhau, cách nhau ít nhất một dấu cách hoặc một dấu xuống dòng. Kết quả đưa ra file TUOI.OUT cấu trúc như file vào nhưng đã được sắp xếp.

Ví dụ:

TUOI.INP TUOI.OUT

1 2 20 4 45 62 3 2 4 55 2 4 5 100 1 2 2 2 3 4 4 4 5 20 45 55 62 100

ĐỀ SỐ 12

Bài 1. Ghép số nguyên tố

Giả sử dóy A là dóy tăng dần các số nguyên tố

2, 3, 5, 7, ...

Ta lập dóy B bằng cỏch viết ghộp từng cặp số liền kề của dóy A với nhau:

23, 57, 1113, 1719, ...

C là dóy nhận từ B bằng cỏch gạch đi các số không là nguyên tố.

Hóy tỡm j số hạng đầu của dóy C, j<=300. Số j nhập từ bàn phớm và kết quả viết ra file NT.TXT, mỗi số hạng một dũng.

Bài 2. Xếp việc

Bắt đầu từ thời điểm 0, một người làm N việc với số hiệu từ 1 đến N, N<=200. Với 1<=i<=N, việc i cần làm trong T[i] đơn vị thời gian và mỗi đơn vị thời gian từ thời điểm 0 đến lúc bắt đầu làm nó, người đó bị phạt một lượng tiền C[i]. Khi đã làm một việc nào thì phải làm xong mới chuyển sang việc làm khác. Hãy thu xếp trình tự các việc làm sao cho tổng số tiền bị phạt là ít nhất.

Dữ liệu vào được cho bởi file XEPVIEC.INP trong đó dòng thứ nhất ghi số nguyên dương N. Với 1<=i<=N, dòng thứ i+1 ghi hai số thực T[i] và C[i].

Dữ liệu ra ghi trong file XEPVIEC.OUT. Dòng thứ nhất ghi tổng số tiền bị phạt. Từ dòng thứ hai ghi mỗi dòng 1 cặp số: số thứ nhất là số hiệu việc, số thứ hai là thời điểm bắt đầu làm việc. Trình tự từ trên xuống dưới là trình tự lần lượt làm các việc.

ĐỀ SỐ 13

Bài 1. Giao dịch

Trờn một lónh thổ cú N thành phố đánh số từ 1đến N (N<=100). Trên lónh thổ cú một mạng giao thụng một chiều. Một cụng ty nọ muốn đặt các trạm giao dịch để từ đó hàng hoá của công ty có thể đi đến tất cả các thành phố.

1. Hóy cho biểt cụng ty cần đặt ít nhất bao nhiêu trạm giao dịch để đạt được mục đích trên.

2. Hóy cho biết cú thể loại bỏ được nhiều nhất bao nhiêu con đường mà số ít nhất trạm giao dịch cần thiết vẫn không đổi.

3. Hóy cho biết cần thờm vào mạng giao thụng ớt nhất bao nhiờu con đường nối trực tiếp nữa để chỉ cần một trạm giao dịch là đủ.

Dữ liệu vào từ file GIAODICH.INP bao gồm:

- Dũng đầu là số N.

- Cỏc dũng tiếp theo ghi các con đường với cặp số i j cách nhau 1 dấu cách nghĩa là có con đường từ i đến j.

Kết quả ra file GIAODICH.OUT bao gồm:

- Cõu 1: dũng1 là số trạm giao dịch ớt nhất. Cỏc dũng sau ghi chỉ số cỏc thành phố cần xõy dựng trạm giao dịch, cỏch nhau ớt nhất một dấu cỏch.

- Cõu 2: dũng tiếp theo ghi số con đường nhiều nhất có thể loại. Mỗi dũng tiếp theo ghi cặp số P Q cỏch nhau 1 dấu cỏch thể hiện con đường đó.

- Cõu 3: dũng tiếp theo ghi số con đường ít nhất cần xây dựng. Mỗi dũng tiếp theo ghi cặp số x y cỏch nhau 1 dấu cách thể hiện con đường đó.

Bài 2. Xoá số

Một số nguyên dương N rất lớn có thể được cho bởi số nguyên dương P, P số nguyên dương A1, ..., Ap và P xâu kí tự chỉ gồm các chữ số thập phân S1, ..., Sp. Khi đó N sẽ nhận được bằng cách viết S1 liên tiếp A1 lần rồi S2 liên tiếp A2 lần, ..., Sp liên tiếp Ap lần. Ví dụ với P=3, A1=3, S1=123, A2=4, S2=0, A3=2, S3=45 thì ta có N=12312312300004545.

Giả sử số N được cho như vậy và cho một số nguyên dương K không vượt quá số chữ số của N, hãy tìm cách gạch đi K chữ số của N để nhận được một số có giá trị nhỏ nhất.

Các số P, K, A1, ..., Ap, các xâu S1, ..., Sp có thể nhập từ file hoặc từ bàn phím. Thông báo số nhận được ra màn hình.

ĐỀ SỐ 14

Bài 1. Lá bài

Có N lá bài với các số hiệu là 1, 2, ..., N, N<=50, trên lá bài i ghi một số nguyên dương F[i], 1<=F[i]<=N. Hãy tìm một số nhiều nhất các lá bài sao cho tập các số hiệu của chúng trùng với tập các số ghi trên các lá bài đó.

Dữ liệu vào cho bởi file LABAI.INP trong đó dòng thứ nhất ghi số N nguyên dương. Trong các dòng tiếp theo ghi mỗi số 10 số (cho tới khi hết N số) lần lượt là các số ghi trong các lá bài từ lá bài 1 đến lá bài N.

Dữ liệu ra ghi ra file LABAI.OUT, trong đó dòng thứ nhất ghi số lượng lá bài. Trong các dòng tiếp theo, mỗi dòng ghi 10 số hiệu của các lá bài được chọn, các số hiệu ghi theo thứ tự tăng dần cho đến hết.

Ví dụ

LABAI.INP LABAI.OUT

14

6 5 1 3 4 2 8 10 7 9

3 2 1 9 10

1 2 3 4 5 6 7 8 9 10

Bài 1. Lịch gia công tuần tự hai máy

Có n chi tiết {1,2,...,n}, mỗi chi tiết cần được lần lượt gia công trên 2 máy. Đầu tiên qua máy A rồi đến máy B.

Giả thiết thời gian gia công trên máy A là ai, thời gian gia công trên máy B là bi. Hãy xếp lịch gia công để thời gian hoàn thành tất cả các chi tiết là sớm nhất.

Dữ liệu vào từ file THOIGIAN.TXT bao gồm:

- Dòng đầu là số chi tiết N

- N số tiếp theo là thời gian từng chi tiết thực hiện trên máy A

- N số tiếp theo là thời gian từng chi tiết thực hiện trên máy B

Kết quả ra file LICH.TXT bao gồm:

- Dòng đầu là thời gian thực hiện T

- N số tiếp theo là thứ tự gia công trên máy A

- N số tiếp theo là thứ tự gia công trên máy B

ĐỀ SỐ 15

Bài 1. Dãy ngoặc

Một dóy ngoặc đúng là một dóy cỏc ký tự "(", ")", "[" và "]" được định nghĩa như sau:

I. Dóy rỗng là một dóy ngoặc đúng

II. Nếu A là dóy ngoặc đúng thỡ (A) và [A] cũng là những dóy ngoặc đúng

III. Nếu A và B là những dóy ngoặc đúng thỡ AB cũng là dóy ngoặc đúng.

Vớ dụ cỏc dóy: (), [], ([])()[()] là những dóy ngoặc đúng.

Yờu cầu: Cho xõu S chỉ gồm cỏc ký tự "(", ")", "[" và "]". Hóy tỡm cỏch bổ sung một số tối thiểu cỏc ký tự cần thiết để nhận được một dóy ngoặc đúng. Cho biết dóy ngoặc đúng đó.

Dữ liệu: Vào từ file văn bản BRACKET.INP, chỉ gồm 1 dũng chứa xõu S khụng quỏ 200 ký tự

Kết quả: Ghi ra file văn bản BRACKET.OUT, chỉ gồm 1 dũng ghi biểu thức ngoặc đúng tương ứng với xâu S.

Vớ dụ:

BRACKET.INP BRACKET.OUT BRACKET.INP BRACKET.OUT

([(]

()[()]

([[((())())]()])[]

([[((())())]()])[]

Bài 1. Đua ngựa

Ở thời Xuân Thu, vua Tề và Điền Kỵ thường hay tổ chức đua ngựa từng cặp với nhau. Mỗi một loại ngựa có một hệ số khác nhau. Trong cuộc đua, con ngựa nào có hệ số cao hơn thì sẽ thắng, nếu có hệ số ngang nhau thì sẽ về đích cùng một lúc. Ai có tổng số trận thắng nhiều hơn thì sẽ thắng chung cuộc. Số trận <=1000 trận. Bạn hãy giúp Điền Kỵ sắp xếp các lượt đấu để đạt số trận thắng cao nhất có thể.

Dữ liệu vào từ file HESO.TXT bao gồm:

- Dòng đầu là số lượng ngựa: n

- Dòng thứ hai có n số , số thứ i là hệ số của con ngựa thứ i của Điền Kỵ.

- Dòng thứ hai có n số , số thứ i là hệ số của con ngựa thứ i của vua Tề.

Kết quả ghi vào file LICH.TXT gồm n số, số thứ i là chỉ số ngựa của Điền Kỵ đem đấu với con ngựa thứ i của vua Tề.

Ví dụ:

HESO.TXT

3

4 6 2

9 3 5

LICH.TXT

3 1 2

ĐỀ SỐ 16

Bài 1. Hòm phiếu

Trờn một lónh thổ cú n thành phố được đánh số từ 1 đến n. Trong một cuộc chưng cầu dân ý cần đặt một số hũm phiếu tại một số thành phố ở mọi người từ n thành phố đi bỏ phiếu. Tuy nhiên, để số người đi bỏ phiếu là nhiều nhất có thể được, người ta muốn đặt cỏc hũm phiếu sao cho quóng đường người phải đi xa nhất là ngắn nhất có thể được.

Hóy tỡm cỏch đặt các hũm phiếu sao cho đạt được mục đích đó.

INPUT: file TP.INP bao gồm:

- n, k (số thành phố và số thành phố cần đặt hũm phiếu)

- ma trận khoảng cỏch giữa cỏc thành phố.

OUTPUT: file TP.OUT bao gồm:

- quóng đường mà người phải đi xa nhất.

- lần lượt các thành phố cần đặt hũm phiếu.

Vớ dụ:

TP.INP TP.OUT

4 2

0 8 0 9

8 0 2 0

0 2 0 2

9 0 2 0 2

1 3

Bài 2. Xin chữ ký

Giám đốc công ty trách nhiệm hữu hạn muốn xin chữ ký kiến trỳc sư trưởng thành phố phê duyệt dự án xây dựng của công ty. Ông kiến trúc sư chỉ ký vào giấy khi bà thư ký đó ký duyệt vào giấy phộp. Bà thư ký làm việc ở tầng thứ M của túa nhà gồm M tầng được đánh số từ thấp lên cao, mỗi tầng có N phũng được đánh số từ trỏi sang phải. Mỗi phũng cú 1 nhõn viờn làm việc. Bà thư ký chỉ ký khi cú ớt nhất một nhõn viờn tầng thứ M đó ký duyệt. Một nhõn viờn chỉ ký khi một trong cỏc điều kiện sau thỏa món:

- Nhõn viờn ở tầng 1

- Giấy phép được ký xỏc nhận bởi nhõn viờn ở cựng số phũng tầng dưới

- Giấy phép được ký xỏc nhận bởi nhõn viờn ở phũng liền kề (phũng liền kề là phũng cú chỉ số phũng sai khỏc 1)

Mỗi nhõn viờn khi ký xỏc nhận đều đũi hỏi một khoản lệ phớ. Hóy tỡm cỏch xin được chữ ký kiến trỳc sư trưởng với chi phí nhỏ nhất

Dữ liệu vào: File văn bản SIGN.INP

Dũng đầu chứa 2 số M, N

Dũng thứ i trong M dũng tiếp chứa N số cij là chi phớ phải trả cho nhõn viờn phũng j thuộc tầng i

Dữ liệu ra: File văn bản SIGN.OUT

Dũng đầu ghi 2 số F, K là chi phí phải trả và số phũng đi qua

Cỏc dũng tiếp theo ghi chỉ số cỏc phũng đi qua, mỗi chỉ số ghi trên một dũng

Vớ dụ:

SIGN.INP SIGN.OUT

3 4 8 5

10 10 1 10 3

2 2 2 10 3

1 10 10 10 2

1

1

ĐỀ SỐ 17

Bài 1. Dò mìn

Cho một bói mỡn kớch thước mxn ụ vuụng, trờn một ụ cú thể cú chứa một quả mỡn hoặc khụng, để biểu diễn bản đồ mỡn đó, người ta có hai cách:

• Cách 1: dùng bản đồ đánh dấu: sử dụng một lưới ô vuông kích thước mxn, trên đó tại ô (i, j) ghi số 1 nếu ô đó có mỡn, ghi số 0 nếu ụ đó không cú mỡn

• Cách 2: dùng bản đồ mật độ: sử dụng một lưới ô vuông kích thước mxn, trên đó tại ô (i, j) ghi một số trong khoảng từ 0 đến 8 cho biết tổng số mỡn trong cỏc ụ lõn cận với ụ (i, j) (ụ lõn cận với ụ (i, j) là ụ cú chung với ụ (i, j) ớt nhất 1 đỉnh).

Giả thiết rằng hai bản đồ được ghi chính xác theo tỡnh trạng mỡn trờn hiện trường.

Ví dụ: Bản đồ đánh dấu và bản đồ mật độ tương ứng: (m = n = 10)

Bản đồ đánh dấu Bản đồ mật độ

1 0 1 0 1 0 1 0 0 0 1 3 1 2 1 3 1 2 2 2

0 1 0 0 0 1 0 0 1 1 2 3 3 4 3 3 2 2 2 2

0 0 1 0 1 0 0 0 0 1 2 4 4 5 3 3 2 3 5 3

0 1 1 1 1 0 0 1 1 0 2 4 6 6 3 2 2 2 4 3

0 1 1 1 0 0 0 1 0 1 2 3 6 5 5 2 4 3 5 1

0 0 0 1 0 1 0 1 0 0 3 5 6 3 4 2 5 3 5 3

1 1 1 0 0 1 1 0 1 1 2 3 3 3 5 3 5 4 4 2

1 0 0 1 0 1 0 1 0 1 2 5 4 3 5 5 7 5 6 3

0 0 1 0 1 1 1 1 1 0 2 3 1 3 4 4 5 3 3 2

1 0 0 0 0 1 0 0 0 0 0 2 1 2 3 3 4 3 2 1

Về nguyờn tắc, lỳc cài bói mỡn phải vẽ cả bản đồ đánh dấu và bản đồ mật độ, tuy nhiên sau một thời gian dài, khi người ta muốn gỡ mỡn ra khỏi bói thỡ vấn đề hết sức khó khăn bởi bản đồ đánh dấu đó bị thất lạc !!. Cụng việc của cỏc lập trỡnh viờn là: Từ bản đồ mật độ, hóy tỏi tạo lại bản đồ đánh dấu của bói mỡn.

Dữ liệu: Vào từ file văn bản MINE.INP, các số trên 1 dũng cỏch nhau ớt nhất 1 dấu cỏch

• Dũng 1: Ghi 2 số nguyờn dương m, n (2  m, n  80)

• m dũng tiếp theo, dũng thứ i ghi n số trờn hàng i của bản đồ mật độ theo đúng thứ tự từ trái qua phải.

Kết quả: Ghi ra file văn bản MINE.OUT, các số trên 1 dũng ghi cỏch nhau ớt nhất 1 dấu cỏch

• Dũng 1: Ghi tổng số lượng mỡn trong bói

• m dũng tiếp theo, dũng thứ i ghi n số trờn hàng i của bản đồ đánh dấu theo đúng thứ tự từ trái qua phải.

Vớ dụ:

MINE.INP MINE.OUT

10 15

0 3 2 3 3 3 5 3 4 4 5 4 4 4 3

1 4 3 5 5 4 5 4 7 7 7 5 6 6 5

1 4 3 5 4 3 5 4 4 4 4 3 4 5 5

1 4 2 4 4 5 4 2 4 4 3 2 3 5 4

1 3 2 5 4 4 2 2 3 2 3 3 2 5 2

2 3 2 3 3 5 3 2 4 4 3 4 2 4 1

2 3 2 4 3 3 2 3 4 6 6 5 3 3 1

2 6 4 5 2 4 1 3 3 5 5 5 6 4 3

4 6 5 7 3 5 3 5 5 6 5 4 4 4 3

2 4 4 4 2 3 1 2 2 2 3 3 3 4 2

80

1 0 1 1 1 1 0 1 1 1 1 1 1 1 1

0 0 1 0 0 1 1 1 0 1 1 1 0 1 1

0 0 1 0 0 1 0 0 1 1 1 0 0 1 1

1 0 1 1 1 0 0 1 0 0 0 0 0 1 1

1 0 0 0 1 1 1 0 0 1 0 0 1 0 1

0 0 0 0 1 0 0 0 0 1 1 0 1 0 0

0 1 1 0 0 1 0 0 1 1 0 0 1 0 0

1 0 1 0 1 0 1 0 1 1 1 1 0 1 0

0 1 1 0 1 0 0 0 0 0 1 1 1 1 1

1 1 1 1 1 0 1 1 1 1 0 0 0 0 1

Bài 2. Tô màu lưới

Một lưới toạ độ gồm M dòng và N cột. Gọi G là một tập hợp các điểm nào đó trên các mắt của lưới. Cần tô màu các điểm của G bằng 2 màu xanh, đỏ sao cho nhìn theo bất kỳ dòng nào cũng như cột nào của lưới, ta đều có số điểm màu xanh và màu đỏ hoặc bằng nhau, hoặc chênh nhau 1.

Dữ liệu vào được cho trong một file văn bản LUOI.INP trong đó dòng đầu ghi các giá trị M, N (cách nhau ít nhất một dấu trắng), M dòng tiếp theo, mỗi dòng ghi thông tin một dòng của lưới dưới dạng một xâu nhị phân độ dài N (các kí tự 0, 1 viết liền nhau), với quy ước kí tự 1 ghi nhận vị trí của điểm của G và kí tự 0 ghi nhận các vị trí còn lại.

Kết quả cần đưa ra file văn bản LUOI.OUT, trong đó dòng đầu ghi các giá trị M, N (cách nhau một dấu trắng), M dòng sau, mỗi dòng ghi một xâu độ dài N gồm các kí tự 0, 1, 2 viết liền nhau với quy ước: kí tự 1 ghi nhận vị trí các điểm xanh, kí tự 2 ghi nhận vị trí các điểm đỏ, kí tự 0 ghi nhận các vị trí khác.

Thí dụ lưới và tập hợp G cho trong hình dưới đây:

LUOI.INP

5 11

01010010001

10100001000

01010100001

00000001010

10000100000

ĐỀ SỐ 18

Bài 1. Phân phối kênh

Công ty dịch vụ mạng máy tính cần phân phối kênh hoạt động phục vụ n (n<1000) yêu cầu của khách hàng đánh số từ 1 đến n. Với mỗi khách hàng thứ i ta biết khoảng thời gian yêu cầu sử dụng kênh là (si, ti), i=1, 2, ..., n (khách hàng sẽ sử dụng kênh từ thời điểm si đến thời điểm ti). Thời gian chuyển giao quyền sử dụng kờnh từ khỏch hàng này cho khỏch hàng khác là không đáng kể. Như vậy, nếu hai khách hàng nào đó được bố trí làm việc trên cùng một kênh thỡ cỏc khoảng thời gian sử dụng của họ chỉ cú thể cú nhiều nhất một điểm chung.

Yờu cầu: Hóy tỡm cỏch phõn phối sử dụng ớt kờnh nhất.

Dữ liệu: Vào từ file văn bản CHANEL.INP có cấu trúc như sau:

• dũng đầu tiên ghi số n;

• dũng thứ i trong số n dũng tiếp theo ghi 2 số nguyờn dương si, ti, i = 1, 2, ..., n.

Kết quả: Ghi ra file văn bản với tên CHANEL.OUT theo cấu trúc sau:

• dũng đầu tiên ghi số lượng kênh cần sử dụng p;

• mỗi dũng thứ i trong số p dũng tiếp theo chứa cỏc chỉ số của cỏc khỏch hàng sử dụng kờnh thứ i, i = 1, 2, ..., p.

Vớ dụ: file CHANEL.INP và CHANEL.OUT tương ứng có thể có dạng:

CHANEL.INP

7

0 3

3 5

6 8

0 7

7 8

0 2

2 6

CHANEL.OUT

3

1 2 3

6 7 8

4

Bài 1. Mua vé tàu hỏa

Tuyến đường sắt từ thành phố A đến thành phố B đi qua một số nhà ga. Tuyến đường có thể biểu diễn bỏi một đoạn thẳng, các nhà ga là các điểm ở trên nó. Tuyến đường sắt bắt đầu từ A và kết thúc ở B, vì thế các nhà ga sẽ được đánh số bắt đầu từ A (có số hiệu là 1) và B là nhà ga cuối cùng.

Giá vé đi lại giữa 2 nhà ga chỉ phụ thuộc vào khoảng cách giữa chúng. Cách tính giá vé được cho trong bảng sau đây.

Khoảng cách giữa hai nhà ga - X Giá vé

0 < X ≤ L1 C1

0 < L1 ≤ L2 C2

0 < L2 ≤ L3 C3

Vé để đi thảng từ nhà ga này đến nhà khác chỉ có thể đặt mua nếu khoảng cách giữa chúng không vượt quá L3 . Vì thế nhiều khi để đi từ nhà ga này đến nhà khác ta phải đặt mua một số vé.

Ví dụ: Trên tuyến đường sắt cho trên hình 1, để đi từ nhà ga 2 đến nhà ga 6 không thể mua vé đi thẳng. Có nhiều cách đặt mua vé để đi từ ga 2 đến ga 8. Chẳng hạn, đặt mua vé từ ga 2 đến ga 3 mất chi phí C2 và sau đó đi từ ga 3 đến ga 6 mất chi phí C3 , và chi phí tổng cộng từ để mua vé từ ga 2 đến ga 6 theo cách này là C2 + C3. Lưu ý là mặc dù khoảng cách từ ga 2 đến ga 6 là 2*L2 nhưng không thể đặt mua 2 vé với giá C2 để đi từ ga 2 đến ga 6 với chi phí tổng cộng là 2*C2 , vì mỗi vé chỉ có giá trị đi lại giữa 2 nhà ga nào đó.

Yêu cầu: Tìm cách đặt mua vé để đi lại giữa 2 nhà ga cho trước với chi phí mua vé là nhỏ nhất.

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

• Dòng đầu tiên ghi các số nguyên L1, L2, L3, C1, C2, C3 (1 ≤ L1< L2 < L3 ≤ 109, 1≤C1< C2 < C3 ≤ 109) theo đúng thứ tự vừa liệt kê.

• Dòng thứ hai chứa số lượng nhà ga N(1 ≤ N ≤ 10000)

• Dòng thứ ba ghi 2 số nguyên s,t là các chỉ số của 2 nhà ga cần tìm cách đặt mua vé với chi phí nhỏ nhất để đi lại giữa chúng.

• Dòng thứ i trong sô N-1 dòng tiếp theo ghi số nguyên là khoảng cách từ nhà ga A (ga 1) đến nhà ga thứ i+1 (i=1,2,..,N-1). Chi phí đi từ nhà ga đầu tiên A đến nhà ga cuối cùng B không vượt quá 109.

Kết quả: Ghi ra File RTICKET.OUT chi phí nhỏ nhất tìm được.

Ví dụ:

RTICKET.INP RTICKET.OUT

3 6 8 20 30 40

7

2 6

3

7

8

13

15

23 70