TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

kockice.cpp    1,013 b      izvorni kod rešenja
kockice.checker.cpp    812 b      izvorni kod programa za testiranje
kockice.checker.exe    24,710 b      program za testiranje
kockice.tests.rar    420,485 b      test primeri

zadatak: Kockice

Mali Đokica je dobio kockice za rođendan. Uzeo je tablu dimenzija n puta m i na svako polje je postavio nekoliko kockica (jednu na drugu). Time je napravio figuru koja ne mora da bude povezana. Njegov tata posmatra kako se mali Đokica igra i želi da zna zapreminu i površinu dobijenog tela.

Ulaz:

U prvom redu ulazne datoteke ZAD3.DAT nalaze se dva prirodna broja razdvojena prazninom n i m (1 ≤ n, m ≤ 500) i predstavljaju dimenzije table. U svakom od sledećih n redova se nalazi m brojeva. U i-tom redu j-ti broj a[i][j] (0 ≤ a[i][j] ≤ 1000) označava visinu stuba (broj kockica) na tom polju.

Izlaz:

U izlaznu datoteku ZAD3.RES ispisati zapreminu i površinu tela koje je mali Đokica napravio.

Primer:

ZAD3.DAT      ZAD3.RES
2 3
2 2 2
1 0 3
        
10 36

Objašnjenje:

Figura na slici odgovara rasporedu kockica u test primeru. Zapremina tela je 10, dok je površina 36.

rešenje


Zapremina tela je jednaka broju kockica koje je Đokica upotrebio – suma svih brojeva u matrici a.

Površinu tela računamo kao zbir svih horizontalnih i vertikalnih vidljivih strana kockica. Broj horizontalnih strana je jednak dvostrukom broju stubića, tj. dvostruki broj nenula elemenata matrice a. Kako bi lakše izračunali broj vertikalnih strana, uokvirimo datu matricu nulama. Broj strana koje su vidljive između dva stubića kockica je jednak apsolutnoj vrednosti razlike visina. Sada prođemo kroz matricu a, i za svako polje pogledamo desno i gore, sabirajući brojeve |a [i, j] – a [i + 1, j]| + |a [i, j] – a [i, j + 1]|.

Složenost algoritma je O (nm).

Pseudokod:

   for i = 0 to n + 1 do begin
      a [i][0] = 0;
      a [i][m + 1] = 0;
   end;
   for j = 0 to m do begin 
      a [0][j] = 0;
      a [n + 1][j] = 0;
   end;
   Volume = 0;
   Area = 0;
   for i = 0 to n do
      for j = 0 to m do begin
         Volume = Volume + a [i][j];
         if (a [i][j] > 0) then
            Area = Area + 2;
         Area = Area + abs (a [i + 1][j] – a [i][j]) + abs (a [i][j + 1] – a [i][j]);
      end;

fajl: kockice.cpp
#include <stdio.h>
#include <math.h>
#define MaxN 502

long n, m, a [MaxN][MaxN], Volume, Area;

void Input ()
{
  FILE *in;
  long i, j;

  in = fopen ("zad3.dat", "r");
  fscanf (in, "%ld %ld", &n, &m);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++)
      fscanf (in, "%ld", &a [i][j]);
  fclose (in);
}

void Output ()
{
  FILE *out;

  out = fopen ("zad3.res", "w");
  fprintf (out, "%ld %ld\n", Volume, Area);
  fclose (out);
}

void Solve ()
{
  long i, j;

  Volume = 0;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++)
      Volume = Volume + a [i][j];

  for (i = 0; i <= n; i++)
  {
    a [i][0] = 0;
    a [i][m + 1] = 0;
  }
  for (j = 0; j <= m; j++)
  {
    a [0][j] = 0;
    a [n + 1][j] = 0;
  }
  Area = 0;
  for (i = 0; i <= n; i++)
    for (j = 0; j <= m; j++)
    {
      if (a [i][j] > 0)
        Area = Area + 2;
      Area = Area + abs (a [i][j] - a [i + 1][j]) + abs (a [i][j] - a [i][j + 1]);
    }
}

int main ()
{
  Input ();
  Solve ();
  Output ();
  return 0;
}