카테고리: boj

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 ‘커서’라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

nums = {1 : [1],
        2 : [2, 4, 8, 6],
        3 : [3, 9, 7, 1],
        4 : [4, 6],
        5 : [5],
        6 : [6],
        7 : [7, 9, 3, 1],
        8 : [8, 4, 2, 6],
        9 : [9, 1]}

for _ in range(n):
    a, b = map(int, input().split())
    # a의 1의 자리수를 구한다 -> 4
		one = a % 10

		# 1의 자리에 나올 수 있는 값들을 가져온다 -> nums[4] -> [4, 6]
		# 이 중에서 b번째 값을 취한다. 4, 6, 4, 6, 4, 6 -> 6
    print(nums[one][(b - 1) % len(nums[one])])

단 a의 1의 자리가 0일 경우 무조건 제곱한 수의 1의 자리도 0이므로 10번 컴퓨터가 처리하게 된다.

import sys, math

i = int(sys.stdin.readline())
for _ in range(i):
    n, m = map(int, sys.stdin.readline().split())
    N = m - n
    r_N = math.sqrt(N)
    N_int = math.trunc(r_N)
    if r_N == N_int: print(N_int * 2 - 1)
    else:
        if N > N_int * (N_int + 1):
            print(N_int * 2 + 1)
        else:
            print(N_int * 2)

...
		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는 커질수록 아래로 진행한다고 생각해야 한다.

nums = str(sys.stdin.readline().strip())
if '0' not in nums:
    print(-1)
else:
    l = [0] * (int(max(nums)) + 1)
    s = ''
    sum = 0
    for i in nums:
        l[int(i)] += 1
    for i in range(len(l)-1, 0, -1):
        s += str(i) * l[i]
        sum += i * l[i]
    if sum % 3 == 0: print(int(s) * (10 ** l[0]))
    else: print(-1)