// Compiler: Gcc 14.0.0 experimental 2023-12-24
// http://www.equation.com/servlet/equation.cmd?fa=fortran
// g++ -O3 -std=c++23 -Wall dsds_max.cpp  -lstdc++exp -o dsds_max

#include <algorithm>
#include <chrono>
#include <iostream>
#include <vector>

int dreieckszahl(int n)
{
	return n*(n+1)/2;
}	

int index(int i, int j)
{
	return dreieckszahl(i)+j;
}

int dreiecksumme(std::vector<int> liste, int n)
{
	int summe = 0;
	for (int i = 1; i < n; ++i)
	{
		for (int j = 1; j <= i; ++j)
		{
			int zahl1 = liste[index(i,j)];
			int zahl2 = liste[index(i,j-1)];
			int zahl3 = liste[index(i-1,j-1)];
			int diff = std::abs(zahl1-zahl2) + std::abs(zahl2-zahl3) + std::abs(zahl3-zahl1);
			summe += diff;
		}
	}		
	return summe;
}

void ausgabe(std::vector<int> liste, int n)
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			if (j > 0) std::cout << " ";
			std::cout << liste[index(i,j)];
		}
		std::cout << '\n';
	}
	std::cout << "DSDSmax=" << dreiecksumme(liste,n) << '\n';
}

void solve(int n)
{
	int anzahl = dreieckszahl(n);
	std::vector<int> liste(anzahl);
	for (int i = 0; i < anzahl; ++i) liste[i] = i;

	auto beste_liste = liste;
	int DSDSmax = 0;

	do
	{
		if (int ds = dreiecksumme(liste, n); ds > DSDSmax)
		{
			DSDSmax = ds;
			beste_liste = liste;
		}
	} while (std::ranges::next_permutation(liste).found);

	ausgabe(beste_liste, n);
}

int main()
{
	for (int n = 0; n < 6; ++n)
	{
		auto start{std::chrono::steady_clock::now()};
		solve(n);	
		auto end{std::chrono::steady_clock::now()};
		std::cout << std::chrono::duration<double>{end - start} << '\n'; 
	}
}