Tài liệu Báo cáo thực tập-hanoi-amsterdam olympiad in infortmatics

  • Số trang: 15 |
  • Loại file: PDF |
  • Lượt xem: 111 |
  • Lượt tải: 3
quangtran

Đã đăng 3721 tài liệu

Mô tả:

Đề 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 -