Josephus

josephus.cpp

// https://algospot.com/judge/problem/read/JOSEPHUS
// time complexity O(kN)
// space complexity O(N)

#include <stdio.h>
#include <list>

using namespace std;

void findAlivePerson(int n, int k) {
  list<int> armyList;
  list<int>::iterator iter_list;
  for (int i = 1; i <= n; i++) {
    armyList.push_back(i);
  }
  int loopCount = 0;
  iter_list = armyList.begin();

  while (loopCount < n - 2) {
    armyList.remove(*iter_list);
    for (int j = 0; j < k; j++) {
      iter_list++;
      //stl list's end() is list's total num
      if (iter_list == armyList.end()) {
        iter_list = armyList.begin();
      }
    }
    loopCount ++;
  }

  printf("%d %d\n", armyList.front(), armyList.back());

}

int main(void) {
  int testCount, i, n, k;
  scanf("%d", &testCount);
  for (i = 0; i < testCount; i++) {
    scanf("%d %d", &n, &k);
    findAlivePerson(n, k);
  }

  return 0;
}