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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include "cielib.h"
#include <tuple>
#include <vector>
#include <algorithm>

#define MAX 501
int tmp[MAX];

bool isBetter(const int currentD, const int a, const int b)
{
	tmp[currentD] = a;
	czyCieplo(tmp);
	tmp[currentD] = b;
	return czyCieplo(tmp);
}

std::tuple<bool, bool> isBetterTwoStep(const int currentD, const int a, const int b)
{
	const int before = tmp[currentD];
	const bool step1 = isBetter(currentD, a, b);
	tmp[currentD] = a;
	const bool step2 = czyCieplo(tmp);
	tmp[currentD] = before;
	return std::make_tuple(step1, step2);
}

bool fixPosition(const int currentD, int* from, int* to)
{
	if (from[currentD] == to[currentD] || from[currentD] + 1 == to[currentD])
		return false;

	const int middle = from[currentD] + (to[currentD] - from[currentD]) / 2;
	const std::tuple<bool, bool> better = isBetterTwoStep(currentD, to[currentD], from[currentD]);
	if (std::get<1>(better))
	{
		from[currentD] = middle + 1;
		tmp[currentD] = from[currentD] + (to[currentD] - from[currentD]) / 2;
		return true;
	}
	else if (std::get<0>(better))
	{
		to[currentD] = middle;
		tmp[currentD] = from[currentD] + (to[currentD] - from[currentD]) / 2;
		return true;
	}
	return false;
}

void fixSinglePosition(const int r, const int currentD, int* from, int* to)
{
	if (from[currentD] + 1 != to[currentD])
	{
		const int middle = from[currentD] + (to[currentD] - from[currentD]) / 2;
		from[currentD] = middle;
		to[currentD] = middle;
	}
	else if (to[currentD] < r)
		if (isBetter(currentD, to[currentD]+1, to[currentD]-1))
			to[currentD] = from[currentD];
		else
			from[currentD] = to[currentD];
	else
		if (isBetter(currentD, from[currentD]-1, from[currentD]+1))
			from[currentD] = to[currentD];
		else
			to[currentD] = from[currentD];
}

bool shortenSet(const std::vector <int>& init, int* from, int* to)
{
	std::vector<int> next, current(init);
	bool any = false;
	bool result = true;
	while (result)
	{
		result = false;
		for (int i : current)
			if (fixPosition(i, from, to))
			{
				any = true;
				result = true;
			}
			else
				next.push_back(i);
		if (result)
		{
			current = next;
			next.clear();
		}
	}
	return any;
}

int main()
{
	int from[MAX], to[MAX];
	const int d = podajD();
	const int r = podajR();
	std::vector <int> init;
	for (int i=0; i<d; ++i)
	{
		from[i] = 0;
		to[i] = r;
		tmp[i] = to[i] / 2;
		init.push_back(i);
	}

	bool result = true;
	while (result)
	{
		result = false;
		std::random_shuffle(init.begin(), init.end());
		result |= shortenSet(init, from, to);
	}

	for (int i=0; i<d; ++i)
		if (from[i] != to[i])
			fixSinglePosition(r, i, from, to);
	znalazlem(from);
	return 0;
}