Задача Иосифа Флавия

Сложность - 19%

Условие:

Существует легенда, что Иосиф Флавий - известный историк первого века - выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным - он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю…

В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от 1 до N, и будем исключать каждого k-ого до тех пор, пока не уцелеет только один человек.

Например, если N=10, K=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.

Требуется написать программу, которая по заданным N и K будет определять номер уцелевшего человека.

Входные данные

    Входной файл INPUT.TXT содержит два натуральных числа N и K. Ограничения: N<=500, K<=100.

Выходные данные

    В выходной файл OUTPUT.TXT нужно вывести номер уцелевшего человека.

Решение задачи:

#include<iostream> 

using namespace std; 
int n,k,c,x,a[550]; 
int main()
{ 
    freopen("input.txt","r",stdin); 
    freopen("output.txt","w",stdout); 
    
    cin>>n>>k; 
    while (c<n-1)
    { 
       for (int i=1;i<=k;i++)
       { 
            x++;
            if (x>n) x-=n; 
            if (a[x]==1)
            { 
                while (a[x]==1)
                { 
                    x++; 
                    if (x>n) x=x-n; 
                } 
            } 
        } 
        a[x]=1; 
        c++; 
    } 
for (int i=1;i<=n;i++)
    if (a[i]==0) cout<<i; 
}