LSFIGHT (10Đ)TRONG KỲ THI NĂM NAY CÁC THÍ SINH PHẢI THAM GIA MỘT MƠN...

Bài 1: 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

3

1 1 1 1 1 0 1

1

0 1 0 1 1 0 0

0 1 1 1 1 1 1

6

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

Chương trình:

for j:=1 to n do

const fi='LSFIGHT.INP';

for k:=1 to n do

fo='LSFIGHT.OUT';

maxn=501;

if (a[i,j]=0)and(a[i,k]=1)and(a[k,j]=1) then a[i,j]:=1;

var f:text;

end;

i,j,k,n,sl,sn:word;

procedure output;

begin

duoc:array[0..maxn]of boolean;

assign(f,fo);

a:Array[0..maxn,0..maxn]of byte;

rewrite(f);

procedure input;

for i:=1 to n do

begin

assign(f,fi);

reset(f);

sl:=0;

for j:=1 to n do if a[i,j]=1 then inc(sl);

readln(f,n);

if sl=n then begin inc(sn);duoc[i]:=true;end;

end;

writeln(f,sn);

for j:=1 to n do read(f,a[i,j]);

for i:=1 to n do if duoc[i] then writeln(f,i);

readln(f);

close(f);

procedure solve;

input;

solve;

output;

fillchar(duoc,sizeof(duoc),false);

end.