DS5 approach?

general
,
1

Hello everyone
I was trying out this problem.

I did not understand the approach I need to follow to solve this. Could any one provide some kind of hint or some algorithm whose variant I may use here. Also the solutions are not made public otherwise I could have learnt on my own.

Thanks

2

Check out this link. The problem you mentioned has the same underlying solution.

1 Like
3

Its josephus problem with a small change… :)… you should read the wiki article mentioned by @jeeves also for detailed description about josephus problem you should read first chapter of CONCRETE MATHEMATICS by Graham,Knuth and Patashnik… hope that helps enjoy…

1 Like
4

Assuming that you have already at least read the Josephus problem,

int josephus(int n, int k) {
   if (n == 1)
       return 1;
   else
       return (josephus(n - 1, k) + k-1) % n + 1;
}

this problem is a slight tweak of that. What? In Josephus problem, a circle of N objects is given and a number k is given: we pick any object and start the numbering 1, 2, … N and we shoot the kth object starting from 1 first, then the kth from the next and so on…
Here, first we cut-off the electricity in the 1st city, then the kth next, and so on… k has to be such that 13th city always stays lit up till the end (every other city is having power failure while NY:13 is still alive)

You can throw this modified problem back to Josephus problem, how?
For example, take the first sample example, here N = 17
Now, you have to find k such that city 13 is the last to have the electricity cut off.
Draw a circle, put 17 objects on the circumference, number them 1, 2, …, 17
Now we first cut off power from city #1 and then for the kth city, so in the original Josephus problem N has become N-1 and the relative positioning of each city Ci is now Ci-1.
So, for each given N you have to find a k such that josephus(n-1, k) == 12
As the constraints for N were 13<=N<=100, you can easily call the josephus function for each i starting from 1.

Here is my full solution to the problem, copied from the contest only (removing the comments):

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
using namespace std;

int josephus(int n, int k) {
    if (n == 1)
        return 1;
    else
        return (josephus(n - 1, k) + k-1) % n + 1; 
}

int main() {
    int n;
    scanf("%d", &n);
    while(n!=0) {
	for(int i=1; i<=200; i++) {
		if(josephus(n-1, i) == 12) {
			printf("%d\n", i);
			break;
		} 
	} 		
	scanf("%d", &n);
    }
return 0;
}