/* Josephus em O(n lg n)                                         */
/* Compilado no Borland C++ 4.02                                 */
/* Preparado por Mario Leston Rey para a disciplina de MAC324    */
/* sob supervisao do Professor Yoshiharu Kohayakawa              */

#include<stdio.h>
#include<stdlib.h>

/* Seja X um conjunto de inteiros. O posto de um elemento x em X */
/* eh o numero de elementos estritamente menores que x em X      */

typedef struct no *no_ptr;

struct no
{
         int pessoa;
         int tamanho;
         no_ptr esq;
         no_ptr dir;
};

no_ptr
cria_arvore( int min, int max )
/* Recebe inteiros min e max e devolve a raiz de uma arvore binaria */
/* balanceda (ito eh, cuja altura eh lg (max - min + 1)) cujos      */
/* elementos estao no conjunto {min, min + 1, ..., max - 1, max}    */ 
{
        no_ptr r = NULL;
        int centro = (min + max) / 2;

        if (min <= max)
        {
                if (!(r = (no_ptr) malloc (sizeof (struct no))))
                  return NULL;
                r->pessoa = centro; r->tamanho = max - min + 1;
                r->esq = cria_arvore(min, centro - 1);
                r->dir = cria_arvore(centro + 1, max);
        }
        return r;
}

int
eliminacao( no_ptr *r, int p )
/* Recebe a raiz *r de uma arvore binaria (denote por T tal arvore) */
/* e um inteiro p. Seja x o no de T cujo posto eh p. Devolve em *r  */
/* a raiz da arvore binaria obtida removendo-se x de T.             */
/* Devolve o numero da pessoa eliminada.                            */
{

        no_ptr *x = r, *y, aux;
        int eliminado;

        while (1)
        {
                /* Busca pelo elemento cujo posto eh p */
                int posto = (*x)->esq ? (*x)->esq->tamanho + 1 : 1;

                (*x)->tamanho--;

                if (posto == p) break;

                if (posto > p) x = &((*x)->esq);
                else
                {
                        p = p - posto;
                        x = &((*x)->dir);
                }
        }
        /* Neste ponto *x aponta para o elemento cujo posto eh p */
        eliminado = (*x)->pessoa;

        /* Remove *x da arvore. Perceba que o algoritmo abaixo nao  */
        /* garante que a arvore binaria resultante seja balanceada, */
        /* mas como a remocao de um elemento nao aumenta a altura   */
        /* da arvore segue que o tempo para remocao eh de O(lg n0)     */
        /* onde n0 eh o tamanho original da arvore. Isto eh suficiente */
        /* para obtermos um algoritmo de complexidade O(n0 lg n0).     */
        if ((*x)->esq && (*x)->dir)
        {
                y = &((*x)->dir);
                while ((*y)->esq)
                {
                        (*y)->tamanho--;
                        y = &((*y)->esq);
                }
                /* Neste ponto *y aponta para o sucessor em ordem de *x */
                (*x)->pessoa = (*y)->pessoa;
                aux = *y; *y = (*y)->dir; free(aux);
        }
        else
        {
                aux = *x;
                *x = (*x)->esq ? (*x)->esq : (*x)->dir;
                free(aux);
        }

        return eliminado;
}

void
main( int argc, char *argv[] )
{
  int m, n, p = 1;
  no_ptr r;

  if (argc != 3)
                fprintf(stderr, "uso: %s <numero de pessoas> <execucao>\n", argv[0]);
  else
  {
                n = atoi(argv[1]); m = atoi(argv[2]);
                if ((n <= 0) || (m <= 0))
                        fprintf(stderr, "<numero de pessoas> e <execucao> devem ser "
                                                                 "estritamente maiores que 0\n");
                else
                {
                        if (!(r = cria_arvore (1, n)))
                                fprintf(stderr, "Nao ha espaco disponivel!", n);
                        else
                        {
                                while (n)
                                {
                                        if (!(p = (p + m - 1) % n)) p = n;

                                        if (n > 1)
                                                fprintf (stdout, "%d, ", eliminacao(&r, p));
					else
						fprintf (stdout, "%d", eliminacao(&r, p));
					n--;
				}
			}
		}
		printf("\n");
	}
}