/*************************************************************
* Section : 15
* Machine No. : N
* Roll No. : 19CS100XY
* Name : Aritra Hazra
* Assignment No : 10b
* Description : Josephus Problem using Circular Linked Lists
*************************************************************/

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

typedef struct _node {
    int number;
    struct _node *next;
} node;

int main ()
{
    node *head, /* the header */
         *p; /* the running pointer (prosecutor)*/
    int n, m, i;

    printf("Enter n: ");
    scanf("%d", &n);
    printf("Enter m: ");
    scanf("%d", &m);

    /* Allocate memory for the first node*/
    p = head = (node *)malloc(sizeof(node));
    p -> number = 1;

    /* Allocate memory for the remaining nodes*/
    for (i=2; i<=n; ++i) {
        p -> next = (node *)malloc(sizeof(node));
        p = p -> next;
        p -> number = i;
    }

    /* Let the last link point to the head*/
    p -> next = head;

    /* As long as there are two or more living convicts*/
    while ( p -> next != p ) {
        /* Skip m-1 convicts */
        for (i=1; i < m ; ++i)
            p = p -> next;
        printf("Convict %d Killed!\n", p -> next -> number );

        /* Delete the node from the list*/
        p -> next = p -> next -> next;
    }
    printf("==> Convict %d Survives!\n", p -> number );
    
    return 0;
}