Submission #116668

#	Time	Username	Problem	Language	Result	Execution time	Memory
116668		emilem	Board (CEOI13_board)	C++14	40 / 100	10 ms	640 KiB

board

#include <cassert>
#include <algorithm>
#include <iostream>
#include <string>
using std::swap;

long long Depth(const std::string& a)
{
	int depth = 0;
	for (auto dir = a.begin(); dir != a.end(); ++dir)
		if (*dir == 'U')
			--depth;
		else if (*dir == '1' || *dir == '2')
			++depth;
	assert(depth >= 0);
	return depth;
}
long long Coord(const std::string& a)
{
	long long coord = 0;
	for (auto dir = a.begin(); dir != a.end(); ++dir)
		switch (*dir)
		{
		case '1':
			coord *= 2; break;
		case '2':
			coord *= 2;
			++coord; break;
		case 'L':
			--coord; break;
		case 'R':
			++coord; break;
		case 'U':
			coord /= 2;
		}
	return coord;
}
int main()
{
	std::string path;
	std::cin >> path;
	long long aDepth = Depth(path);
	long long aCoord = Coord(path);
	std::cin >> path;
	long long bDepth = Depth(path);
	long long bCoord = Coord(path);
	if (aDepth > bDepth)
	{
		swap(aDepth, bDepth);
		swap(aCoord, bCoord);
	}
	long long depthSteps = bDepth - aDepth;
	while (bDepth > aDepth)
	{
		bCoord /= 2;
		--bDepth;
	}
	long long ans = depthSteps + std::abs(aCoord - bCoord);
	while (--aDepth && --bDepth)
	{
		depthSteps += 2;
		aCoord /= 2; bCoord /= 2;
		ans = std::min(ans, depthSteps + std::abs(aCoord - bCoord));
	}
	std::cout << ans << std::endl;

	char I;
	std::cin >> I;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10