Đề thi HSG Pascal Lớp 12 Quảng Ngãi

SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI
TỈNH QUẢNG NGÃI LỚP 12 THPT NĂM HỌC 2011- 2012
Môn thi: Tin học
Thời gian: 150 phút (không kể thời gian giao đề)
Ngày thi: 11-11-2011

Câu 1 (7 điểm) - Điền khuyết xâu kí tự Cho trước 2 xâu ký tự a, b (chiều dài của mỗi xâu không quá 100).
Yêu cầu: Viết chương trình bổ sung một số ký tự vào a và một số ký tự vào b để hai xâu a và b trở nên giống nhau (phân biệt chữ hoa, thường). Tổng số kí tự bổ sung vào là ít nhất.
Input: File văn bản fs.inp cấu trúc như sau:
Bao gồm một số dòng (là số chẵn, có thể lên đến 10.000 dòng).
Mỗi dòng là một xâu kí tự (không quá 100 kí tự).
Output: File văn bản fs.out cấu trúc như sau:
Gồm một số dòng (là số dòng của file input chia 2)
Dòng thứ i chứa xâu kí tự là kết quả của việc bổ sung 2 xâu tại dòng thứ i*2-1 và i*2 trên file input.
Ví dụ:
Fs.inp



Abcde
Abdf

Abcdef


Câu 2: LSFIGHT (10đ)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



Câu 3: COMBINE (10đ) 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