[swea] 7584번: 자가 복제 문자열 - 파이썬(python)

입력범위가 K(1 ≤ K ≤ 1018) 이므로 모든 P값을 찾으려고 하면 낭패이다.

따라서 규칙을 찾아야 한다.

p=“001001100011011...” 으로 진행되는데0인 숫자의 인덱스는 0,1,4,5,7,8,9,12,15,16,17,19,20,24,25,28...1인 숫자의 인덱스는 2,5,6,10,11,13,14,18,21,22,23,26,28,29... 와 같다.따라서 4의 배수면 0의 값이고,4의 배수가 아닌 2의 배수면 1임을 알 수 있다.홀수인덱스의 경우 (i-1)/2 의 값에 따라 결정된다.

 

 

나의 풀이

T = int(input())
answer = []
for t in range(1, T+1):
    k = int(input()) - 1
    while k >= 0:
        if k % 2 == 1:
            k = (k-1)//2
        elif k % 4 == 0:
            k = 0
            break
        elif k % 2 == 0:
            k = 1
            break
    answer.append(f'#{t} {k}')

print(*answer, sep='\n')