118.acmp | Josephus problem

118.cpp

#include <iostream>
using namespace std;

// ifstream cin ("input.txt");
// ofstream cout ("output.txt");

struct elem
{
	int n;
	elem* next; 
} *nextfree;

void MakeFirst (elem** head, int n)
{
	*head = nextfree++;
	(*head)->n = n;
	(*head)->next = *head;
}

void locate (int k, elem** p)
{
	for (int i = 1; i < k; i++)
		*p = (*p)->next;
}

void insert (elem *p, int n)
{
	elem *t = nextfree++;
	t->next = p->next;
	p->next = t;
	t->n = n;
}

void del (elem *p)
{
	p->next = p->next->next;
}

int main ()
{
	int n, k;
	cin >> n >> k;

	elem *p = nextfree = new elem[n];
	elem *t;
	MakeFirst(&t, n);

	for (int i = n-1; i >= 1; i--)
		insert (t, i);

	for (int i = 1; i < n; i++)
	{
		locate (k, &t);
		del (t);
	}

	cout << t->n << endl;

	delete []p;
}