1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <array>
#include <iostream>
#include <limits>
#include <vector>

struct oddzial_t
{
	int zgrzytow;
	std::vector<short> zolnierze;
};

int main()
{
	short wszystkich;
	std::array<int, 45> permutacja;
	std::array<std::array<int, 45>, 45> zgrzyty;
	
	std::cin >> wszystkich;
	
	for (short i = 0; i < wszystkich; ++i)
	{
		std::cin >> permutacja[i];
		--permutacja[i];
	}

	std::vector<oddzial_t> oddzialy{};
	
	for (short z = 0; z < wszystkich; ++z)
	{
		oddzialy.push_back({0, {z}});
		for (short z2 = z + 1; z2 < wszystkich; ++z2)
		{
			zgrzyty[z][z2] = (permutacja[z] > permutacja[z2]);
		}
	}
	
	std::cout << 0 << ' ' << wszystkich << std::endl;
	
	std::vector<oddzial_t> nowe_oddzialy;
	
	for (short i = 1; i < wszystkich; ++i)
	{
		int min_zgrzytow = std::numeric_limits<int>::max();
		int najlepszych_oddzialow = 0;
		for (const auto &oddzial: oddzialy)
		{
			for (int z = oddzial.zolnierze.back() + 1; z < wszystkich; ++z)
			{
				int zgrzytow = oddzial.zgrzytow;
				for (const auto &w_oddziale: oddzial.zolnierze)
				{
					zgrzytow += zgrzyty[w_oddziale][z];
				}
				if (zgrzytow < min_zgrzytow)
				{
					min_zgrzytow = zgrzytow;
					najlepszych_oddzialow = 1;
				}
				else if (zgrzytow == min_zgrzytow)
				{
					++najlepszych_oddzialow;
				}
				oddzial_t nowy_oddzial = {zgrzytow, oddzial.zolnierze};
				nowy_oddzial.zolnierze.push_back(z);
				nowe_oddzialy.push_back(nowy_oddzial);
			}
		}
		
		std::cout << min_zgrzytow << ' ' << najlepszych_oddzialow << std::endl;
		
		oddzialy.clear();
		oddzialy.swap(nowe_oddzialy);
	}
}