Algorithm


Problem Name: 2 AD-HOC - beecrowd | 1031

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1031

Power Crisis

 

Unknown Author

Timelimit: 1

During a power crisis in New Zealand last 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 the region of Wellington by 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

 

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

 

Output

 

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.

 

 

 

Input Sample Output Sample

17
0

7

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>

int remaining(int n, int k) {
    int r = 0;
    for (int i = 1; i  <  n; i++)
        r = (r + k) % i;

    return r;
}

int main(){
    int n, x, y, j, num, pulo;
    while(1){
           scanf("%d",&n);
           if(n == 0) break;
           y = 1;
           for(;;){
                   if(remaining(n,y) != 11) y++;
                   else break;
           }
           printf("%d\n",y);
    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
17
0

Output

x
+
cmd
7

#2 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#include <deque>
#define MAXN 301
using namespace std;
int dp[MAXN][MAXN], vetor[MAXN];
void solve(int n, int m) {
    deque < int> simula;
    for (int i = 1; i  < = n; i++) {
        simula.push_back(i);
    }
    int cortados = 0;
    while (simula.size() != 1) {
        int davez = simula.front();
        simula.pop_front();
        if (cortados % m != 0) simula.push_back(davez);
        cortados++;
    }
    dp[n][m] = simula.front();
}
int main() {
    for (int i = 1; i  < = 100; i++) {
        for (int j = 1; j  <  MAXN; j++) {
            solve(i, j);
            if (dp[i][j] == 13) {
                vetor[i] = j;
                break;
            }
        }
    }
    int escolhido;
    while (scanf("%d", &escolhido) && escolhido) {
        printf("%d\n", vetor[escolhido]);
    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
17
0

Output

x
+
cmd
7

#3 Code Example with Python Programming

Code - Python Programming


def res(x,aux):
    aux1=0
    i=1
    while i < x:
        aux1=(aux1+aux)%i
        i+=1
    return aux1
while True:
    x=int(input())
    if x==0:break
    aux=1
    while res(x,aux)+2!=13:aux+=1
    print(aux)
Copy The Code & Try With Live Editor

Input

x
+
cmd
17
0

Output

x
+
cmd
7
Advertisements

Demonstration


Previous
#1030 Beecrowd Online Judge Solution 1030 Flavious Josephus Legend Solution in C, C++, Java, Python and C#
Next
#1032 Beecrowd Online Judge Solution 1032 Joseph’s Cousin Solution in C, C++, Java, Js and Python