ĐỀ VÀ ĐÁP ÁN _ HSG ĐBSCL _XVI - 2009¬_Kiên Giang_ Tin

SỞ GIÁO DỤC VÀ ĐÀO TẠO KIÊN GIANG KÌ THI HỌC SINH GIỎI ĐỒNG BẰNG SÔNG CỬU LONG
TRƯỜNG THPT CHUYÊN HUỲNH MẪN ĐẠT NĂM HỌC: 2008 – 2009

ĐỀ THI ĐỀ NGHỊ

Bài 1: LSFIGHT
Trong kỳ thi năm nay các thí sinh phải tham gia một môn thi đấu đối kháng giữa 2 người. Sau vòng loại, ban tổ chức sẽ chọn ra N thí sinh có số điểm cao nhất và đánh số từ 1 đến N. Các thí sinh này phải xếp lần lượt theo thứ tự thành 1 vòng tròn (người thứ N đứng cạnh người thứ 1). Sau đó sẽ chọn ra 2 thí sinh bất kì đang đứng cạnh nhau trong vòng tròn để thi đấu, thí sinh nào thua sẽ bị loại và buộc phải đi ra vòng tròn, trở về hàng ghế khán giả. Cuộc đấu cứ tiếp tục như thế đến khi chỉ còn một người ở lại và cũng chính là người thắng cuộc.
Yêu cầu: Ban tổ chức muốn biết trước xem có bao nhiêu người có khả năng thắng cuộc và đó là những người nào. Biết trước ai sẽ thắng trong mỗi trận đấu, bạn hãy giúp ban tổ chức.
Dữ liệu vào: LSFIGHT.INP
- Dòng đầu là số nguyên dương N (3<=N<=500). - N dòng sau là ma trận A[i, j], A[i, j] = 0 nếu thí sinh i thua thí sinh j và A[i, j] = 1 nếu ngược lại. Biết rằng luôn đảm bảo A[i, i]=1 với mọi i và A[i, j] + A[j, i] = 1 với i <> j. Các số viết cách nhau ít nhất 1 dấu cách.
Kết quả: LSFIGHT.OUT
- Dòng đầu là số nguyên dương M - số lượng thí sinh có khả năng thắng cuộc - M dòng sau mỗi dòng ghi một số là chỉ số của thí sinh có khả năng thắng cuộc theo thứ tự tăng dần của chỉ số.
Time: 1s.
Ví dụ:
LSFIGHT.INP
LSFIGHT.OUT

7
1 1 1 1 1 0 1
0 1 0 1 1 0 0
0 1 1 1 1 1 1
0 0 0 1 1 0 1
0 0 0 0 1 0 1
1 1 0 1 1 1 1
0 1 0 0 0 0 1
3
1
3
6


BÀI 2: COMBINE
Có n đoạn dây xích (N≤20000), mỗi đoạn dây xích là một chuỗi các mắt xích được nối với nhau. Các đoạn dây xích này tách rời nhau. Mỗi đoạn xích có không quá 20000 mắt xích
Bằng cách cắt ra một mắt xích, sau đó hàn lại, ta có thể nối hai dây xích thành một đoạn. Thời gian để cắt và hàn mỗi mắt xích là 1 đơn vị thời gian và được xem như bằng nhau với mọi mắt xích.
Yêu cầu: Hãy tính thời gian ngắn nhất để nối N đoạn dây xích thành 1 đoạn duy nhất.
Dữ liệu vào: COMBINE.INP
Dòng đầu ghi số N
Dòng thứ 2 ghi N số nguyên dương, mỗi số là độ dài của 1 đoạn xích.
Kết quả: COMBINE.OUT
Một số duy nhất là thời gian ngắn nhất tìm được.
Time: 1s.
Ví dụ:
COMBINE.INP
COMBINE.OUT

4
5 7 8 9
3