// https://pydefis.callicode.fr/defis/Hercule04Sanglier/txt
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;

const int N = 60;

// Règles :
// - Le premier bond fait toujours 1m.
// - Chaque nouveau bond peut avoir la même longueur que le précédent ou 2m de plus ou 2m de moins.
// - Pas plus que deux bonds de la même longueur
// - Hercule ne peut creuser des trous qu'entre 20 et 40 inclus
// - Hercule doit creuser le moins de trous possibles

set<vector<int>> sols; // positions des bonds dans la zone 20-40

// Vecteur des positions des bonds du sanglier
void backtrack(vector<int> &bonds, const int jump, const int pos)
{
	if(pos > N) // il faut tomber exactement sur la case 60
	{
		return;
	}
	else if(pos == N) // dernière case
	{
		// Est-ce-qu'il y a plus que deux bonds de la même longueur?
		map<int, int> freq;
		for(size_t i = 1; i < bonds.size(); i++)
			freq[bonds[i] - bonds[i - 1]]++;

		for(auto &elt : freq)
			if(elt.second > 2)
				return;

		for(auto &b : bonds)
			cout << b << ' ';
		cout << '\n';

		vector<int> tmp;
		for(auto &b : bonds)
			if(b >= 20 && b <= 40)
				tmp.push_back(b);
		sols.insert(tmp);
	}
	else // pos < N
	{
		bonds.push_back(pos + jump);

		// Prochain saut de même longueur seulement s'il n'y a pas déjà
		// deux bonds de cette longueur
		int cpt = 0;
		for(size_t i = 1; i < bonds.size(); i++)
			if(bonds[i] - bonds[i - 1] == jump)
				cpt++;

		if(cpt < 2)
		{
			backtrack(bonds, jump, pos + jump);
		}

		// Prochain même longueur moins 2m seulement s'il n'y a pas déjà
		// deux bonds de cette longueur
		if(jump > 2)
		{
			cpt = 0;
			for(size_t i = 1; i < bonds.size(); i++)
				if(bonds[i] - bonds[i - 1] == jump - 2)
					cpt++;

			if(cpt < 2)
			{
				backtrack(bonds, jump - 2, pos + jump);
			}
		}

		// Prochain même longueur plus 2m seulement s'il n'y a pas déjà
		// deux bonds de cette longueur
		cpt = 0;
		for(size_t i = 1; i < bonds.size(); i++)
			if(bonds[i] - bonds[i - 1] == jump + 2)
				cpt++;

		if(cpt < 2)
		{
			backtrack(bonds, jump + 2, pos + jump);
		}

		bonds.pop_back(); // backtrack
	}
} // backtrack()

int main()
{
	vector<int> positions;
	positions.push_back(0);
	backtrack(positions, 1, 0); // position de départ 0, 1er saut de longueur 1

	for(auto &elt : sols)
	{
		for(auto &x : elt)
			cout << x << ' ';
		cout << '\n';
	}

	return 0;
} // main()