/***********************************************************
* Section 15
* M/c No : M
* Roll No : 18CS100XY
* Names : Soumyajit Dey, Aritra Hazra
* Assignment No : 4b
* Description : Program to find survivor in Josephus Problem
***********************************************************/

#include <stdio.h>
#define MAX 1000000

int main()
{
  int person[MAX];
  int n, m, i, j,  order;

  // user input
  printf("Enter Number of Persons: ");
  scanf("%d", &n);
  printf("Enter Elimination Gap: ");
  scanf("%d", &m);

  // initializing / unmarking all persons
  for ( i=0; i<n; i++ ) {
    person[i] = 0;
  }
  i = n-1; // initialization considering a circular array
  // n-1 person will be eliminated iteratively
  for ( order=1; order<n; order++ ) {
    j = 1;
    while ( j <= m ) { // determining next person to be eliminated
      i = (i+1)%n;
      if ( person[i] == 0) {
        j++; // incrementing gap count only w.r.t. non-eliminated person
      }
    }
    person[i] = order; // next person eliminated
  }

  //printing output
  printf("The Elimination Order:\n");
  for(i=0; i<n; i++){
    if ( person[i] == 0 ) {
      printf("Person #%d Survives!!\n", i);
    }
    else {
      printf("Person #%d eliminated at Step #%d\n", i, person[i]);
    }
  }
  return 0;
}