Tag: recursion

sys.setrecursionlimit(10**6)

string = sys.stdin.readline().strip()
length = len(string)

visited = [False] * length

def select_char(start, end):
    if start > end:
        return

    min_char = 'Z' + '1' 
    min_idx = -1
    for i in range(start, end + 1):
        if string[i] < min_char:
            min_char = string[i]
            min_idx = i

    visited[min_idx] = True

    current_result = ""
    for i in range(length):
        if visited[i]:
            current_result += string[i]
    print(current_result)
    select_char(min_idx + 1, end)
    select_char(start, min_idx - 1)

select_char(0, length - 1)

merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- ⌊(p + r) / 2⌋;       # q는 p, r의 중간 지점
        merge_sort(A, p, q);      # 전반부 정렬
        merge_sort(A, q + 1, r);  # 후반부 정렬
        merge(A, p, q, r);        # 병합
    }
}

# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
    i <- p; j <- q + 1; t <- 1;
    while (i ≤ q and j ≤ r) {
        if (A[i] ≤ A[j])
        then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
        else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
    }
    while (i ≤ q)  # 왼쪽 배열 부분이 남은 경우
        tmp[t++] <- A[i++];
    while (j ≤ r)  # 오른쪽 배열 부분이 남은 경우
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while (i ≤ r)  # 결과를 A[p..r]에 저장
        A[i++] <- tmp[t++];
}

...
		num = 2 ** (N - 1)
		# 좌상단
    if x <= num and y <= num:
        position(N-1, x, y, base)
        
		# 우상단
    elif x > num and y <= num:
        position(N-1, x - num, y, 4 ** (N - 1) + base)
    
		# 좌하단
    elif x <= num and y > num:
        position(N-1, x, y - num, 2 * 4 ** (N - 1) + base)
        
		# 우하단
    elif x > num and y > num:
        position(N-1, x - num, y - num, 3 * 4 ** (N - 1) + base)

위와 같이 한 변이 $2^n$인 영역이 주어졌을 때 각 변을 직각 이등분 하는 선은 가장 좌상단의 꼭짓점에서 $2^n/2(=2^{n-1})$ 만큼 떨어져 있는 것을 확인할 수 있다. 그러므로 x, y가 $2^{n-1}$보다 큰지 작은지 확인하면 네 개의 영역 중 어디에 속해있는지 알 수 있다. 단 여기서 x는 커질수록 오른쪽, y는 커질수록 아래로 진행한다고 생각해야 한다.