#!/usr/bin/perl

package Gyujtohely;

use strict;

use constant TAVOLSAG	=> 0;
use constant TOMEG	=> 1;

sub new {
	my $class = shift;
	my $self = [@_];
	bless $self, $class;
	return $self;
}

sub tavolsag {
	my $self = shift;
	return $self->[TAVOLSAG];
}

sub tomeg {
	my $self = shift;
	return $self->[TOMEG];
}

1;

package Matrix;

sub new {
	my $class = shift;
	my $self = [];
	bless $self, $class;
	return $self;
}

sub value : lvalue {
	my $self = shift;
	my ($i1, $i2) = @_;
	$self->[$i1]->[$i2];
}

sub print {
	my $self = shift;
	printf("%8s ", "");
	for (my $i1 = 0; $i1 < @$self; $i1++) {
		printf("    [%2d] ", $i1);
	}
	print "\n";
	for (my $i1 = 0; $i1 < @$self; $i1++) {
		printf("    [%2d] ", $i1);
		my $dim2 = $self->[$i1];
		for(my $i2 = 0; $i2 < @$dim2; $i2++) {
			my $v = $dim2->[$i2];
			if ($v) {
				printf("%8d ", $v);
			} else {
				printf("%8s ", "-");
			}
		}
		print "\n";
	}
}

1;

package main;

use strict;

# Kiszamoljuk az osszes esetben, hogy ket gyujto kozotti szallitasnak mekkora koltsege van (nem szamolva a kozbeeso gyujtok szallitasait)
# CPU & memoria: O(gyujtohely^2)
sub calcKoltsegMatrix {
	my ($gyujtok) = @_;

	my $koltsegMatrix = Matrix->new;
	for (my $start = $#{$gyujtok}; $start >= 0; $start--) {
		for (my $cel = $start; $cel >= 0; $cel--) {
			$koltsegMatrix->value($start, $cel) = $gyujtok->[$start]->tomeg * ($gyujtok->[$start]->tavolsag - $gyujtok->[$cel]->tavolsag);
		}
	}

	$koltsegMatrix->print;
	print "\n";

	return $koltsegMatrix;
}


# Kiszamoljuk az osszes esetben, hogy ket gyujto kozotti szallitasnak mekkora koltsege van, beleertve a kozbeeso gyujtok szallitasait is
# CPU & memoria: O(gyujtohely^2)
sub calcAggregaltKoltsegMatrix {
	my ($gyujtok) = @_;

	my $koltsegMatrix = calcKoltsegMatrix($gyujtok);

	my $aggregaltKoltsegMatrix = Matrix->new;
	for (my $cel = 0; $cel <= $#{$gyujtok}; $cel++) {
		my $aggregaltKoltseg = 0;
		for (my $start = $cel; $start <= $#{$gyujtok}; $start++) {
			$aggregaltKoltsegMatrix->value($start, $cel) = $aggregaltKoltseg += $koltsegMatrix->value($start, $cel);
		}
	}

	$aggregaltKoltsegMatrix->print;
	print "\n";

	return $aggregaltKoltsegMatrix;
}

# Megkeressunk rekurzivan, hogy a megadott ket gyujto kozott hol a legoptimalisabb elhelyezni a megadott szamu malmot
# Visszaadja a malmok listajat es a hozza tartozo koltseget 
# CPU: O( malomSzam * gyujtohely * ln(gyujtohely) )
# memoria: O(malomSzam)
sub getOptimalisMalomLista {
	my ($start, $cel, $malomSzam, $alapKoltseg, $aggregaltKoltsegMatrix) = @_;
	#print "getMinKoltseg($start, $cel, $malomSzam, $alapKoltseg)\n";

	if (!$malomSzam) {
		# Ha mar nem kell ujabb malmot elhelyezni, akkor csak visszaadjuk a start es a cel kozotti koltseget es egy ures malom listat
		return ([], $alapKoltseg + $aggregaltKoltsegMatrix->value($start, $cel));
	} else {
		my $optIdxList;
		my $minKoltseg;

		# Ha a start es a cel megegyezik, az azt jelenti, hogy a celba mar nem tudunk malmot elhelyezni, igy hibas eset
		return undef unless $start > $cel;

		# Vegigprobaljuk a megadott start es cel kozott, hogy hova lehet malmot elhelyezni
		for (my $malom = $start; $malom > $cel; $malom--) {
			# Kiszamoljuk, hogy a maradek (1-gyel kevesebb) malmot hogyan lehet optimalisan elhelyezni
			# az aktualis pozicio utani fennmarado gyujtohelyekre a celig
			my ($recIdxList, $koltseg) =
				&getOptimalisMalomLista($malom - 1, $cel, $malomSzam - 1, $alapKoltseg + $aggregaltKoltsegMatrix->value($start, $malom), $aggregaltKoltsegMatrix);

			# Ha a visszakapott koltseg nem definialt, akkor ez egy ervenytelen eset es inkabb tovabb kell probalkoznunk egy ujabbal
			next unless defined($koltseg);

			# Megnezzuk, hogy az probalt malom pozicioval optimalisabb-e a koltseg vagy sem
			# (Ha eddig meg nem szamoltunk koltseget, akkor automatikusan ez a legjobb)
			if (!defined($minKoltseg) || $koltseg < $minKoltseg) {
				# Eltaroljuk ezt a legoptimalisabb koltseget, hogy a tovabbi probalkozasokat osszevethessuk vele
				$minKoltseg = $koltseg;
				# Eltaroljuk a maradek malmok optimalis pozicioinak listajat kiegeszitve az aktulisan vizsgalt malom pozicioval
				$optIdxList = [$malom, @$recIdxList];
			}
		}


		# Visszaterunk az eredmenyekkel
		return ($optIdxList, $minKoltseg);
	}

}

sub calcOptimalisMalomPos {
	my ($gyujtok, $malomSzam, $aggregaltKoltsegMatrix) = @_;
	my ($malomLista, $minKoltseg) = getOptimalisMalomLista($#{$gyujtok}, 0, $malomSzam, 0, $aggregaltKoltsegMatrix);
	print "EREDMENY #$malomSzam: [", join(', ', map { $_ + 1 } @$malomLista), "] ($minKoltseg)\n";
}

my $gyujtok = [
	Gyujtohely->new(0, 1),
	Gyujtohely->new(2, 2),
	Gyujtohely->new(3, 3),
	Gyujtohely->new(6, 44),
	Gyujtohely->new(7, 5),
	Gyujtohely->new(20, 6),
	Gyujtohely->new(22, 33),
	Gyujtohely->new(34, 18),
	Gyujtohely->new(35, 9),
	Gyujtohely->new(44, 10),
	Gyujtohely->new(57, 11),
	Gyujtohely->new(66, 2),
	Gyujtohely->new(88, 13),
	Gyujtohely->new(100, 44),
];

my $aggregaltKoltsegMatrix = calcAggregaltKoltsegMatrix($gyujtok);

# 1 fureszmalom
calcOptimalisMalomPos($gyujtok, 1, $aggregaltKoltsegMatrix);

# 2 fureszmalom
calcOptimalisMalomPos($gyujtok, 2, $aggregaltKoltsegMatrix);

# 3 fureszmalom
calcOptimalisMalomPos($gyujtok, 3, $aggregaltKoltsegMatrix);

# 4 fureszmalom
calcOptimalisMalomPos($gyujtok, 4, $aggregaltKoltsegMatrix);