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
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#include<stdio.h>
#include<conio.h>
int main()
{
int N,off[100],i,last,count=0,m,inc=0,a,num=0,ans[100];
clrscr();
while(scanf("%d",&N))//Taking the number of regions into N.
{
if(N!=0)
{
m=1;last=0;
while(last!=13)
{
//Initilaizing the off[] array.
for(i=0;i<N;i++)
{
off[i]=0;
}
count=0;//Counts the number of regions in which electricity has been switched off.
i=0;
while(count<N)
{
if(off[i]==0)
//1 denotes off and 0 denotes not off.
{off[i]=1;count++;}//Swithing off if not already off.
last=i+1;//Keeps the last region in which electricity has been switched off.
inc=0;//Counts the number of times i has been incremented by 1.
while(inc<m && count<N)
{
if(i>=N-1)
{
i=0;
if(off[i]!=1)
{inc++;}
}
/*inc is incremented only while passing through a region with 0 state.*/
if(off[i+1]==0)
{
i++;
inc++;
}
else
{
i++;
}
}
}
m++;
}
ans[num]=m-1;//Storing the values of m in the ans[] array.
num++;
}
else
{
for(i=0;i<num;i++)
{printf("%d\n",ans[i]);}
scanf("%d",&m);
return 0;
}
}
}
17
13
0
7
1
