ONI 97, Finala, Timisoara
Clasa X, Ziua 2

Problema 1 (Inchisoarea)
     In urma grevelor ce au avut loc in inchisori s-a hotarat "de sus" sa se ia 
masuri de intarire a pazei celulelor. Datorita austeritatii bugetului inchisorii, 
si necesitatii reducerilor e posibil ca un gardian sa supravegheze mai multe 
celule cu conditia ca acestea sa fie in raza lui vizuala .
Cerinta conducerii este sa se foloseasca un numar minim de gardieni, plasati in 
posturile din fata celulelor ocupate.
In proiectul elaborat de un detinut informatician care sparsese o banca prin 
Internet, inchisorii i se asociaza un graf cu n noduri (celule) in care muchia 
(i,j) reprezinta faptul ca intre celulele i,j exista vizibilitate.
Intrare:
Datele de intrare aflate in fisierul in.txt sunt reprezentate sub forma: 
- pe prima linie, numarul de celule n (n<=50).
- Pe urmatoarele n linii sunt componentele matricei de adiacenta separate 
printr-un spatiu, fiecare linie terminandu-se cu <enter>.
Iesire:
Datele de iesire se vor gasi in fisierul out.txt si vor reprezenta solutiile sub 
forma unor linii dispuse astfel: 
- pe prima linie se afla numarul gardienilor, iar pe urmatoarele, pe cate o 
linie, numerele de ordine ale celulelor unde sunt plasati, despartite prin 
spatiu (o linie pentru fiecare solutie gasita)
Exemplu:
Date de intrare:
9
1 1 1 1 1 1 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 1 1 1
1 0 0 1 1 1 0 0 0
1 0 0 1 1 1 0 0 0
1 0 0 1 1 1 0 0 0
0 0 1 0 0 0 1 1 1
0 0 1 0 0 0 1 1 1
0 0 1 0 0 0 1 1 1
Iesire:
2
1 7
1 8
1 9
3 6
3 4
3 5
1 3
====================================
Solutia Comisiei:
Program inchisoare;
uses crt;
type multime=set of byte;
var f:text;
    nfis:string;
    n,i,j:byte;
    a:array[1..100,1..100]of 0..1;
    csv:multime;

function lungime(csv:multime):integer;
var t,k:byte;
    csv1:set of byte;
begin
csv1:=[];
for k:=1 to n do
  if (k in csv) then begin
                      csv1:=csv1+[k];
                      for j:=1 to n do if a[k,j]=1 then csv1:=csv1+[j];
                     end;

t:=0;
for k:=1 to n do if k in csv1 then t:=t+1;
lungime:=t;
end;

procedure max;
var k,j,t:byte;
    lng:array[0..100]of byte;
    ag:boolean;
begin
ag:=false;
for k:=0 to n do lng[k]:=0;
t:=0;
for k:=1 to n do
 if not (k in csv) then
 begin
  lng[k]:=0;
  for j:=1 to n do
   if (not(j in csv))and(a[k,j]=1) then lng[k]:=lng[k]+1;
 end;
for k:=1 to n do
 if lng[k]>lng[t] then if not(k in csv) then begin
                                              t:=k;
                                              ag:=true;
                                             end;
if ag then csv:=csv+[t];
end;


begin
clrscr;
write('nfis = ');
readln(nfis);
assign(f,nfis);
reset(f);
readln(f,n);
for i:=1 to n do
 begin
  for j:=1 to n do read(f,a[i,j]);
  readln(f);
 end;
csv:=[];
repeat
 max;
until lungime(csv)=n;
for i:=1 to n do
 if i in csv then write(i,' ');
readkey;
end.
================================
Input 1:
13
1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 1 0 0 0 0 0 0 0 0 0
0 0 1 0 1 1 1 0 0 0 0 0 0
0 0 1 0 1 1 1 0 0 0 0 0 0
0 0 1 0 1 1 1 0 0 0 0 0 0
0 0 1 0 0 0 0 1 1 0 0 0 0
0 0 1 0 0 0 0 1 1 0 0 0 0
0 0 1 0 0 0 0 0 0 1 1 0 0
0 0 1 0 0 0 0 0 0 1 1 0 0
0 0 1 0 0 0 0 0 0 0 0 1 1
0 0 1 0 0 0 0 0 0 0 0 1 1
============================
Input 2:
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
================================
Input 3:
6
1 1 1 0 0 0
1 1 1 1 1 1
1 1 1 0 0 0
0 1 0 1 1 1
0 1 0 1 1 1
0 1 0 1 1 1
=============================
Input 4:
6
1 1 1 0 0 0
1 1 1 0 0 0
1 1 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
===========================
Input 5:
13
1 1 1 1 0 0 0 0 0 0 1 0 0
1 1 1 1 0 0 0 0 0 0 1 0 0
1 1 1 1 0 0 0 0 0 0 1 0 0
1 1 1 1 0 0 0 0 0 0 1 0 0
0 0 0 0 1 1 1 0 0 1 0 0 0
0 0 0 0 1 1 1 0 0 1 0 0 0
0 0 0 0 1 1 1 0 0 1 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1
=============================
Input 6:
9
1 0 0 0 0 0 0 1 0
0 1 1 0 0 0 0 0 1
0 1 1 0 0 0 0 0 0
0 0 0 1 1 0 0 0 1
0 0 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 1
0 0 0 0 0 1 1 0 0
1 0 0 0 0 0 0 1 1
0 1 0 1 0 1 0 1 1
=============================
Input 7:
12
1 0 1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1 0 1
=================================

Iesire 1:
10
1
3
=====================
Iesire 2:
5
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
=========================
Iesire 3:
10
1
2
=========================
Iesire 4:
5
4
1 4 5 6
2 4 5 6
3 4 5 6
==========================
Iesire 5:
5
2
11 10
11 7
11 5
11 6
10 1
10 2
10 3
10 4
==========================
Iesire 6:
10
4
1 2 4 6
1 2 4 7
1 2 5 6
1 2 5 7
1 3 4 6
1 3 4 7
1 3 5 6
2 4 6 8
2 4 7 8
2 5 6 8
2 5 7 8
3 4 6 8
3 4 7 8
3 5 6 8
3 5 7 8
========================
Iesire 7:
5
8
2 5 8 11 1 4 7 10
2 5 8 11 1 4 7 12
2 5 8 11 1 4 9 10
2 5 8 11 1 4 9 12
2 5 8 11 1 6 7 10
2 5 8 11 1 6 7 12
2 5 8 11 1 6 9 10
2 5 8 11 1 6 9 12
2 5 8 11 3 4 7 10
2 5 8 11 3 4 7 12
2 5 8 11 3 4 9 10
2 5 8 11 3 4 9 12
2 5 8 11 3 6 7 10
2 5 8 11 3 6 7 12
2 5 8 11 3 6 9 10
2 5 8 11 3 6 9 12
========================

