/*
Subject: #130 Roman Roulette
e-mail: morcavon@gmail.com
Homepage: http://www.morcavon.com
Building: 09/03/2005 ~ 10/03/2005
Last Update: 10/03/2005
*/
/*
<INPUT>
n k n: # of people
. k: # to kill
.
0 0 0 0: termination line
-
<OUTPUT>
i i: safe starting point
.
.
-
<CONDITION>
0 < n <= 100
My allocated number is 1.
The numbering from 1 to n proceeds consecutively in a clockwise direction.
After one person killed, The person number further k so selected
has the job of burying the victim, and then returning to the position
in the circle that the victim had previously oppucied.(swap)
*/
#include <iostream>
using namespace std;
const int MAX = 100;
// circular queue로 구현...
typedef struct Person* pPerson;
struct Person
{
char locate;
pPerson link;
};
void init(pPerson people, int n);
int roulette(pPerson person, int k);
pPerson jump2kill(pPerson person, int j);
pPerson jump2bury(pPerson person, int j);
pPerson last_person(pPerson person);
int main()
{
int n, k;
int i;
/*
최대 인원수만큼 배열을 만들어 링크를 설정하고
매 반복수행때마다 재설정해서 사용...
*/
pPerson people = new Person[MAX];
while (cin >> n >> k) {
if (!n || (!n&& !k))
break;
for (i = 0; i < n; i++) { // 첫번째 위치부터 다 조사해 보자=_=
init(people, n);
if (roulette(&people[i], k) == 1) { // 나는 살았다!!! 냐하하~~ @_@
cout << i + 1 << endl;
break;
}
} // end of one circle with start position i
} // end of one input sequence
return 0;
}
void init(pPerson people, int n)
{
int i;
n--; // 마지막 원소는 수행안함
for (i = 0; i < n; i++) {
people[i].locate = i + 1;
people[i].link = &people[i+1];
}
people[i].locate = i + 1;
people[i].link = &people[0]; // 마지막 원소 다음에 처음 원소가 오게끔...
}
int roulette(pPerson person, int k)
{
/*
룰렛을 돌려 사람을 죽이고(=_=) 최후에 남은 사람의 번호(locate)를 리턴
people: 시작 위치, k: 죽을 차례
---
우선 k번째 사람을 죽이고,
거기서 k번째 사람이 죽은 사람을 묻으러 가서 죽은 사람의 자리로 복귀,
죽은 사람의 바로 다음 사람부터 다시 시작
*/
pPerson pre_kill, pre_bury; // 죽을 사람과 묻을사람의 바로 전 사람
pPerson killed, bury; // 죽은 사람의 위치(나중에 묻으러 간 사람이 돌아와야 할 자리)
// 묻으러 간 사람
while (person != person->link) { // 한사람만 남을 때까지 돌아돌아~ @_@
pre_kill = jump2kill(person, k);
killed = pre_kill->link;
pre_kill->link = killed->link; // 죽은 사람을 빼고 서클을 만듬
person = killed->link; // 다음 시작 위치는 계속 추적해야 할듯...
pre_bury = jump2bury(person, k); // 묻으러 갈 사람의 전 사람
bury = pre_bury->link;
pre_bury->link = bury->link; // 묻으러 간 사람을 서클에서 제외
// 묻으러 갈 사람이 시작위치(person)에 있다면 시작위치를 다음으로 넘긴다.
if (bury == person)
person = bury->link;
last_person(person)->link = bury; // 묻고 와서 죽은 사람의 자리로 들어간다.
bury->link = person;
}
return person->locate;
}
pPerson jump2kill(pPerson person, int j)
{
// j번째 위치한 죽을 사람의 바로 전 사람을 리턴
while (--j > 1)
person = person->link;
return person;
}
pPerson jump2bury(pPerson person, int j)
{
// 죽은사람을 묻으러 갈 사람(person에서 j번째 사람)의 "전"포인트를 리턴.
while (--j > 1)
person = person->link;
return person;
}
pPerson last_person(pPerson person)
{
// 서클에서 person을 시작으로 해서 마지막 사람를 리턴
pPerson w_ptr;
for (w_ptr = person; w_ptr->link != person; w_ptr = w_ptr->link)
;
return w_ptr;
}
