Đề thi hsg Tin học 2012

Bài 1: Các phân tử sinh học được cấu tạo từ 4 nuclêôtit cơ bản ký hiệu bởi các chữ cái A, T, G, X. Mỗi gen di truyền được tạo thành bởi một chuỗi các nuclêôtit với độ dài được tính bằng số lượng các nuclêôtit. Ví dụ AXXTTGAT là một gen có độ dài 8.

Trong một di truyền khảo sát, giáo sư Altein phát hiện một gen lạ gồm n nuclêôtit được xếp trên một vòng tròn. Ngay lập tức, giáo sư Altein dự định tiến hành so sánh gen lạ này với một số gen mẫu đang lưu trữ nhằm tìm hiểu xem mẫu gen này có gần gũi với loại gen mẫu nào đã được biết. Trong sinh học để đo độ khác biệt giữa hai mẫu gen người ta thường tính khoảng cách hamming giữa chúng. Khoảng cách Hamming giữa hai gen cùng độ dài được định nghĩa là số lượng vị trí mà tại đó hai gen chứa các nuclêôtit khác nhau. Ví dụ, hai gen AGGTT và TGATT có khoảng cách Hamming bằng 2 do 2 nuclêôtit ở vị trí 1 và 3 của chúng là khác nhau. Do các gen mẫu được sử dụng đều có độ dài m (m <= n) và có cấu trúc thẳng, trong khi gen lạ lại có độ dài n và có cấu trúc vòng nên giáo sư Altien đã định nghĩa khoảng cách Hamming giữa một gen mẫu và gen lạ là số nhỏ nhất trong số các khoảng cách Hamming giữa gen mẫu và những đoạn gen gồm m nuclêôtit liên tiếp theo chiều kim đồng hồ trong gen lạ.

Yêu cầu : Cho k gen mẫu, hãy xác định gen mẫu với khoảng cách Hamming đến gen lạ là nhỏ nhất và đưa ra khoảng cách tìm được.

Dữ liệu :
- Dòng nhất chứa 3 số n, m, k (m <= n <= 1000, k <= 100)
- Dòng hai chứa xâu độ dài n là dãy các nuclêôtit của gen lạ được liệt kê theo chiều kim đồng hồ bắt đầu tại một vị trí nào đó.
- Dòng thứ i trong số k dòng tiếp theo chứa xâu độ dài m biễu diễn gen mẫu thứ i.

Kết quả: Ghi ra một số nguyên là khoản cách Hamming nhỏ nhất tìm được.

Ví dụ:
Input --------- Output
7 3 2 ---------- 1
GTAAXXT
GAT
TTT

Bài 2: Công ty du lịch tư nhân Travel chuyên tổ chức các tour du lịch nội địa. Có n thành phố nằm trong phạm vi khai thác của công ty. Các thành phố được đánh số từ 1 tới n. Có m cặp thành phố có đoạn đường hai chiều trực tiếp nối chúng. Đề đáp ứng yêu cầu của khác hàng trong các kỳ nghỉ ngắn hạn, công ty chỉ khai thác các tour du lịch vòng quanh 4 thành phố theo các đoạn đường trực tiếp nối chúng. Để chắc chắn có thể khai thác những tour như vậy, công ty tiến hành khảo sát xem liệu có 4 thành phố nào tạo thành 1 hành trình khép kín xuất phát từ 1 thành phố và đi qua 3 thành phố còn lại, mỗi thành phố đúng 1 lần và quay về thành phố xuất phát hay không.

Yêu cầu : Hãy giúp công ty kiểm tra xem có tồn tại hành trình nào như vậy không.

Dữ liệu :
- Dòng thứ nhất chứa 2 số n, m (n <= 10000, m <= 200000)
- Dòng thứ i trong m dòng tiếp theo chứa 2 số chỉ 2 thành phố có đoạn đường trực tiếp nối chúng.

Kết quả : Ghi ra 4 số nguyên dương theo thứ tự chỉ 4 thành phố trên một hành trình tìm được hoặc ghi số -1 nếu câu trả lời là phủ định.

Ví dụ :
Input -------------- Output
5 6 ---------------- 4 5 2 3
1 2
1 5
2 3
2 5
3 4
4 5

Bài 3: Sau khi thực hiện quy hoạch của Bộ Giao Thông, sơ đồ giao thông của thành phố H gồm n tuyến đường ngang và n tuyến đường dọc cắt nhau tạo thành một lưới ô vuông với n * n nút giao thông. Các nút giao thông được gắn tọa độ theo hàng từ 1 đến n, từ trên xuống dưới và theo cột từ 1 đến n, từ trái qua phải. Ban chỉ đạo an toàn giao thông quyết định điều n cảnh sát giao thông đến các nút giao thông làm nhiệm vụ. Ban đầu mỗi cảnh sát được phân công đứng trên một nút của một tuyến đường ngang khác nhau. Đến giờ cao điểm, xuất hiện ùn tắc tại các tuyến đường dọc không có cảnh sát giao thông. Để sớm giải quyết tình trạng này, ban chỉ đạo an toàn giao thông quyết định điều động một số cảnh sát giao thông ở một số nút, từ nút hiện tại sang một nút khác cùng hàng ngang để đảm bảo mỗi tuyến đường dọc đều có mặt của cảnh sát giao thông.

Yêu cầu : Biết rằng cảnh sát ở hàng ngang thứ i cần t[i] đơn vị thời gian để di chuyển qua 1 cạnh của lưới ô vuông, hãy giúp Ban chỉ đạo an toàn giao thông tìm cách điều động các cảnh sát thoả mãn yêu cầu đặt ra sao cho việc điều động được hoàn thành tại thời điểm sớm nhất. Giả thiết là các cảnh sát được điều động đồng thới thực hiện việc di chuyển đến vị trí mới tại thời điểm 0.

Dữ liệu:
- Dòng nhất chứa một số nguyên dương n (n <= 10000)
- Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên dương c[i], t[i] (t[i] <= 10000) tương ứng là tọa độ và thời gian để di chuyển qua 1 cạnh của lưới ô vuông của cảnh sát đứng trên tuyến đường ngang thứ i.

Kết quả: Ghi ra một số nguyên duy nhất là thời điểm sớm nhất tìm được.

Ví dụ:
Input -------------- Output
5 ------------------ 10
5 10
3 10
3 20
2 9
2 15

Bài 4: Bản vanxơ Fibonacci là một bản nhạc mà giai điệu của nó bắt nguồn từ một trong những dãy số nổi tiếng nhất của lý thuyết số - dãy số Fibonacci. Hai số đầu tiên của dãy là số 1 và số 2, các số tiếp theo được xác định bằng tổng của hai số liên tiếp ngay trước nó trong dãy.

Bản vanxơ Fibonacci thu được bằng việc chuyển dãy số Fibonacci thành dãy các nột nhạc theo qui tắc chuyển một số nguyên dương thành nốt nhạc sau đây:
- Số 1 tương ứng với nốt Đô(C)
- Số 2 tương ứng với nốt Rê(D)
- Số 3 tương ứng với nốt Mi(E)
- Số 4 tương ứng với nốt Fa(F)
- Số 5 tương ứng với nốt Sol(G)
- Số 6 tương ứng với nốt La(A)
- Số 7 tương ứng với nốt Si(B)
- Số 8 tương ứng với nốt Đô(C)
- Số 9 tương ứng với nốt Rê(D)
và cứ tiếp tục như vậy. Ví dụ dãy số gồm 6 số Fibonacci đầu tiên 1, 2, 3, 5, 8 và 13 tương ứng với dãy các nốt nhạc C, D, E, G, C, A.

Để xây dựng nhịp điệu vanxơ người ta thường đi tìm các đoạn nhạc có tính chu kỳ trong bản vanxơ Fibonacci. Đoạn nhạc được gọi là có tính chu kỳ nếu như có thể chia nó ra thành k >= 2 đoạn giống hệt nhau. Ví dụ, đoạn nhạc GCAGCA là đoạn nhạc có tính chu kỳ, vì nó gồm hai đoạn giống hệt nhau GCA.

Yêu cầu : Cho trước hai số nguyên dương u, v (u < v) hãy xác định độ dài đoạn nhạc dài nhất có tính chu kỳ của bản nhạc gồm dãy các nốt nhạc của bản vanxơ Fibonacci bắt đầu từ vị trí u kết thúc ở vị trí v.

Dữ liệu:
- Dòng thứ nhất chứa số nguyên dương k là số lượng test (k <= 100)
- Dòng thứ i trong số k dòng tiếp theo chứa hai số nguyên dương u, v (u < v < 10^9) là vị trí bắt đầu và kết thúc của một bản nhạc.

Kết quả: Ghi ra k dòng, dòng thứ i chứa một số nguyên là độ dài đoạn nhạc tìm được tương ứng với test thứ i. Nếu không tìm được đoạn nào thì ghi ra số -1.

Ví dụ
Input ------------------ Output
2 ---------------------- -1
1 3--------------------- 2
4 10

Bài 5: Cuộc thi vòng loại Robocon năm nay có chủ đề "Gặp gỡ". Các Robocon sẽ tranh tài trên một lưới ô vuông n x n. Các hàng của lưới được đánh số từ 1 -> n từ trên xuống, các cột của lưới được đánh số từ 1 -> n từ trái qua. Trên k ô vuông của lưới có đặt chướng ngại vật. Ở phần thi Robot tự động, mỗi đội sẽ phải sử dụng đồng thời hai con Robot. Tại thời điểm xuất phát, Robot thứ nhất được đặt ở ô (1,1), mỗi bước chỉ được phép di chuyển sang ô kề cạnh bên phải hoặc xuống ô kề cạnh bên dưới hoặc xuống ô kề đỉnh phía dưới bên phải. Robot thứ hai được đặt tại ô (1,n), mỗi bước chỉ được phép di chuyển sang ô kề cạnh bên trái hoặc xuống ô kề cạnh bên dưới hoặc xuống ô kề đỉnh phía dưới bên trái. Bắt đầu từ thời điểm xuất phát được tính là 0, hai Robot phải di chuyển liên tục theo qui tắc đã nêu, Thời gian di chuyển từ một ô sang ô kề tiếp được tính là 1 giây. Nhiệm vụ của đội chơi là phải lập trình điều khiển hai Robot xuất phát cùng lúc, di chuyển tránh chướng ngoại vật để gặp nhau tại một ô không có chướng ngoại vật. Hai Robot gặp nhau càng sớm đội chơi càng được nhiều điểm. Lưới ô vuông được thiết kế để đảm bảo là luôn có cách đi để 2 Robot gặp nhau.

Yêu cầu : Hãy tìm cách điều khiển để cho 2 con robot gặp nhau ở thời điểm sớm nhất

Dữ liệu :
- Dòng đầu chứa 2 số n, k (n < 500, k < 10000)
- k dòng tiếp theo chứa tọa độ của các chướng ngoại vật.

Kết quả : Ghi ra 1 số nguyên duy nhất chỉ thời điểm sớm nhất tìm được

Ví dụ
Input ------- Output
5 6 ----------3
2 2
1 4
2 3
3 5
4 2

Bài 6: Một nhóm n bạn đi tập văn nghệ về khuya. Cả nhóm chỉ có một chiếc đèn pin và phải qua một cây cầu gồm m đoạn, các đoạn được đánh số từ 1 đến m. Còn vị trí n bạn đang đứng là đoạn thứ 0 và đàu cầu bên kia là vị trí m+1. Cây cầu đã cũ, do đó có một số đoạn của cầu đã hỏng và không thể đi vào được, hơn nữa cầu chỉ chịu được sức nặng của không quá 2 người. Để qua cầu an toàn các bạn phải tổ chức qua cầu theo cách thức sau : Mỗi lượt chỉ có 2 người cầm đèn pin để cùng nhau qua cầu và không được đi vào những vị trí đoạn cầu bị hỏng. Sau khi hai người qua đến đầu cầu bên kia thì những người đã qua cầu phải cử một người đem đèn pin trở lại đầu cầu bên này để các bạn khác tiếp tục qua cầu ... Mỗi đơn vị thời gian, bạn thứ i có thể bước không quá r[i] đoạn, nghĩa là nếu bạn i đang ở đoạn thứ s của cây cầu thì bạn ấy có thể di chuyển vào một trong các đoạn thứ s+1, s+2, ... , s+r[i] nếu đoạn đó không bị hỏng. Việc thực hiện một bước đi đòi hỏi 1 đơn vị thời gian. Do đó có thể có người qua cầu nhanh hơn, có người qua chậm hơn. Nếu hai bạn đi cùng nhau qua cầu thì họ phải di chuyển qua cầu với thời gian của bạn chậm hơn. Vì đã quá khuya nên cả nhóm bàn nhau tìm cách qua cầu sớm nhất có thể.

Yêu cầu : Cho biết vị trí các đoạn cầu bị hỏng và khả năng di chuyển của từng bạn, hãy tính thời gian ngắn nhất để n bạn qua được cầu. Giả thiết rằng luôn có cách để cả nhóm vượt qua cầu.

Dữ liệu :
- Dòng nhất chứa 2 số n và m (n < 10000, m < 100000);
- Dòng thứ hai chứa n số nguyên dương r[1], r[2], ... , r[n] (r[i] < 100)
- Dòng thứ ba chứa một xâu gồm m ký tự '0' hoặc '1' mô tả trạng thái của cây cầu. Ký tự '0' là đoạn không bị hỏng, ký tự '1' là đoạn đó bị hỏng.

Kết quả : Ghi ra một số nguyên duy nhất chỉ thời gian ngắn nhất để n bạn qua cầu.

Ví dụ
Input ------- Output
3 5 ----------8
2 2 4
00100