[shkola] zadachata za krystowishtata

  Eto i zadachata za koqto goworihme na shkolata. Towa mi beshe wtorata zadacha
po informatika w jiwota, taka che reshenieto sym go pisal napylno intuitiwno,
bez da mislq za razni dinamichni strukturi algoritmi, tehniki i metodi. taka
che ne se smeite na reshenieto, bahcka za 100 tochki, neznam kak ;o)) trqbwaha
mi okolo 3 chasa sumarno za da go izmislq, i
okolo 3-4 beta versii.
testowete tuk: http://infoman.musala.com/contests/spring/2002/tests_9-10.zip
 Eto go uslowieto (windows 1251 cyrillic):
 Задача 2. КРЪСТОВИЩЕ

Едно пътно кръстовище е образувано от пресичането на N улици (1 < N < 9).
Улиците са номерирани по посока обратна на часовниковата стрелка с номера от 1
до N. Всяка от улиците започва от кръстовището. Това означава, че т. нар.
"обикновено" кръстовище, при което се пресичат перпендикулярно два пътя, в тази
задача се счита, че е съставено от 4 улици. За осигуряване на безконфликтно
движение, при навлизането на всяка улица в кръстовището е поставена светофарна
секция, която може да свети червено или зелено, с което се указва дали
автомобилите, идващи по тази улица могат да навлизат в кръстовището или не.
Един автомобил, след като навлезе в кръстовището, може да продължи движението
си по всяка от улиците, за които няма забрана. Всички улици са двупосочни и за
всяка улица платното, по което се навлиза в кръстовището, е разположено
отдясно. Отделните светофарни секции се включват да светят синхронизирано така,
че във всеки момент съществува определено разпределение на червените и зелените
светлини, което се нарича фаза на светофара за цялото кръстовище. Напишете
програма JUNC.EXE, която намира минималния брой на различните фази така, че при
всяка фаза да е гарантирано безконфликтно движение на всеки автомобил, навлязъл
в кръстовището. Движението на два автомобила е конфликтно, когато техните
траектории се пресичат вътре в кръстовището, но не e конфликтно, когато
пресичането е в точката на навлизане в някоя от улиците.

Входните данни се четат от текстовия файл JUNC.INP. В първия ред на файла е
записано числото N. Следват N реда, всеки съдържащ данни за поредната улица.
Всеки ред започва с броя на улиците (или с 0), по които е забрането да продължи
движението си автомобил, навлязъл от тази улица и след това в реда следват
номерата на забранените улици, ако има такива.

Резултатът трябва да бъде записан във вид на цяло число в текстовия файл
JUNC.OUT.

Пример:

JUNC.INP

41 42 1 301 3
JUNC.OUT

3




--------------------------------------
Това писмо е изпратено от  www.mail.bg

Безплатният адрес в mail.bg предлага:
- Силна АнтиСПАМ защита
- 12MB място за поща
- SMS за ново писмо (всички оператори)
- WAP достъп от GSM и без компютър
- Безплатен POP3 достъп
- Безплатна поддръжка по телефона
______________________________________
БЕЗ ИЗЛИШНИ ВЪПРОСИ РЕГИСТРИРАЙТЕ СВОЙ
БЕЗПЛАТЕН АДРЕС НА  http://www.mail.bg



program junc;
uses windos;
const nmax=8;          {max ulici}
      path='c:\dosprogs\tp\works\konkurs\junc\testing';
type street=array [1..nmax] of boolean; {false-zabraneno true-razre6eno}
     juncs=array[1..nmax] of street;
var f1:text; {output}
    j:juncs;
    fmin,n:byte;
    over:boolean;

 {4etene na danni}
 procedure readjunc;
 var f:text;
     str,dest,denials,i:byte;
 begin
  assign(f,'junc.inp');
  reset(f);

  readln(f,n);
  if n=2 then
   begin
    fmin:=1;
    over:=true;
    exit;
   end;
  fmin:=n;
  for str:=1 to n do
   for dest:=1 to n do j[str,dest]:=true;
  for str:=1 to n do j[str,str]:=false;

  for str:=1 to n do
   begin
    read(f,denials);
    for i:=1 to denials do
     begin
      read(f,dest);
      j[str,dest]:=false;
     end;
   end;

  close(f);
 end;

 {prowerka za conflictno dwijenie m/u ulici I i P}
 function conflict(i,p:byte):boolean;
 var collision:boolean;
     dest,dest1:byte;
 begin
  for dest:=1 to n do
   if j[i,dest]=false then continue
   else for dest1:=1 to n do
        if j[p,dest1]=false then continue
        else {uslowie za razminawane}
             if ( (i=dest1) and (p=dest) ) then continue
             else  {purwo uslowie za konflict}
                   if (i>dest) AND (dest<=p) AND ( (dest1>i) or (dest1<dest) ) 
then
                     begin
                      conflict:=true;
                      exit;
                     end
                   else {wtoro uslowie za konflict}
                        if (i>dest) AND (dest>p)  AND ( (dest1>dest) and 
(dest1<=i) ) then
                          begin
                           conflict:=true;
                           exit;
                          end
                        else {treto uslowie za konflict}
                             if (i<dest) AND (dest>p)  AND ( (dest1<dest) and 
(dest1>i) ) then
                               begin
                                conflict:=true;
                                exit;
                               end
                             else {4etwurto uslowie za konflict}
                                  if (i<dest) AND (dest<=p) AND ( (dest1<i) or 
(dest1>dest) ) then
                                    begin
                                     conflict:=true;
                                     exit;
                                    end;
  conflict:=false;
 end;


 {izsledwa krustowi6te}
 procedure xplorjunc;
 var i,p:byte;
     streets:array[1..nmax] of boolean; {false - ulicata nqma priqtelska ulica}
                                        {true - ulicata ima priqtleska ulica}
 begin
  for i:=1 to nmax do streets[i]:=false;

  for i:=2 to n do
    for p:=1 to i-1 do
      if not conflict(i,p)
      then if not(streets[i]) and not(streets[p]) then
            begin
             streets[i]:=true;
             streets[p]:=true;
             dec(fmin);
            end;
 end;


BEGIN
 setcurdir(path);
 readjunc;
 if not over then xplorjunc;

 assign(f1,'junc.out');
 rewrite(f1);
 writeln(f1,fmin);
 close(f1);
END.

Other related posts: