Đề bài - Lời giải
2008
Hanoi-Amsterdam Olympiad in
Informatics
Phạm Nam Long
Phạm Hải Minh
Lê Đôn Khuê
Ngô Minh Đức
Nguyễn Hoành Tiến
http://vnoi.info
Biên soạn: Ngô Minh Đức
10/08/2008
v1.0
Hanoi-Amsterdam Olympiad in Informatics
2008
Tổng quan về ngày thi thứ nhất
( 09 – 08 – 2008 )
Bài thi
Bài 1
Bài 2
Bài 3
Tên bài
Gấp tiền
Mã và tốt
Giải phóng
mặt bằng
Giới hạn thời
gian
0.5s/test
2s/test
3s/test
Tổng số điểm
100
100
100
http://vnoi.info
Trang 2
Hanoi-Amsterdam Olympiad in Informatics
Gấp tiền
2008
Mã bài: NOTE
Tác giả: Phạm Nam Long
LSM là cố vấn cao cấp của HAOI 2008 và được giao nhiệm vụ ra đề thi. Hạn nộp bài đang đến gần mà LSM
không có một ý tưởng nào. Thư kí Lola thúc giục ngày đêm cộng thêm khoản tiền bồi thường nếu không
hoàn thành công tác đúng hạn làm LSM hết sức lo lắng. Trong lúc tuyệt vọng, LSM vô tình gập đôi liên tiếp
tờ tiền 100$ trước mặt. Khi mở tờ tiền ra, trong tay LSM là tờ giấy bạc có các vết gấp lên xuống. Đột nhiên,
một ý tưởng lóe sáng: nếu có cách nào đó xác định được nếp gấp thứ p tính từ trái sang phải của tờ tiền tiền
là lên hay xuống, thì đây sẽ là một bài toán hay cho các thí sinh của HAOI 2008. Hãy giúp LSM thoát khỏi
tình thế khó khăn này nhé!
Tờ tiền có hình dạng chữ nhật và luôn được thực hiện sao cho mép trái được gập đè lên mép phải. LSM thực
hiện gấp như vậy f lần. Tuy nhiên trong thực tế, tới một lúc nào đó đồng tiền sẽ không thể gấp được do quá
dày, nhưng chúng ta bỏ qua thực tế này và tờ tiền vẫn được gấp đôi chính xác sau f lần.
Dữ liệu
Gồm nhiều dòng mỗi dòng chứa đúng 2 số nguyên ngăn cách nhau bởi dấu cách f và p tương ứng
là số lần gấp tờ tiền và vị trí nếp gấp cần xác định. (1 ≤ f ≤ 31. p thỏa mãn không vượt quá số lượng
nếp gấp được tạo ra sau f lần gấp)
Dữ liệu được kết thúc bởi 2 số 0 và không yêu cầu in ra kết quả cho 2 số này.
Kết quả
Với mỗi dòng tương ứng với dữ liệu vào, in ra một kí tự duy nhất ở mỗi dòng: U cho nếp gấp lên trên và D
cho nếp gấp xuống dưới.
Ví dụ
Dữ liệu
2 1
2 2
2 3
0 0
Kết quả
U
D
D
http://vnoi.info
Trang 3
Hanoi-Amsterdam Olympiad in Informatics
2008
Lời giải
Xây dựng hàm isUp(f, p) cho biết với f lần gấp thì nếp gấp thứ p có phải là nếp gấp lên hay không.
Nhận xét:
2^(f-1)
Nếu p là nếp gấp chính giữa, hay p = 2f-1 thì isUp(f, p)=false (p luôn là nếp gấp xuống).
Nếu p thuộc nửa phải của tờ giấy, hay p > 2f-1 thì isUp(f, p) = isUp(f-1, p-2f-1) (nếp gấp p tương ứng
với nếp gấp p-2f-1 khi chỉ dùng f-1 lần gấp).
Nếu p thuộc nửa trái của tờ giấy, hay p > 2f-1 thì isUp(f, p)=not isUp(f-1, 2f-1-p) (nếp gấp p tương
ứng với nếp gấp 2f-1-p khi chỉ dùng f-1 lần gấp, nhưng ở trạng thái ngược lại).
Thời gian thực hiện: O(f).
http://vnoi.info
Trang 4
Hanoi-Amsterdam Olympiad in Informatics
Mã và tốt
2008
Mã bài: KANDP
Tác giả: Phạm Hải Minh/Lê Đôn Khuê
Trên một bài cờ vua kích thước vô hạn có một con mã và một con tốt. Vị trí của quân mã là (Mx, My), vị trí
của quân tốt là (Tx, Ty), trong đó x là chỉ số dòng và y là chỉ số cột. Quân mã được quyền đi theo 8 hướng
như ở bàn cờ vua chuẩn. Quân tốt chỉ được đi một hướng là đi xuống dưới (từ vị trí (x, y) đến vị trí (x-1, y)).
Hai quân cờ sẽ di chuyển theo lượt, xen kẽ nhau. Khi một quân cờ vào vị trí của quân cờ khác đang đứng thì
quân cờ vừa di chuyển sẽ thắng.
Bạn biết vị trí ban đầu của hai quân cờ, quân cờ nào đi trước. Bạn hãy tính xem quân mã có khả năng thắng
không và nếu thắng thì nó sẽ phải đi ít nhất là bao nhiêu nước.
Dữ liệu
Dòng thứ nhất ghi hai số Mx, My.
Dòng thứ hai ghi hai số Tx, Ty.
Dòng thứ ba ghi 0/1 ứng với quân mă đi trước hoặc quân tốt đi trước.
Kết quả
Dòng thứ nhất ghi YES/NO tương ứng với quân mă có khả năng thắng hoặc không có khả năng
thắng.
Nếu dòng thứ nhất là YES thì dòng thứ hai ghi số bước ít nhất.
Giới hạn
Mx, My, Tx, Ty là các số nguyên có trị tuyệt đối nhỏ hơn hoặc bằng 1000. Trong 50% số test, Mx, My, Tx,
Ty có trị tuyệt đối nhỏ hơn hoặc bằng 50.
Ví dụ
Dữ liệu
0 0
0 3
0
Kết quả
YES
2
Giải thích
Ở hình vẽ bên dưới, chữ K thể hiện vị trí quân mã, chữ P thể hiện vị trí quân tốt.
http://vnoi.info
Trang 5
Hanoi-Amsterdam Olympiad in Informatics
2008
Lời giải:
Nhận xét: do ta quan tâm đến việc mã ăn tốt nên bước đi cuối cùng phải là của mã.
Xét trường hợp tốt đi trước. Mỗi bước tốt di chuyển theo vector (-1, 0) còn mã di chuyển theo vector (x, y)
trong đó x2+y2=5. Ta có thể coi như tốt đứng yên (di chuyển theo vector (0, 0)) còn mã di chuyển theo
vector (x+1, y). Bằng cách BFS từ vị trí ban đầu của mã, ta sẽ tìm được số bước đi ngắn nhất đến vị trí tốt
đứng.
Trong trường hợp mã đi trước, ta cần duyệt trước một bước đi bình thường của mã (8 hướng). Sau đó với
mỗi bước đi, BFS như trên để tìm số bước ngắn nhất đến vị trí của tốt.
http://vnoi.info
Trang 6
Hanoi-Amsterdam Olympiad in Informatics
Giải phóng mặt bằng
2008
Mã bài: GPMB
Tác giả: Ngô Minh Đức
Chính quyền thành phố KN đang tiến hành mở thêm một tuyến đường mới trong thành phố. Chính quyền có
bản đồ tọa độ của N hộ dân trong khu vực tuyến đường có thể đi qua. Tuyến đường là một đường thẳng đi
qua tọa độ các hộ dân. Các hộ dân được đánh số từ 1 đến N; hộ dân thứ i có diện tích sử dụng là si (m2). Nếu
tuyến đường đi ngang qua hộ dân thứ i, chính quyền cần phải đền bù cho hộ dân này si2+5 (đồng) tiền giải
phóng mặt bằng. Hỏi chính quyền cần phải đền bù nhiều nhất bao nhiêu tiền khi xây dựng tuyến đường?
Dữ liệu
Dòng 1: một số nguyên N là số hộ dân (1 ≤ N ≤ 1500).
Dòng thứ i trong N dòng tiếp theo chứa 3 số nguyên xi, yi, si cho biết tọa độ và diện tích của hộ dân
thứ i (-50 ≤ xi, yi ≤ 50, 30 ≤ si ≤ 500).
Kết quả
In ra một số duy nhất là số tiền nhiều nhất chính quyền phải đền bù khi xây dựng tuyến đường.
Ví dụ
Dữ liệu
5
0 0 1
1 1 2
2 2 4
0 1 5
1 0 3
Kết quả
51
http://vnoi.info
Trang 7
Hanoi-Amsterdam Olympiad in Informatics
Lời giải:
2008
Phát biểu lại bài toán:
Cho n điểm trên mặt phẳng, điểm thứ i có trọng số là si2 + 5 (với các si cho trước). Trọng số của một đường
thẳng là tổng trọng số của các điểm thuộc đường thẳng đó. Đề bài yêu cầu tìm đường thẳng có trọng số lớn
nhất.
Nhận xét: đường thẳng có trọng lớn nhất luôn đi qua ít nhất 2 điểm trong n điểm đã cho.
Xét các đường thẳng đi qua điểm thứ i. Ta sắp xếp các điểm j còn lại theo phương đối với điểm i, bằng cách
sử dụng và so sánh các vector chỉ phương (x[j] - x[i], y[j] - y[i]). Sau khi sắp xếp, mỗi đoạn vector chỉ
phương bằng nhau cho ta một đường thẳng đi qua điểm i. Cộng tất cả trọng số các điểm trong đoạn để thu
được trọng số của đường thẳng và so sánh với kết quả.
Thời gian thực hiện: O(n2logn).
http://vnoi.info
Trang 8
Hanoi-Amsterdam Olympiad in Informatics
2008
Tổng quan về ngày thi thứ hai
( 10 – 08 – 2008 )
Bài thi
Bài 4
Bài 5
Bài 6
Tên bài
HAOI6000
Rạp chiếu
phim
Rước đuốc
Olympic
Giới hạn thời
gian
1s/test
1s/test
3s/test
Tổng số điểm
100
100
100
http://vnoi.info
Trang 9
Hanoi-Amsterdam Olympiad in Informatics
2008
HAOI 6000
Mã bài: HAOI6000
Tác giả: Nguyễn Hoành Tiến
Ngày nay, khi internet đã trở nên vô cùng phổ biến, các cuộc thi đều có xu hướng chuyển sang hình thức thi
on-line, vừa tiết kiệm được chi phí, vừa thu hút được số lượng đông đảo thí sinh. HAOI (Hot Angel On the
Internet – tạm dịch là Thiên thần xinh đẹp trên mạng) là một cuộc thi như vậy. Giống như những cuộc thi
sắc đẹp bình thường, HAOI cũng bao gồm các vòng thi phụ: tài năng, trí tuệ, trang phục truyền thống… Sau
đây là câu hỏi ở phần thi trí tuệ:
Một toà nhà hình chữ nhật được chia thành MxN ô vuông nhỏ. Ở mỗi ô vuông, người ta xây đúng một bức
tường là một trong hai đường chéo của ô đó. Yêu cầu tìm đường đi nhanh nhất từ mặt phía Bắc tới mặt phía
Nam của toà nhà mà không được đi ra ngoài toà nhà?
Xét ví dụ trong hình vẽ bên, có 3 đường đi khác nhau. Trong đó, đường 1 và 3 là ngắn nhất với độ dài 10.
Giả sử bạn gái của bạn đang tham gia HAOI. Bạn hãy lập trình một chương trình giải quyết câu hỏi trên
trong thời gian cho phép để giúp đỡ cô ấy.
Dữ liệu
Dòng đầu tiên là hai số M, N.
MxN số tự nhiên tiếp theo (mỗi số cách nhau ít nhất một khoảng trống) miêu tả trạng thái các bức
tường ở các ô (1,1), (1,2) … (1,N), (2,1), (2,2) … (M,N). Số 0 nếu bức tường nối đỉnh trái trên với
phải dưới, số 1 nếu bức tường nối đỉnh trái dưới và phải trên của ô vuông.
Kết quả
In ra file HAOI.OUT hai số nguyên là độ dài đường đi ngắn nhất và số lượng đường đi có độ dài
như vậy. Trong trường hợp không có đường đi nào, in ra một dòng chứa hai số 0 0.
Giới hạn
http://vnoi.info
Trang 10
Hanoi-Amsterdam Olympiad in Informatics
1 ≤ M, N ≤ 1000
2008
Ví dụ
Dữ liệu
5 5
0 0 1 1
1 1 0 0
0 0 1 1
1 1 0 0
0 0 0 1
1
0
1
0
1
Kết quả
10 2
Lời giải
Xây dựng đồ thị mỗi đỉnh tương ứng với một nửa ô vuông. Hai đỉnh có cạnh nối khi hai nửa ô vuông tương
ứng kề nhau và không có tường ngăn cách.
Vì mỗi đỉnh có bậc không quá 2 nên đồ thị chỉ chứa các “dải” hoặc các “vòng” như hình vẽ:
Vì chúng ta xuất phát từ một đỉnh phía rìa ngoài nên chỉ đi trên các “dải” mà không đi vào “vòng”.
Thuật toán là duyệt: khi ta đứng ở một đỉnh, xem đỉnh nào kề với nó mà chưa được đi đến thì đi tới (luôn có
duy nhất một đỉnh như vậy); bao giờ đi đến một đỉnh nằm ở rìa phía Nam thì cập nhập kết quả tối ưu.
http://vnoi.info
Trang 11
Hanoi-Amsterdam Olympiad in Informatics
Rạp chiếu phim
2008
Mã bài: CINEMA
Tác giả: Lê Đôn Khuê
Megastar là rạp chiếu phim lớn và hiện đại nhất ở Hà Nội. Rạp chiếu này có một phòng chiếu gồm M hàng
ghế, mỗi hàng có N ghế. Để có được vé xem phim, bạn có thể đặt vé qua mạng. Mỗi yêu cầu đặt vé có thể
đặt một lúc nhiều vé. Hiện tại, sau khi nhận được các yêu cầu đặt vé, rạp sẽ sắp xếp bố trí chỗ ngồi cho các
yêu cầu sao cho các chỗ ngồi của mỗi yêu cầu là một vùng liên thông. Một ghế không nằm ở hàng đầu, hàng
cuối, cột trái nhất, cột phải nhất sẽ có 4 ghế ở phía trước, phía sau, phía trái và phía phải được coi là kề với
nó.
Công việc sắp xếp chỗ ngồi này hiện tại được làm hoàn toàn bằng tay. Bạn hãy viết chương trình sắp xếp
chỗ ngồi cho hợp lý nhất.
Dữ liệu
Dòng thứ nhất ghi số M và N.
Dòng thứ hai ghi số K là số yêu cầu đặt vé.
Dòng thứ ba ghi K số là số lượng vé mỗi yêu cầu đã đặt.
Kết quả
Ghi ra M dòng, mỗi dòng N số với ý nghĩa ghế đó dành cho yêu cầu đặt vé thứ i.
Nếu một ghế là trống thì in ra 0.
Giới hạn
1 ≤ M, N ≤ 1000.
Tổng số vé yêu cầu không vượt quá M * N.
Trong 40% số test, M N ≤ 100.
Ví dụ
Dữ liệu
5 4
3
4 5 9
Kết
1 1
1 1
3 3
3 3
3 3
quả
2 2
2 2
3 2
3 0
3 0
http://vnoi.info
Trang 12
Hanoi-Amsterdam Olympiad in Informatics
Lời giải
2008
Bài toán này có nhiều cách để giải, tuy nhiên có 1 cách làm đơn giản như sau:
Xét lần lượt các yêu cầu, với dòng 1, ta sắp xếp chỗ ngồi từ trái sang phải, với dòng 2, ta sắp xếp chỗ từ phải
sang trái, v.v... Cách này sẽ đảm bảo các chỗ ngồi trong mỗi yêu cầu luôn thuộc một miền liên thông.
http://vnoi.info
Trang 13
Hanoi-Amsterdam Olympiad in Informatics
Rước đuốc Olympic
2008
Mã bài: TORCH
Tác giả: Lê Đôn Khuê
Olympic Bắc Kinh 2008 đang diễn ra vô cùng sôi nổi và quyết liệt. Ngay từ lúc này, những nhà tổ chức của
Olympic London 2012 đã tính đến kế hoạch cho lễ rước đuốc của Olympic lần tới. Họ dự định sẽ đi qua N
thành phố. Mỗi thành phố có tọa độ (x, y) trên mặt phẳng. Kế hoạch của lễ rước đuốc là ngọn đuốc sẽ bắt
đầu từ thành phố 1, đi lần lượt giữa các thành phố khác mỗi thành phố đúng 1 lần rồi quay trở lại thành phố
1. Bạn hãy tìm một hành trình để tổng đường đi là nhỏ nhất.
Dữ liệu
Dòng thứ nhất ghi số N.
N dòng tiếp theo, mỗi dòng ghi một cặp số (x, y) là tọa độ của các thành phố
Kết quả
Dòng đầu tiên ghi độ dài của hành trình có đường đi ngắn nhất mà bạn tìm được với ít nhất 3 chữ
số sau dấu phẩy.
Dòng thứ hai ghi N số bắt đầu bằng số 1 và tiếp theo là lần lượt các thành phố trên hành trình.
Giới hạn
1 ≤ N ≤ 100
Tọa độ các thành phố có trị tuyệt đối không quá 105.
Ví dụ
Dữ liệu
4
0 0
1 0
0 5
1 5
Kết quả 1
12.0000
1 2 4 3
Kết quả 2
20.1980
1 4 2 3
Kết quả 3
12.1980
1 2 3 4
Cách tính điểm
Với mỗi test, ban tổ chức có đưa ra một đáp số ExpectedResult. Gọi kết quả của bạn là Result.
Nếu Result ≤ ExpectedResult bạn sẽ được 10 điểm.
http://vnoi.info
Trang 14
Hanoi-Amsterdam Olympiad in Informatics
2008
Nếu ExpectedResult < Result < 1.5 × ExpectedResult bạn sẽ được 9 – 1.5(Result – ExpectedResult) / 25
Ngoài ra, bạn sẽ không được điểm.
Với test ví dụ ở trên, với ExpectedResult = 12, output 1 sẽ được 10 điểm, output 2 sẽ được 0 điểm, output 3
sẽ được 7.997 điểm.
Lời giải
Đây là một bài toán thuộc lớp NP (không có thuật toán tốt): tìm chu trình Hamilton trên đồ thị.
Trong trường hợp các đỉnh của đồ thị là các điểm trên mặt phẳng và trọng số các cạnh là khoảng cách, ta có
một cách làm cho kết quả khá tốt như sau.
Dùng phương pháp tìm kiếm cục bộ (local search): ban đầu chọn một chu trình nào đó. Nếu chu trình có
dạng 1 ... u, v ... x, y ... 1 mà uv cắt xy thì ta cập nhật chu trình mới là 1 ... u, x ... v, y ... 1. Chu trình mới
này chắc chắn tốt hơn chu trình cũ. Cứ lặp lại bước "nâng cấp" kết quả này cho đến khi không nâng cấp
được nữa hoặc vượt quá giới hạn thời gian cho phép.
http://vnoi.info
Trang 15
- Xem thêm -