- Forum
- General C++ Programming
- Queues
Queues
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. Hint: Use Queues.
Input and Output
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 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
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. Hint: Use Queues.
Input and Output
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 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
don't worry, it's just I do a lot of Informatics (basically finding the most efficient way to do something) and that is exactly how they set out Informatics questions.
It's not really important
It's not really important
the most obvious way is to do a loop that tries m=2,m=3,m=4 and so on until it finds one that works.
However, this is very inefficient.
Note that m and N must be relatively prime (ie they do not have any common factors)
However, this is very inefficient.
Note that m and N must be relatively prime (ie they do not have any common factors)
ya i understood, may i have the code of that program now coz m going to uni now and i have to take it with me?
closed account (D80DSL3A)
| theranga wrote: |
|---|
| the most obvious way is to do a loop that tries m=2,m=3,m=4 and so on until it finds one that works. |
You have been offered this advice and ignored it.
Doing that discourages others from offering to help.
Try to implement what theranga suggested in a program.
If you get stuck, post back here WITH CODE.
Topic archived. No new replies allowed.