2. zadatak, Ugljen, 80 bodova

Opis algoritma

Nakon učitavanja podataka iz ulazne datoteke UGLJEN.IN inicijalizira se polje zapisa rudari tako da se u obje varijable zapisa upisuje vrijednost -1. To polje će za svakog rudara sadržavati informaciju o tome da li on trenutno radi ili ne radi. Npr. ukoliko se u varijabli pocetak nalazi vrijednost -1, to znači da taj rudar trenutno ne radi i da se u varijabli kraj nalazi broj koji nam kaže kada je taj rudar zadnji put prestao raditi (to nam je bitno zbog dužine pauze). S druge strane, ukoliko je vrijednost varijable kraj jednaka -1, to znači da taj rudar trenutno radi i varijabla pocetak nam kaže kada je on zadnji put počeo raditi. Ukoliko se i u varijabli pocetak i u varijabli kraj nalazi vrijednost -1, to znači da taj rudar još uopće nije počeo raditi.
Nakon gore spomenute inicijalizacije polja rudari poziva se rekurzivna funkcija rijesi sa 3 parametra (kod prvog poziva funkcije rijesi to su 1, 0 i 0). Funkcija rijesi pokušava na sve moguće načine rasporediti rudare tokom radnog vremena. Ona prvo popunjava prvi sat radnog vremena rudnika, tako da pokušava ubacivati radnike na posao s time da pazi koji se rudari mrze međusobno, pazi na maksimalna vremena koliko koji rudar može raditi i na dužinu pauze. Kada popuni prvi sat, funkcija popunjava drugi sat radnog vremena i tako dalje, sve dok ne popuni cijelo radno vrijeme s rudarima. Prvi parametar označava koji trenutno sat radnog vremena popunjavamo (poprima vrijednost između 1 i broj_sati), drugi parametar je redni broj rudara kojeg pokušavamo ubaciti na posao (vrijednost između 0 i broj_rudara - 1) i treći parametar će nam u svakom trenutku sadržavati vrijednost količine do sada iskopane rude.
I na kraju se u izlaznu datoteku UGLJEN.OUT zapisuje vrijednost varijable max_kolicina u kojoj će biti spremljena maksimalna količina iskopane rude za neki raspored rudara.

UGLJEN.C

#include <stdio.h>

#define MAX_RUDARA 5
#define MAX_SATI 8

typedef struct {
                 int pocetak,kraj;
               } TIP_RUDARI;

int broj_rudara,broj_sati,maksimum[MAX_RUDARA],ucinak[MAX_RUDARA],
    duzina_pauze,mrze_se[MAX_RUDARA][MAX_RUDARA],max_kolicina = 0;
TIP_RUDARI rudari[MAX_RUDARA];

void rijesi(int,int,int);

void main(void)
{
  int i,j;
  FILE *fp_ulaz,*fp_izlaz;

  fp_ulaz = fopen("UGLJEN.IN","rt");
  fp_izlaz = fopen("UGLJEN.OUT","wt");

  fscanf(fp_ulaz,"%d %d",&broj_rudara,&broj_sati);
  for (i = 0;i < broj_rudara;++i)
    fscanf(fp_ulaz,"%d",maksimum + i);
  for (i = 0;i < broj_rudara;++i)
    fscanf(fp_ulaz,"%d",ucinak + i);
  fscanf(fp_ulaz,"%d",&duzina_pauze);

  for (i = 0;i < broj_rudara;++i)
    for (j = 0;j <= i;++j)
    {
      fscanf(fp_ulaz,"%d",&mrze_se[i][j]);
      mrze_se[j][i] = mrze_se[i][j];
    }
  for (i = 0;i < broj_rudara;++i)
    rudari[i].pocetak = rudari[i].kraj = -1;

  rijesi(1,0,0);
  fprintf(fp_izlaz,"%d\n",max_kolicina);

  fclose(fp_ulaz);
  fclose(fp_izlaz);
}

void rijesi(int sat,int rudar,int kolicina)
{
  int i,ne_mrze_se;
  TIP_RUDARI old_rudar;

  if (rudar == broj_rudara)
  {
    rudar = 0;
    if (++sat > broj_sati)
    {
      if (kolicina > max_kolicina)
        max_kolicina = kolicina;
      return;
    }
  }
  old_rudar = rudari[rudar];
  if (old_rudar.pocetak != -1)
  {
    if (sat - old_rudar.pocetak < maksimum[rudar])
    {
      ne_mrze_se = 1;
      for (i = 0;i < rudar;++i)
        if (rudari[i].pocetak != -1 && mrze_se[rudar][i])
        {
          ne_mrze_se = 0;
          break;
        }
      if (ne_mrze_se) // ne mrze se
        rijesi(sat,rudar + 1,kolicina + ucinak[rudar]);
    }

    rudari[rudar].pocetak = -1;
    rudari[rudar].kraj = sat - 1;
    rijesi(sat,rudar + 1,kolicina);
  }
  else // rudar ne radi
  {
    if (old_rudar.kraj == -1 || sat - old_rudar.kraj > duzina_pauze)
    {
      ne_mrze_se = 1;
      for (i = 0;i < rudar;++i)
        if (rudari[i].pocetak != -1 && mrze_se[rudar][i])
        {
          ne_mrze_se = 0;
          break;
        }
      if (ne_mrze_se)
      {
        rudari[rudar].pocetak = sat;
        rudari[rudar].kraj = -1;
        rijesi(sat,rudar + 1,kolicina + ucinak[rudar]);
      }
    }
    rudari[rudar] = old_rudar;
    rijesi(sat,rudar + 1,kolicina);
  }
  rudari[rudar] = old_rudar;
}

UGLJEN.PAS

program ugljen;
const
  MAX_RUDARA = 5;
  MAX_SATI = 8;
type
  TIP_RUDARI = record
                 pocetak,kraj : integer;
               end;
var
  i,j,broj,broj_rudara,broj_sati,duzina_pauze,max_kolicina : integer;
  mrze_se : array [1..MAX_RUDARA,1..MAX_RUDARA] of boolean;
  maksimum,ucinak : array [1..MAX_RUDARA] of integer;
  rudari : array [1..MAX_RUDARA] of TIP_RUDARI;
  fp_ulaz,fp_izlaz : text;

procedure rijesi(sat,rudar,kolicina : integer);
var
  ne_mrze_se : boolean;
  i : integer;
  old_rudar : TIP_RUDARI;
begin
  if rudar > broj_rudara then
    begin
      rudar := 1;
      inc(sat);
      if sat > broj_sati then
        begin
          if kolicina > max_kolicina then
            max_kolicina := kolicina;
          exit;
        end;
    end;

  old_rudar := rudari[rudar];

  if old_rudar.pocetak <> -1 then
    begin
      if sat - old_rudar.pocetak < maksimum[rudar] then
        begin
          ne_mrze_se := true;
          for i := 1 to rudar - 1 do
            if (rudari[i].pocetak <> -1) and mrze_se[rudar,i] then
              ne_mrze_se := false;
          if ne_mrze_se then
            rijesi(sat,rudar + 1,kolicina + ucinak[rudar]);
        end;
      rudari[rudar].pocetak := -1;
      rudari[rudar].kraj := sat - 1;
      rijesi(sat,rudar + 1,kolicina);
    end
  else
    begin
      if (old_rudar.kraj = -1) or (sat - old_rudar.kraj > duzina_pauze) then
        begin
          ne_mrze_se := true;
          for i := 1 to rudar - 1 do
            if (rudari[i].pocetak <> -1) and mrze_se[rudar,i] then
              ne_mrze_se := false;
          if ne_mrze_se then
            begin
              rudari[rudar].pocetak := sat;
              rudari[rudar].kraj := -1;
              rijesi(sat,rudar + 1,kolicina + ucinak[rudar]);
            end;
        end;
      rudari[rudar] := old_rudar;
      rijesi(sat,rudar + 1,kolicina);
    end;

  rudari[rudar] := old_rudar;
end;

begin
  assign(fp_ulaz,'UGLJEN.IN');
  assign(fp_izlaz,'UGLJEN.OUT');

  reset(fp_ulaz);
  rewrite(fp_izlaz);

  read(fp_ulaz,broj_rudara,broj_sati);
  for i := 1 to broj_rudara do
    read(fp_ulaz,maksimum[i]);
  for i := 1 to broj_rudara do
    read(fp_ulaz,ucinak[i]);
  read(fp_ulaz,duzina_pauze);
  for i := 1 to broj_rudara do
    for j := 1 to i do
      begin
        read(fp_ulaz,broj);
        if broj = 1 then
          mrze_se[i,j] := true
        else
          mrze_se[i,j] := false;
        mrze_se[j,i] := mrze_se[i,j];
      end;
  for i := 1 to broj_rudara do
    begin
      rudari[i].pocetak := -1;
      rudari[i].kraj := -1;
    end;

  max_kolicina := 0;

  rijesi(1,1,0);
  writeln(fp_izlaz,max_kolicina);

  close(fp_ulaz);
  close(fp_izlaz);
end.


Test podaci

UGLJEN1.IN
UGLJEN2.IN
UGLJEN3.IN
UGLJEN4.IN

2
2
1 2
3 5
1
0
0 0


2
4
2 3
1 3
2
0
0 0


3
3
1 2 3
1 3 5
3
0
0 0
0 0 0


3
5
1 2 3
1 3 5
1
0
0 0
0 1 0

UGLJEN1.OUT
UGLJEN2.OUT
UGLJEN3.OUT
UGLJEN4.OUT
13
11
22
26
4 boda
6 bodova
8 bodova
9 bodova

UGLJEN5.IN
UGLJEN6.IN
UGLJEN7.IN
UGLJEN8.IN

4
5
2 1 3 3
2 3 4 5
2
0
0 0
0 1 0
0 0 0 0


4
6
2 1 3 1
4 3 2 2
1
0
0 0
0 1 0
0 0 0 0


5
8
2 1 3 1 2
4 3 2 2 1
3
0
1 0
1 1 0
1 1 0 0
0 1 1 1 0


5
8
2 2 3 5 2
3 2 2 5 1
2
0
1 0
1 1 0
1 1 1 0
1 1 1 1 0

UGLJEN5.OUT
UGLJEN6.OUT
UGLJEN7.OUT
UGLJEN8.OUT
39
37
33
36
10 bodova
13 bodova
15 bodova
15 bodova