카테고리

CamelACT (9)
UVa (3)
Basics (4)
Information (2)
Statistics Graph


관련 링크 : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=87


Input: standard input

Output: standard output

Time Limit: 3 second

Memory Limit: 32 MB

 

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 afterN, and ignoring regions already turned off. For example, if N = 17 andm = 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


 첫 블로그를 위한 게시물이다. 블로그에 포스트를 하기 위해 UVa 문제 도전!

하지만 너무 만만하게 봤던 탓일까 시간이 오래 걸렸다. 난이도는 50% 이상 풀 수 있는 최저 난이도, 하지만 정말 어렵게 풀었다. 총 네 시간 정도. 중간에 간식 먹고, 동영상 시청에 너무 집중이 안되었다. 이 모두 변명에 불과하지만...? 어쨌든 풀긴 풀었으니 간단한 문제 해석 고고~

 

Problem

 뉴질랜드에 여러 공장이 있는데 소비 전력을 줄이기 위해 공장의 전원을 내려야 한다. 단 공장의 전원을 내릴 순서는 규칙이 있다. N개의 입력으로 공장의 수가 정해지며 임의의 값 m으로 전원을 내릴 공장의 순서가 정해진다. 

 첫 번째 공장부터 N번째 공장까지 원형으로 배치되어 있다고 생각하자. 이때 N이 17, m이 5라고 한다면 첫 번째 공장의 전원을 내렸다고 했을 때 m개 건너 뛴 공장의 전원을 내린다. m이 5이므로 1번 공장의 전원을 우선 내리고 그 다음 6번 공장의 전원을 내린다. 6번 공장 이후에는 11번 공장... 이런 식으로 전원을 내리다가 17번 공장 이후에는 다시 1번 공장부터 이어오던 간격 수를 유지하며 전원을 내린다. 이런 식으로 하게 되면 1,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,7번의 순서로 불이 꺼지게 된다.

 위의 예제에서 7번 공장이 맨 마지막으로 꺼졌지만 13번 공장이 맨 마지막으로 꺼지도록 가장 작은 정수 m을 정하여 출력하면 된다. 단, 13 < N < 100이며 0을 입력 시 프로그램이 종료된다.


 처음에는 if문 안에 && 연산자를 통하여 조건을 주니 머리 속에서 자꾸 헷갈린다. && 다음의 조건을 무시하고 코드를 읽어 나갔다. 이러면 안되겠다 싶어서 무조건 if-if 구조로 가독성을 높였다. if-if 구조로 바꾸니 한결 코드 읽기가 수월해 졌다.

 그 다음으로 삽질이 너무 많았다. 예제 샘플의 17에 대한 결과 7은 진작에 잘 나왔지만 다른 입력 값의 결과가 엉망이었다. 간단한 bool 값의 착각으로 인해 출력 조건이 안 맞아서 결과값이 안 나왔다. 마지막 if(!turnedOff[13]){ 에서 if(i == 13)으로 유지한 체 1시간을 헤매니 너무 허탈하였다.

 bool 타입의 초기화 조건을 하는 방법을 잊지 말자.


#include <cmath>
#include <iostream>

using namespace std;

int main (void) {
	while(true){
START:
		int input;
		cin >> input;

if(input == 0) break; if(input < 13 || 100 <= input) break; for(int m = 1 ; m < 100 ; m ++){ // m = 7 bool turnedOff[100] = {0, }; int i = 1; // 지역 int mCount = 0; // 간격 카운트 int turnedOffCount = 0; // 꺼짐 카운트 while(true){ if(turnedOff[i] == false){ // m = 7 if(mCount % m == 0){ turnedOff[i] = true; turnedOffCount++; mCount = 1; } else mCount++; } i++; if(i > input){ for(int j = 1 ; j < input ; j++){ if(turnedOff[j] == false){ i = j; break; } } } if(turnedOffCount == input - 1){ if(!turnedOff[13]){ cout << m << endl; goto START; }else break; } if(turnedOff[13]) break; } } } return 0; }



신고
크리에이티브 커먼즈 라이선스
Creative Commons License

'UVa' 카테고리의 다른 글

[UVa]102 - Ecological Bin Packing  (1) 2012.12.05
[UVa]151 - Power Crisis  (0) 2012.12.04
[UVa]10310 - Dog and Gopher  (0) 2012.12.01
UVa l 2012.12.04 01:37
1 ··· 2 3 4 5 6 7 8 9 
get rsstistory! Tistory Tistory 가입하기!

티스토리 툴바