MODULE NBrojeva;

  FROM IO IMPORT
    WrLn, WrCard, RdCard, WrStr;

  CONST
    MaxNiz = 50;
    MaxSuma = 500;

  VAR
    n, Suma, SumaPola: CARDINAL;
    Broj: ARRAY [1 .. MaxNiz] OF CARDINAL;
    Iskor: ARRAY[1 .. MaxNiz] OF BOOLEAN;
    Mat: ARRAY[0 .. MaxSuma], [0 .. MaxNiz] OF CARDINAL;
   (*   Mat[i, j] je suma brojeva u resenju ako je maksimalna *)
   (* dozvoljena suma brojeva u resenju jednaka 'i' i ako se  *)
   (* koristi samo prvih 'j' brojeva.                         *)

  PROCEDURE Unos;
    VAR
      i: CARDINAL;
  BEGIN
    WrStr('Unesite n: ');
    n:= RdCard();
    Suma:= 0;
    FOR i:= 1 TO n DO
      WrStr('Unesite ');
      WrCard(i, 1);
      WrStr('. broj: ');
      Broj[i]:= RdCard();
      Suma:= Suma + Broj[i];
      Iskor[i]:= FALSE;
    END;
    SumaPola:= Suma DIV 2;
  END Unos;

  PROCEDURE Resi;
    VAR
      i, j, Pom: CARDINAL;
  BEGIN
    FOR i:= 0 TO SumaPola DO
      Mat[i, 0]:= 0;  (* Koristi se prvih 0 brojeva *)
    END;
    FOR j:= 1 TO n DO
      Mat[0, j]:= 0;  (* Maksimalna dozvoljena suma brojeva u resenju je 0 *)
    END;
    FOR i:= 1 TO SumaPola DO
      (* Maks. dozvoljena suma brojeva u resenju je i *)
      FOR j := 1 TO n DO
        (* U resenju mogu ucestvovati prvih j brojeva *)
        Mat[i, j]:= Mat[i, j - 1];
        IF Broj[j] <= i THEN
          Pom:= Mat[i - Broj[j], j - 1] + Broj[j];
          IF Pom > Mat[i, j] THEN
            Mat[i, j]:= Pom;
          END;
        END;
      END;
    END;
  END Resi;

  PROCEDURE IspisiPrvu;
    VAR
      i, j: CARDINAL;
  BEGIN
    WrStr('Zbir prve grupe brojeva je ');
    WrCard(Mat[SumaPola, n], 1);
    WrLn;
    WrStr('Prvu grupu brojeva cine brojevi:');
    WrLn;
    i:= SumaPola;
    j:= n;
    REPEAT
      WHILE (j > 0) AND (Mat[i, j] = Mat[i, j - 1]) DO
        DEC(j);
      END;
      IF j > 0 THEN
        WrCard(Broj[j], 8);
        Iskor[j]:= TRUE;
        i:= i - Broj[j];
        DEC(j);
      END;
    UNTIL j = 0;
  END IspisiPrvu;

  PROCEDURE IspisiDrugu;
    VAR
      i, j: CARDINAL;
  BEGIN
    WrLn;
    WrStr('Zbir druge grupe brojeva je ');
    WrCard(Suma - Mat[SumaPola, n], 1);
    WrLn;
    WrStr('Drugu grupu brojeva cine brojevi:');
    WrLn;
    FOR i := 1 TO n DO
      IF NOT Iskor[i] THEN
        WrCard(Broj[i], 8);
      END;
    END;
  END IspisiDrugu;

BEGIN
  Unos;
  IF SumaPola > MaxSuma THEN
    WrStr('Ulazni podaci su suvise veliki.');
  ELSE
    Resi;
    IspisiPrvu;
    IspisiDrugu;
  END;
END NBrojeva.