ZADATAK 1 - GLISTA - 40 bodova

TEST PODACI


	Broj N		Rješenje	Broj bodova
Test 1	112		1		3
Test 2	256		0		4
Test 3	1162261467	19		5
Test 4	2813846		3		5
Test 5	373248		6		5
Test 6	991169449	15		5
Test 7	1078282205	255		6
Test 8	1999666333	7		7

OPIS ALGORITMA (GLISTA2)

Zadani broj n je potrebno prikazati kao sumu od barem dva uzastopna broja. Dakle, mora vrijediti

n=s+(s+1)+(s+2)+ ... +(s+m-2)+(s+m-1)

gdje je s najmanji broj u sumi, a m broj brojeva u sumi, dakle m(2. Ova suma se može napisati kao

n=m*s+m*(m-1)/2

iz čega slijedi

2*n=m*(2*s+m-1).

Ideja je rastaviti broj 2*n na proste faktore, pa njihovim kombiniranjem doći do mogućih kandidata za m. Odmah se vidi da je samo jedan od brojeva m i (2*s+m-1) paran, pa se sve potencije broja 2 iz rastava ili nalaze ili ne nalaze u m. Nakon što kombinirajući dođemo do različitih mogućnosti za m potrebno je provjeriti da li postoji odgovarajući s. Iz gornje formule slijedi

s=n/m-(m-1)/2

a kako je s(1, odnosno s(0 slijedi

n/m-(m-1)/2>0

odnosno

(m-1)/2<n/m
m*(m-1)/2<n

i to je uvjet koji moramo provjeriti. Nakon toga sigurni smo da za taj m postoji tražena suma. Ovdje je algoritam implementiran rekurzivno (dio koji kombinira brojeve iz rastava na proste faktore), ali se vrlo lako može implementirati i nerekurzivno.

GLISTA1.PAS

program glista;
var
  n : longint;

procedure ucitaj;
var
  f : text;

begin
  assign(f,'GLISTA.DAT');
  reset(f);
  readln(f,n);
  close(f);
end;

procedure rijesi;
var
  pocetak,kraj : longint;
  suma : real;
  broj_rastava : integer;

begin
  broj_rastava := 0;

  pocetak := 1;
  kraj := 2;
  suma := 3;

  repeat
    if suma = n then
      inc(broj_rastava);
    if suma <= n then
      begin
        inc(kraj);
        suma := suma + kraj;
      end;
    if suma >= n then
      begin
        suma := suma - pocetak;
        inc(pocetak);
      end;
  until pocetak > n DIV 2;

  writeln;
  writeln('Rjesenje = ',broj_rastava);
end;

begin
  ucitaj;
  rijesi;
end.

GLISTA1.C

#include <stdio.h>

long n;

void ucitaj (void)
{
  FILE *fp;

  fp = fopen("GLISTA.DAT","rt");

  fscanf(fp,"%ld",&n);

  fclose(fp);
}

void rijesi (void)
{
  long pocetak = 1l,kraj = 2l;
  unsigned long suma = 3l;
  int broj_rastava = 0;

  do
  {
    if (suma == n)
      printf("%d %ld\n",++broj_rastava,pocetak);
    if (suma <= n)
      suma += ++kraj;
    if (suma >= n)
      suma -= pocetak++;
  } while (pocetak <= n / 2);

  printf("\nRjesenje = %d\n",broj_rastava);

}

int main (void)
{
  ucitaj();
  rijesi();

  return 0;
}

GLISTA2.PAS

program glista;
const
  MAX_DJELITELJA = 10;
var
  n : longint;
  djelitelji : array [1..MAX_DJELITELJA] of record
                                              broj : real;
                                              koliko : integer;
                                            end;
  broj_djelitelja,broj_rastava : integer;

procedure ucitaj;
var
  f : text;

begin
  assign(f,'GLISTA.DAT');
  reset(f);
  readln(f,n);
  close(f);
end;

procedure rijesi;
var
  broj,a : longint;
  granica,dva_n : real;

procedure rekurzija(gdje : integer;broj : real);
var
  i : integer;
  novi_broj : real;

begin
  if gdje > broj_djelitelja then
    begin
      inc(broj_rastava);
      exit;
    end;

  novi_broj := broj;
  for i := 0 to djelitelji[gdje].koliko do
    begin
      if novi_broj * (novi_broj - 1) >= dva_n then
        break;

      rekurzija(gdje + 1,novi_broj);

      novi_broj := novi_broj * djelitelji[gdje].broj;
    end;

end;

begin
  broj := n;
  djelitelji[1].broj := 2;
  djelitelji[1].koliko := 1;

  while broj MOD 2 = 0 do
    begin
      broj := broj DIV 2;
      djelitelji[1].broj := 2 * djelitelji[1].broj;
    end;

  broj_djelitelja := 1;
  granica := sqrt(broj);
  a := 3;

  repeat
    if broj MOD a = 0 then
      begin
        inc(broj_djelitelja);
        djelitelji[broj_djelitelja].broj := a;
        djelitelji[broj_djelitelja].koliko := 0;
        while broj MOD a = 0 do
          begin
            broj := broj DIV a;
            inc(djelitelji[broj_djelitelja].koliko);
          end;
        granica := sqrt(broj);
      end;
    inc(a,2);
  until a > granica;

  if broj > 1 then
    begin
      inc(broj_djelitelja);
      djelitelji[broj_djelitelja].broj := broj;
      djelitelji[broj_djelitelja].koliko := 1;
    end;

  broj_rastava := 0;
  dva_n := 2.0 * n;

  rekurzija(1,1);

  writeln;
  writeln('Rjesenje = ',broj_rastava - 1);
end;

begin
  ucitaj;
  rijesi;
end.

GLISTA2.C

#include <stdio.h>
#include <math.h>

#define MAX_DJELITELJA 10

long n;
struct {
         unsigned long broj;
         int koliko;
       } djelitelji[MAX_DJELITELJA];
int broj_djelitelja,broj_rastava = 0;

void ucitaj (void)
{
  FILE *fp;

  fp = fopen("GLISTA.DAT","rt");

  fscanf(fp,"%ld",&n);

  fclose(fp);
}

void rekurzija (int gdje,unsigned long broj)
{
  int i;
  unsigned long novi_broj;

  if (gdje == broj_djelitelja)
  {
    ++broj_rastava;
    return;
  }

  novi_broj = broj;
  for (i = 0;i <= djelitelji[gdje].koliko;++i)
  {
    if (((double) novi_broj) * (novi_broj - 1) >= 2 * (double) n)
      break;

    rekurzija(gdje + 1,novi_broj);

    novi_broj *= djelitelji[gdje].broj;
  }
}

void rijesi (void)
{
  long broj,a,granica;

  broj = n;
  djelitelji[0].broj = 2l;
  djelitelji[0].koliko = 1;

  while (!(broj % 2))
  {
    broj >>= 1;
    djelitelji[0].broj <<= 1;
  }

  broj_djelitelja = 1;
  granica = (long) floor(sqrt((double) broj));
  a = 3l;

  do
  {
    if (!(broj % a))
    {
      djelitelji[broj_djelitelja].broj = a;
      djelitelji[broj_djelitelja].koliko = 0;
      while (!(broj % a))
      {
        broj /= a;
        ++djelitelji[broj_djelitelja].koliko;
      }
      ++broj_djelitelja;
      granica = (long) floor(sqrt((double) broj));
    }
    a += 2;
  } while (a <= granica);

  if (broj > 1)
  {
    djelitelji[broj_djelitelja].broj = broj;
    djelitelji[broj_djelitelja].koliko = 1;
    ++broj_djelitelja;
  }

  rekurzija(0,1l);

  printf("\nRjesenje = %d\n",broj_rastava - 1);
}

int main (void)
{
  ucitaj();
  rijesi();

  return 0;
}