151 power crisis

>> বুধবার, ১৮ নভেম্বর, ২০০৯

During the power crisis in New Zealand this 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 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 tex2html_wrap_inline42 . The file will be terminated by a line consisting of 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
Description : presented by rizoan toufiq

ACM problem 151 & 440: (Solved by Josephus):Flavius Josephus was a famous historian of the first century. Legend has it that Josephus wouldn't have lived to become famous without his mathematical talents. During the Jewish-Roman war, he was among a band of 41 Jewish rebels trapped in cave by the Romans. Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. But Josephus, along with an unindicted co-conspirator, wanted none of this suicide nonsense; so he quickly calculated where he and his friend stand in the vicious circle.
Algorithm:
*       Given A Circular queue: 1,2,3,4,5,6,7,8,9,10,11,12,13,14
*      If(total_ele>1){
§  pop();
§  element--;
§  front moves;
o    }
*       i.e _,2,3,4,5,6,7,8,9,10,11,12,13,14
*      if difference =2 ,then next two element push into the back.
*       While(i!=diff) it pop()data from front and then push it back.ie, _,_,_,4,5,6,7,8,9,10,11,12,13,14,2,3. Now front is on 4 data and rear is on 3 data. Element decrease by 2(i.e 12). Now Follow above step until number element 1;
*      7,8,9,10,11,12,13,14,2,3,5,6 [4 die]
*      10,11,12,13,14,2,3,5,6,8,9 [7 die]
*      13,14,2,3,5,6,8,9,11,12 [10 die]
*       3,5,6,8,9,11,12,14,2 [13 die]
*      8,9,11,12,14,2,5,6 [3 die]
*      12,14,2,5,6,9,11 [8 die]
*      5,6,9,11,14,2 [12 die]
*      11,14,2,6,9 [5 die]
*      6,9,14,2 [11 die]
*      2,9,14 [6 die]
*      9,14 [2 die]
*      14 [9 die]

DOWNLOAD DOCUMENT FILE :
Download to click

একটি মন্তব্য পোস্ট করুন

  © Rizoan Toufiq , Copy Right @ 2009

Back to TOP