ACM 2009. 6. 2. 20:25
반응형

100 - The 3n + 1 problem

Time limit: 3.000 seconds
 
 The 3n + 1 problem 

Background

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

The Problem

Consider the following algorithm:

 		1. 		 input n

2. print n

3. if n = 1 then STOP

4. if n is odd then n = 3n+1

5. else n = n/2

6. GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers nsuch that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

The Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

You can assume that no operation overflows a 32-bit integer.

The Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

1 10100 200201 210900 1000

Sample Output

1 10 20100 200 125201 210 89900 1000 174

반응형

'ACM' 카테고리의 다른 글

10039 - Railroads  (0) 2009.06.02
10110 - Light, more light  (0) 2009.06.02
10132 - File Fragmentation  (0) 2009.06.02
10099 - The Tourist Guide  (0) 2009.06.02
10004 - Bicoloring  (0) 2009.06.02
posted by ssuk1010
:
Unix/Linux 2009. 6. 2. 20:17
반응형


 ------------------ 실행 방법 ------------------

 gdb 프로그램명 ex) gdb bugprg
 gdb 프로그래명 코어파일명 ex) gdb bugprg core.14998
 gdb 프로그램명 실행중인 프로세스 PID ex) gdb bugprg 14998

 
 ------------------- 종료 방법 -----------------

 q or Cntr+d

 
 -------------------- 보기 ---------------------

 set listsize 20 -> 한번에 출력되는 행 수 조절
 l(list) -> 소스 내용 출력
 l 10 -> 10행을 기준으로 출력
 l func이름 -> func을 기준으로 출력
 l main -> main함수 기준으로 출력
 l file.c:func -> file.c의 func을 기준으로 출력

 -------------------- 브레이크 포인트 -------------

 r -> 어떤 파일의 어떤 함수 부분에서 어떠한 문제가 발생했다는 것을 표시
 bt -> 스택을 백트레이스 하면서 어떤 함수를 호출하다가 문제가 발생했는지 표시
 
 b func -> funt시작에 브레이크 포인트 설정
 b 10 -> 10행에 브레이크 포인트 설정
 b file.c:func -> file.c의 func에 브레이크 포인트 설정
 b +2 -> 현재 행에서 2개 행 이후에 브레이크 포인트 설정
 b 10 if var =0 -> 10행에서 설정하는데 변수값이 0일때 동작
 condition [N(브레이크번호)] var ==0 ->이미 그 행에 브레이크 포인트가 걸려있을때 condition으로
   조건을 걸어서 설정할 수 있다.

 tb -> b는 gdb내내 브레이크가 존재하고 tb는 한번만 실행한다.
 cl(clear)  func -> 브레이크 포인트 지움
 cl 10 -> 10행에 브레이크 포인트 지움
 cl file.c:10  -> 브레이크 포인트 지움
 cl -> 모든 브레이크 포인트 지움

 info b(info breakpoints -> 모든 브레이크 정보 보기


 -------------------- 프로그램 수행 -------------------

 r : 프로그램 수행
 r arg1  arg2 -> arg1과 arg2를 인자로 프로그램 수행
 k -> 프로그램 수행 종료

 s(step) -> 현재 행 수행하고 멈춘다. 현재행이 함수를 호출하는 부분이라면 함수의 내부로 들어가서 수행
 n(next) -> 현재 행 수행하고 멈춘다. 현재행이 함수를 호출하는 부분이라면 함수의 내부로 들어가지 않음
 c(connection) -> 다음 브레이크 포인트를 만날때까지 수행
 
 u -> for문을 빠져나옴
 finish -> 함수가 끝난 시점으로 간다
 return (리턴값) -> 함수의 나머지 부분을 수행하지 않고 빠져나옴
 si -> 현재 인스트럭션을 수행. 함수 호출시 내부로 들어감
 ni -> 현재 인스트럭션을 수행. 함수 호출시 내부로 들어가지 않음


 ---------------------- 값 확인 -------------------------

 watch 변수명 -> 변수값이 어떻게 변하는지 확인할 수 있음
 info locatls -> for문 위치에서 어떤 지역변수들이 있으며 각각 값은 무엇인지 볼 수 있음
 info variables -> 어떤 전역변수들이 있으며 각각 값은 무엇인지 볼 수 있음
 p 변수 -> 해당 변수 값이 보임
 p 함수 -> 함수의 주소 값이 보임
 p 포인터 변수 -> 포인터 변수가 가리키는 주소
 p *포인터 변수 -> 포인터 변수가 가리치는 주소에 있는 값
 display 변수 -> 변수값을 매번 화면에 디스플레이 한다.
 undisplay 디스플레이 번호 -> 디스플레이 설정을 없앤다.
 diable display 디스플레이 번호 -> 디스플레이를 일시 중단한다.
 enable display 디스플레이 번호 -> 디스플레이를 다시 활성화한다.
 
------------------------ 출력 형식의 지정 ----------------

 t -> 2진수
 o -> 8진수
 d -> 부호있는 10진수
 u -> 부호없는 10진수
 x -> 16진수
 c -> 최초 1바이트 값을 문자형으로 출력
 f -> 소수점을 출력
 a -> 심볼을 오프셋을 출력

반응형

'Unix/Linux' 카테고리의 다른 글

[스크랩] 리눅스 시그널 정리  (0) 2009.09.14
vi 필수 명령어  (0) 2009.06.02
posted by ssuk1010
:
Unix/Linux 2009. 6. 2. 20:13
반응형


ESC + :e filename -> 현재파일을 저장하지 않고 다른 파일을 불러온다.

(입력모드) s -> 현재 커서의 글자 지우고 입력

------------- 이동하기 -----------------------

 w -> 다음 단어의 첫 글자로 이동
 b -> 이전 단어의 첫 글자로 이동

 gg -> 문서의 맨 첫 행으로 이동
 G -> 문서의 맨 끝으로 이동

 ^ -> 행의 시작으로 이동
 $ -> 행의 끝으로 이동

 

-------------- 삭제하기 --------------------

 x -> 한 글자 삭제
 dw -> 한 단어 삭제
 dd -> 한 행 삭제


-------------- 복사하기 ---------------------

 yw -> 현재 위치의 한 단어 복사
 yy -> 현재 위치의 한 행 복사

 p -> 복사한 것 붙여넣기


-------------- 블로지정 동작 -----------------

 v & 이동커서 -> 블록지정
     d : 잘라내기 및 삭제
     y : 복사
     < : 행 앞에 탭 삭제
     > : 행 앞에 탭 삽입


-------------- 되돌리기 -----------------------

 u -> 되돌리기
 Ctrl + r -> 되살리기


 ------------- 검색하기 ------------------------

 / or ? + 문자 -> 검색하기
    n : 다음 단어로 이동
    N : 이전 단어로 이동
 * -> 단어 위에서 *를 입력하면 아래로 검색
 # -> 단어 위에서 #을 입력하면 위로 검색


 ------------- 단어 바꾸기(치환) ----------------

 %s/바뀌기 전 단어/바꾼 후 단어/g -> 단어 치환(문서전체)
 s/바뀌기 전 단어/바꾼 후 단어/g -> 단어 치환(매칭되는 가장 처음 문장)
    gc(단어마다 모두 치환할 것인지 물어본다)


 ------------ 여러파일 동시에 열기 --------------

 vi file1 file2 .... -> 여러 파일을 동시에 연다.
   b1 : 첫 번째 파일 버퍼
   b2 : 두 번째 파일 버퍼
    .....

 map ,1 :b!1<CR> -> , 를 누르고 뗀 다음 숫자 1을 누르면 첫 번째 파일 버퍼로 간다.


 ------------ 다중 창 사용하기 -------------------

 Ctrl + w 을 동시에 누른 다음 n -> 창으로 반으로 나뉘면서 위에 빈 공간이 생긴다.
 e filename -> 위의 빈 공간에 새로운 파일을 연다.
 Ctrl ww -> 두 파일이 번갈아 가면서 커서가 이동한다.
 Ctrl + w q or :q! -> 열린 파일 닫기

 Ctrl + w s -> 현재 파일을 수평으로 분할
 Ctrl + w v -> 현재 파일을 수직으로 분할
 Ctrl ww -> 두 파일이 번갈아 가면서 커서가 이동한다.
 Ctrl + w q or :q! -> 열린 파일 닫기


 ------------ 마킹해서 이동하기 --------------------

 ma -> 현재 위치를 a로 마킹하기
 `a -> a로 마킹된 위치로 가기


 ------------ 쉘 명령어 사용하기 ------------------

 :!쉘 명령어(예 : ls) -> 현재 파일을 닫지 않고 쉘 명령어를 실행하고 파일로 돌아갈 수 있음


 ------------- 파일 탐색 기능 ---------------------

 :20vs ./ -> 현재 폴더에 있는 파일들의 리스트를 볼수 있다.

 
 -------------- 괄호 이동 및 탐색 -------------------

 {  } -> 블럭의 처음과 끝으로 이동한다.
 [[ -> 현재 함수의 맨 처음으로 이동
 ]] -> 다음 함수의 맨 처음으로 이동
 % -> { or } 에서 누르면 쌍을 이루는 괄호로 이동한다.


 -------------- 폴딩 --------------------------------

 v ]}zf : 함수를 접어서 블록으로 형성한다. (어려우니 map으로 지정해놓자)
 v zo : 접은 함수로 가서 누르면 접었던 함수가 펴진다.


 ------------- 탭 사이즈 조정 ----------------------

 :set ts = 8 -> 문서 전체의 탭 사이즈를 8로 조정한다.
 :set tabstop=4

 :set ai -> 자동 들여쓰기
 :set autoindent  -> 자동 들여쓰기

 
 ------------- 흐트러진 소스 정렬 ------------------

 v = -> v로 선택하여 블록을 지정한 다음 =를 누르면 소스가 정리된다.

 

 -------------- 달라진 소스 확인 -------------------
 
vimdiff 첫번째 파일 두번째 파일
do = 오른쪽 파일에서 다른 점을 왼쪽으로 옮겨오기
dp = 왼쪽 파일에서 다른 점을 오른쪽으로 옮겨오기

체크인 버전에 따라 비교하기
vd PvbGetAttGroup.c
PvbGetAttGroup.c@@/main/1


Ctrl + w + w -> 분할된 화면 이동

Ctrl + w + = -> 분할된 화면의 크기가 동일하도록 조정

] + c -> 차이점이 있는 부분으로 이동 (Down)

[ + c -> 차이점이 있는 부분으로 이동 (Up)

d + o -> 현재 커서가 위치한 창 쪽으로 반대 창 쪽의 내용을 적용 시키기

d + p -> 현재 커서가 위치한 창 쪽의 내용을 반대 창 쪽으로 적용 시키기

z + o (or space) -> 접혀 있는 부분 열기

z + c -> 차이점 없는 부분 접기

:diffupdate -> 문서 간의 차이점을 다시 비교하도록 하는 명령 (한 쪽 창의 내용을 edit하다 보면 문서 간의 차이점을 나타내는 색깔이 없어지기도 함)


3. diff된 단락으로 점프

[c            % 변화가 있는 이전 단락의 처음으로 점프
]c            % 변화가 있는 다음 단락의 처음으로 점프

4. diff시 접힌 단락 펼치기

diff를 이용하면서 비교할 필요가 없는 단락들은 자동으로 접어두게 됩니다. 접혀진 내용을 보거나 다시 접을 때 사용하는 명령어 들입니다.

za            % 커서위의 folded paragraph를 토글합니다.
zR            % 모든 접힌 단락을 펼칩니다.
zM           % 모든 열린 단락을 접습니다.

 

창넘나들기(Window)
diff를 사용하면 창이 분할이 됩니다. 이때 창을 넘나들며 편집을 해야하는데 이 때 사용할 수 있는 명령어들을 함께 소개합니다. 물론, diff 이외에도 모든 창분할시 사용되는 명령입니다.

1. 창 나누기

CTRL-W s         % 가로 창 나누기
CTRL-W v         % 세로 창 나누기


2. 창 닫기

CTRL-W q


3. 창 이동하기

CTRL-W w                 % 열린 창들을 순서대로 편집창 이동
CTRL-W [h/j/k/l]       % 커서방향에 따라 편집창 이동

4. 창 크기 조절하기

CTRL_W =            % 모든 창들의 너비와 높이를 동일하게 조절한다.
CTRL_W +            % 현재 편집 창의 크기를 늘린다.
CTRL_W -            % 현재 편집 창의 크기를 줄인다.
CTRL_W CTRL_-   % 현재 편집 창을 최대로 늘린다.


 -------------- buffer에 저장 -------------------------
 
 1) v로 블록지정
 2) :w! /tmp/11
 3) 복사할 위치에 :r /tmp/11

 -> 11이라는 버퍼에 저장되고 붙여넣기가 된다.
 

반응형

'Unix/Linux' 카테고리의 다른 글

[스크랩] 리눅스 시그널 정리  (0) 2009.09.14
Debug  (0) 2009.06.02
posted by ssuk1010
: