POCRI - Power Crisis

no tags 

 

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.

 

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

Input will consist of a series of lines, each line containing the number of regions (N) with 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.

 

Example

Input:
17
0

Output:
7

hide comments
kshubham02: 2019-04-18 19:58:12

A rather bland question. Don't think too much, m has a not-so-large upper bound. Go brute-force.
(Proving that m has a not-so-large upper bound is what's interesting).

Piyush Kumar: 2016-06-29 18:21:59

I feel there should be some constraint on the source code limit of such questions !

Last edit: 2016-06-29 19:02:32
fibonacciprw: 2015-12-11 06:15:01

@Miguel Angel Diaz, and everyone else who got it accepted on UVa: the test cases on UVa are terribly weak and miss all the interesting ones. For example, the answer for N=84 should be the highest in the specified range - check whether that is the case with your program.

RIVU DAS: 2014-05-12 17:56:17

Nice implementation of Josephus problem!!

Victim: 2014-02-11 23:31:02

very nice question....
Joshephus problem :)

Vipul Pandey: 2013-06-25 20:14:07

a very nice problem.

Ouditchya Sinha: 2013-06-23 18:50:00

@Neo : Nice Catch( m can be > N )! AC!! Nice Problem. :)

Miguel Angel Diaz: 2013-01-07 22:44:47

Hmm. I precomputed values from 13-100 and put them in an array; yet, I am getting WA. Why?

Aradhya: 2012-03-28 11:30:39

awe$0me question!!


Added by:Andres Tellez
Date:2011-05-17
Time limit:3.381s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64