/*
Subject: #151 Power Crisis
e-mail: morcavon@gmail.com
Homepage: http://www.morcavon.com
Building: 09/06/2005 ~ 10/06/2005
Last Update: 10/06/2005
*/
/*
<PURPOSE>
For a given N, the 'random' number m needs to be carefully choosen
so that region 13 is the last region selected.
-
<PREDICATE>
It start from region 1 and every m'th region after that, wrapping around 1 after N,
and ignore regions already choosen.
13 <= N < 100
-
<INPUT>
N N: Total number of regions
...
0 0: termination character
-
<OUTPUT>
m m: proper region's number
...
*/
#include <iostream>
using namespace std;
#include <cstring> // memset
#include <iomanip>
#define ONLINE_JUDGE
const int LAST = 13;
short processing(short n);
short processing2(short n);
int main()
{
short n;
#if 1
while (cin >> n) {
if (n == 0)
break;
cout << processing(n) << '\n';
}
#endif
#if 0 // 냐하하=_=;;;;; 따라하지마셈~후후
short sol[90] = {1,-1,10,11,7,17,11,15,-1,5,21,13,-1,14,11,23,22,9,-1,17,-1,7,-1,15,-1,22,
-1,24,30,9,38,15,-1,27,9,-1,38,22,19,-1,38,53,-1,-1,-1,20,9,22,7,21,-1,
-1,41,10,-1,-1,64,-1,-1,-1,67,19,66,-1,52,24,22,-1,10,57,-1,-1,41,70,60,
-1,81,79,55,-1,49,5,22,54,52,-1,15};
for (short i = 13; i < 100; i++)
cout << setw(4) << i << setw(4) << processing(i) << '\n';
/* while (cin >> n) {
if (n == 0)
break;
cout << sol[n-13] << '\n';
}
*/
#endif
return 0;
}
short processing(short n)
{
unsigned short m;
unsigned short bit[7]; // 16 * 7 = 112 bit
unsigned short idx, i, j, cnt; // idx: bit[] array index
unsigned short remain;
if (n == LAST)
return 1;
for (m = 2; m < n; m++) {
if ((LAST - 1) % m == 0)
continue;
// 모든 비트가 0인 상태로 시작
memset(bit, 0, sizeof(unsigned short)*7);
// 항상 0번 위치에서 부터 시작하므로 0번은 미리 체크한 상태로 시작
bit[0] = 0x8000;
remain = n;
for (i = j = m, cnt = m - 1; remain > 1; i++) { // i는 루프마다 증가, cnt는 선택적
// mask를 m만큼 시프트한 후 해당 bit[]를 1로 설정
// i: 전체 비트상의 위치
// 배열의 인덱스와 offset(j) 계산(실제 배열상의 위치)
if (i == n) // 경계를 넘어가면 다시 처음으로...
i = 0;
idx = i >> 4; // i / 16;
j = i - (unsigned short)(idx << 4); // i = i - (idx * 16)
// 비트가 이미 설정된 경우는 스킵~~
if ((unsigned short)(bit[idx] << j) >> 15 != 0x0001)
cnt++;
// m만큼 시프트
if (cnt == m) {
if (i == LAST - 1) {
if (remain == 2) // 찾았다!! @_@
return m;
else
break; // 중간에 LAST가 걸리면 바로 중지~
}
cnt = 0;
remain--;
bit[idx] |= 0x8000 >> j;
#ifndef ONLINE_JUDGE
cout << i + 1 << ' ';
#endif
}
} // 하나의 m에 대한 실행
#ifndef ONLINE_JUDGE
cout << "m = " << m << "remain = " << remain << '\n';
#endif
}
return -1;
}
// 또 다른 버전=_=. LAST부터 거꾸로 올라가면서 체크...
// ........귀찮네..나중에 해야지....
short processing2(short n)
{
/*
LAST(끝점) 부터 거꾸로(left)로 거슬러 올라감. m은 1부터 N까지...
진행중에 #1(시작점)을 만났을 때 아직 처리하지 못한 region이 남아 있다면 실패로 간주..
m이 LAST - 1의 소인수일때는 무시(이 경우 중간에 #1을 만나게 된다)
*/
return 0;
}
