Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1032
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1032
Joseph’s Cousin
Unknown Author
Timelimit: 1
The Joseph’s problem is notoriously known. For those who are not familiar with the problem, among people numbered 1,2…n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give the message about the incident.
Although many good programmers have been saved since Joseph spread out this information, Joseph’s cousin introduced a new variant of the malignant game. This insane character is known for its barbarian ideas and wishes to clean up the world from silly programmers. We had to infiltrate some agents of the ACM in order to know the process in this new mortal game.
In order to save yourself from this evil practice, you must develop a tool capable of predicting which person will be saved.
The Destructive Process
The persons are eliminated in a very peculiar order; m is a dynamical variable, which each time takes a different value corresponding to the prime numbers’ succession (2,3,5,7…). So in order to kill the ith person, Joseph’s cousin counts up to the ith prime.
Input
It consists of separated lines containing n [1..3501], and finishes with a 0.
Output
The output will consist in separated lines containing the person's position which the life will be saved.
| Input Sample | Output Sample |
|
6 |
4 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
short eprimo(int n) {
int i;
if (n == 2) return 1;
if (n == 1 || n % 2 == 0) return 0;
for (i = 3; i < = sqrt(n); i += 2)
if (n % i == 0) return 0;
return 1;
}
int prox(int n) {
while (!eprimo(++n));
return n;
}
int main(void) {
int n, j, m, i, k, p;
char *v = 0;
while (scanf("%d", &n) == 1 && n) {
v = (char *) malloc(n * sizeof(char));
for (j = 0; j < n; ++j) v[j] = 1;
m = p = i = 0;
k = 2;
while (m < n-1) {
if (v[i] == 1) ++p;
if (p == k) {
v[i] = 0;
++m;
p = 0;
k = prox(k);
}
++i;
if (i == n) i = 0;
}
for (j = 0; v[j] == 0; ++j);
printf("%d\n", j+1);
}
free(v);
return 0;
}
Input
0
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <stdio.h>
#include <math.h>
#include <cstring>
int prime[3502];
int flavious(int n) {
int r = 0;
for (int i = 1; i < = n; i++){
r = (r + prime[n-i]) % i;
}
return r;
}
int isPrime(int n) {
int i;
if(n == 2) return 1;
if(n%2 == 0) return 0;
for(i = 3; i*i<=n; i+=2) {
if(n%i == 0) return 0;
}
return 1;
}
void primeNumbers(){
memset(&prime, 0, sizeof(prime));
int j;
int a = 0;
for(j = 2; j < 32650; j++){
if(isPrime(j)){
prime[a] = j;
a++;
}
}
}
int main(){
int x;
primeNumbers();
while(1){
scanf("%d",&x);
if(x == 0) break;
printf("%d\n",flavious(x)+1>;
}
return 0;
}
Input
0
Output