Submission #38862

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38862	2018-01-07T11:37:15 Z	alenam0161	Riddick's Cube (IZhO13_riddicks)	C++14	100 / 100	23 ms	2016 KB

riddicks

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int R[10];
int C[10];
int M[10][10];
int n, m;

int getCell(int r, int c)
{
	if (r != 0)
	{
		c = (c + R[r - 1]) % m;
	}

	if (c != 0)
	{
		r = (r + C[c - 1]) % n;
	}

	return M[r][c];
}

bool checkRow(int r)
{
	int val = getCell(r, 0);

	for (int i = 1; i < m; i++)
	{
		if (getCell(r, i) != val)
			return false;
	}

	return true;
}

bool checkCol(int c)
{
	int val = getCell(0, c);

	for (int i = 1; i < n; i++)
		if (getCell(i, c) != val)
			return false;
	return true;
}

bool checkRows()
{
	for (int i = 0; i < n; i++)
		if (!checkRow(i))
			return false;
	return true;
}

bool checkCols()
{
	for (int i = 0; i < m; i++)
		if (!checkCol(i))
			return false;
	return true;
}

const int inf = 100500;


int evalCols()
{
	int ans = 0;
	for (int i = 0; i < m; i++)
	{
		ans += min(C[i], n - C[i]);
	}
	return ans;
}

int evalRows()
{
	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		ans += min(R[i], m - R[i]);
	}
	return ans;
}

int caseCheck()
{
	if (checkRows() || checkCols())
	{
		int ans1 = inf;
		int ans2 = inf;

		for (int i = 0; i < m; i++)
		{
			ans1 = min(ans1, evalRows());

			for (int j = 0; j < n; j++)
			{
				R[j]++;
				R[j] %= m;
			}
		}

		for (int i = 0; i < n; i++)
		{
			ans2 = min(ans2, evalCols());
			for (int j = 0; j < m; j++)
			{
				C[j]++;
				C[j] %= n;
			}
		}

		return min(inf, ans1 + ans2);
	}
	return inf;
}

int recCol(int pos)
{
	if (pos == m - 1)
	{
		return caseCheck();
	}

	int ans = inf;

	for (int i = 0; i < n; i++)
	{
		C[pos] = i;
		ans = min(ans, recCol(pos + 1));
	}

	return ans;

}

int recRow(int pos)
{
	if (pos == n - 1)
	{
		return recCol(0);
	}

	int ans = inf;

	for (int i = 0; i < m; i++)
	{
		R[pos] = i;
		ans = min(ans, recRow(pos + 1));
	}

	return ans;
}

int main()
{
//	freopen("riddicks.in", "r", stdin);
//	freopen("riddicks.out", "w", stdout);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> M[i][j];
	cout << recRow(0) << endl;
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2016 KB	Output is correct
2	Correct	0 ms	2016 KB	Output is correct
3	Correct	0 ms	2016 KB	Output is correct
4	Correct	0 ms	2016 KB	Output is correct
5	Correct	0 ms	2016 KB	Output is correct
6	Correct	0 ms	2016 KB	Output is correct
7	Correct	0 ms	2016 KB	Output is correct
8	Correct	0 ms	2016 KB	Output is correct
9	Correct	0 ms	2016 KB	Output is correct
10	Correct	0 ms	2016 KB	Output is correct
11	Correct	0 ms	2016 KB	Output is correct
12	Correct	0 ms	2016 KB	Output is correct
13	Correct	9 ms	2016 KB	Output is correct
14	Correct	13 ms	2016 KB	Output is correct
15	Correct	23 ms	2016 KB	Output is correct
16	Correct	19 ms	2016 KB	Output is correct
17	Correct	9 ms	2016 KB	Output is correct
18	Correct	9 ms	2016 KB	Output is correct
19	Correct	9 ms	2016 KB	Output is correct
20	Correct	9 ms	2016 KB	Output is correct