UVa -Power Crisis

During the power crisis in New Zealand this winter (caused by a shortage of rain and hence low levels in the hydro dams), a contingency scheme was developed to turn off the power to areas of the country in a systematic, totally fair, manner. The country was divided up into N regions (Auckland was region number 1, and Wellington number 13). A number, m, would be picked `at random', and the power would first be turned off in region 1 (clearly the fairest starting point) and then in every m'th region after that, wrapping around to 1 after N, and ignoring regions already turned off. For example, if N = 17 and m = 5, power would be turned off to the regions in the order:1,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,7.

The problem is that it is clearly fairest to turn off Wellington last (after all, that is where the Electricity headquarters are), so for a given N, the `random' number m needs to be carefully chosen so that region 13 is the last region selected.

Write a program that will read in the number of regions and then determine the smallest number m that will ensure that Wellington (region 13) can function while the rest of the country is blacked out.

Input and Output

Input will consist of a series of lines, each line containing the number of regions (N) with  . The file will be terminated by a line consisting of a single 0.

Output will consist of a series of lines, one for each line of the input. Each line will consist of the number m according to the above scheme.

Sample input

17
0

Sample output

7

출처: https://uva.onlinejudge.org/

1부터 N까지의 지역이 있다고 할 때 정전이 되는 순서가 1, 1+m, 1+m+m ....이라고 할 때 13번 지역이 마지막 순서가 될 수 있는 m을 구하는 문제입니다. 마지막 N 다음 순서는 1으로 순환되며, 이미 정전이 된 지역은 순서를 샐 때 제외하는 규칙입니다.

이 문제는 요세푸스(Josephus) 문제와 비슷한 문제라 생각됩니다. 풀이는 queue 를 이용해 선택된 지역을 꺼내고 다음 선택지가 나올 때 까지 꺼낸 후 뒤로 다시 집어 넣는 방법을 사용했습니다.

my solving 

c++

#include<iostream>
#include <queue>
 
using namespace std;
 
int last = 13;
 
int CalcByQueue(int N)
{
    for (int m = 1; m <= N; m++)
    {
        queue<int> survivors;
        for (int j = 1; j <= N; j++)
            survivors.push(j);
 
        while (survivors.size() > 1)
        {
            survivors.pop();
 
            for (int i = 0; i < m - 1; i++) {
                survivors.push(survivors.front());
                survivors.pop();
            }
        }
 
        if (survivors.front() == last)
        {
            return m;
        }
    }
    return 0;
}
int main()
{
    int N;
        
    while (true)
    {
        cin >> N;
        if (N == 0)
            break;
 
        cout << CalcByQueue(N) << endl;
    }
 
    return 0;
}