UVa 133

The Dole Queue.cpp

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

auto N = 0;
vector<int> clockwise;
vector<int> anticlockwise;

int reduceByN(int number)
{
	return ((number + N) % (N + 1)) + 1;
}

void initialize()
{
	for (auto i = 1; i <= N; i++)
	{
		anticlockwise.push_back(i);
		clockwise.push_back(N - i + 1);
	}
}

int solve(vector<int> &doleQueue, int number, int &currentPosition)
{
	auto doleQueueLength = doleQueue.size();
	while (number > 0)
	{
		currentPosition = (currentPosition + 1) % doleQueueLength;
		number--;
	}
	return doleQueue[currentPosition];
}

void removeNumber(vector<int> &doleQueue, int number, int &position)
{
	auto resultIterator = find(doleQueue.begin(), doleQueue.end(), number);
	if (resultIterator != doleQueue.end())
	{
		int targetPosition = resultIterator - doleQueue.begin();
		if (position != 0 && targetPosition < position)
		{
			position--;
		}
		else if (targetPosition == position)
		{
			position %= doleQueue.size();
		}

		doleQueue.erase(resultIterator);
	}
}

void printResult(int antiResult, int nonAntiResult, bool isFirstTime)
{
	if (!isFirstTime)
	{
		printf(",");
	}

	printf("%3d", antiResult);
	if (antiResult != nonAntiResult)
	{
		printf("%3d", nonAntiResult);
	}
}

int main()
{
	auto k = 0, m = 0;
	while (~scanf("%d%d%d", &N, &k, &m))
	{
		if (N == 0 && k == 0 && m == 0)
		{
			break;
		}

		initialize();
		k = reduceByN(k);
		m = reduceByN(m);

		auto remainingPeople = N;
		auto anticlockwisePosition = 0;
		auto clockwisePosition = 0;
		while (remainingPeople > 0)
		{
			auto antiResult = solve(anticlockwise, k - 1, anticlockwisePosition);
			auto nonAntiResult = solve(clockwise, m - 1, clockwisePosition);

			removeNumber(anticlockwise, antiResult, anticlockwisePosition);
			removeNumber(anticlockwise, nonAntiResult, anticlockwisePosition);
			removeNumber(clockwise, nonAntiResult, clockwisePosition);
			removeNumber(clockwise, antiResult, clockwisePosition);

			printResult(antiResult, nonAntiResult, remainingPeople == N);
			remainingPeople -= (antiResult == nonAntiResult) ? 1 : 2;
		}
		cout << endl;
	}
	return 0;
}