Coding 공부

a = """\    /\\
 )  ( ')
(  /  )
 \\(__)|
"""
print(a)

def check(num):
    visited_numbers = set()
    visited_numbers.add(num)
    if visited[num] == 1:
        return True
    elif visited[num] == 0:
        return False

    while num >= 0:
        temp = 0
        copy_num = num
        while copy_num>0:
            calc_num = copy_num%10
            next_num = copy_num//10
            temp = temp + calc_num**2
            copy_num = next_num
        num = temp
        if temp == 1:
            for vi_num in visited_numbers:
                visited[vi_num] = 1
            return True
        elif temp not in visited_numbers:
            visited_numbers.add(temp)
        else:
            for vi_num in visited_numbers:
                visited[vi_num] = 0
            return False
        


def find_prime_number(N):
    numbers = [True]*(N+1)
    numbers[0] = False
    numbers[1] = False
    prime_list = []
    for num in range(2,N+1):
        if numbers[num]:
            prime_list.append(num)
            for not_prime in range(num+num,N+1,num):
                numbers[not_prime] = False
    return prime_list




N = int(input())


prime_numbers = find_prime_number(N)

visited = [-1]*1000001
result = []

for num in prime_numbers:
    if check(num):
        result.append(num)
for row in result:
    print(row)

def find_arr(arr):
    global result
    for bit_mask in range(2**8):
        copy_arr = [row[:] for row in arr]
        change_bit = str(bin(bit_mask))[2:].count('1')
        if result < change_bit:
            continue
        for row in range(3):
            if bit_mask & (1<<row):
                for col in range(3):
                    copy_arr[row][col] = (copy_arr[row][col]+1)%2

        for col in range(3):
            if bit_mask & (1<<(col+3)):
                for row in range(3):
                    copy_arr[row][col] = (copy_arr[row][col]+1)%2


        if bit_mask & (1<<6):
            for row in range(3):
                copy_arr[row][row] = (copy_arr[row][row]+1)%2

        if bit_mask & (1<<7):
            for row in range(3):
                copy_arr[row][2-row] = (copy_arr[row][2-row]+1)%2

        sum_temp = sum(list(map(sum,copy_arr)))
        if sum_temp == 9 or sum_temp == 0:
            result = change_bit






T = int(input())



for tc in range(T):
    arr = []
    result = float('inf')
    for _ in range(3):
        s = list(input().split())
        for i in range(3):
            if s[i] == 'T':
                s[i] = 1
            else:
                s[i] = 0
        arr.append(s)
    
    cnt = 0

    find_arr(arr)
    print(-1 if result == float('inf') else result)

from collections import Counter

def move_robot(mad_ro,ro):
    new_robot = []

    for mad_x,mad_y in mad_ro:
        ro_distance = float('inf')
        ro_direction = -1
        for i in range(9):
            mad_nx = mad_x + dx[i]
            mad_ny = mad_y + dy[i]
            if 0<= mad_nx < R and 0<= mad_ny <C:
                distance = abs(mad_nx - ro[0]) + abs(mad_ny-ro[1])
                if ro_distance > distance:
                    ro_distance = distance
                    ro_direction = i

        new_x = mad_x + dx[ro_direction]
        new_y = mad_y + dy[ro_direction]
        new_robot.append((new_x,new_y))

    return new_robot
    
def bomb_robot(mad_ro):
    count_mad_ro = Counter(mad_ro)
    new_mad_ro = set()
    for key,value in count_mad_ro.items():
        if value == 1:
            new_mad_ro.add(key)
    return new_mad_ro




R,C = map(int,input().split())

arr = [list(input()) for _ in range(R)]

mad_robots = set()
robot = (0,0)
for i in range(R):
    for j in range(C):
        if arr[i][j] == 'R':
            mad_robots.add((i,j))
            arr[i][j] = '.'
        elif arr[i][j] == 'I':
            robot = (i,j)
            arr[i][j] = '.'

command = list(map(lambda x : x-1, map(int,list(input()))))
dx = [1,1,1,0,0,0,-1,-1,-1]
dy = [-1,0,1,-1,0,1,-1,0,1]
flag = False
answer = 0
for time in range(len(command)):
    x,y = robot
    nx = x + dx[command[time]]
    ny = y + dy[command[time]]
    if (nx,ny) in mad_robots:
        flag =  True
        answer = time + 1
        break
    robot = (nx,ny)
    mad_robots = move_robot(mad_robots,robot)

    if robot in mad_robots:
        flag = True
        answer = time + 1
        break
    mad_robots = bomb_robot(mad_robots)


if flag:
    print(f'kraj {answer}')
else:
    arr[robot[0]][robot[1]] = 'I'
    for mad in mad_robots:
        arr[mad[0]][mad[1]] = 'R'

    for row in arr:
        print(''.join(row))

N,M = map(int,input().split())
INF= float('inf')
dp = [INF]*(M+1)
apps_memory = list(map(int,input().split()))
apps_value = list(map(int,input().split()))
for i in range(N):
    memory,value = apps_memory[i],apps_value[i]
    for k in range(M,-1,-1):
        if k == 0:
            if memory >=M:
                memory = M
            dp[memory] = min(dp[memory],value)
        else:
            if dp[k]:
                num_memory = k + memory
                if num_memory >=M:
                    dp[M] = min(dp[M],dp[k]+value)
                else:
                    dp[num_memory] = min(dp[num_memory],dp[k]+value)
print(dp[M])

N,M = map(int,input().split())
INF= float('inf')

apps_memory = list(map(int,input().split()))
apps_value = list(map(int,input().split()))
total_sum = sum(apps_value)

dp = [0]*(total_sum+1)
result = INF
for i in range(N):
    for j in range(total_sum,apps_value[i]-1,-1):
        if j - apps_value[i] >=0:
            dp[j] = max(dp[j],dp[j-apps_value[i]]+apps_memory[i])
        if dp[j] >= M:
            result = min(j,result)

print(result)

import sys

input = sys.stdin.readline

D,N,M = map(int,input().split())

arr = [0]+[int(input()) for _ in range(N)]

arr.sort()
arr.append(D)
left = 0
right = D
ans = float('inf')
while left<=right:
    mid = (left+right)//2
    cnt = 0
    post_ind = 0
    for ind in range(1,N+2):
        if arr[ind] - arr[post_ind] <= mid:
            cnt += 1
        else:
            post_ind = ind
    
    if cnt > M:
        right = mid -1
    else:
        left = mid + 1

print(left)

import sys
input = sys.stdin.readline

D,N,M = map(int,input().split())


arr = [D] + [int(input()) for _ in range(N)]

arr.sort()
left = 0
right = D
ans = 0
while left<=right:
    mid = (left+right)//2
    past_island = 0
    cnt = 0
    for island in arr:
        if island - past_island >= mid:
            cnt += 1
            past_island = island
    
    if cnt >= N-M+1:
        ans = max(ans,mid)
        left = mid + 1
    else:
        right = mid -1

print(ans)

import sys

input = sys.stdin.readline

N = int(input())
A= []
B = []
C = []
D = []
for _ in range(N):
    a,b,c,d = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)
part_one = {}
for a in A:
    for b in B:
        if part_one.get(a+b):
            part_one[a+b] += 1
        else:
            part_one[a+b] = 1
answer = 0
for c in C:
    for d in D:
        temp_sum = -(c+d)
        if part_one.get(temp_sum):
            answer += part_one[temp_sum]



print(answer)

# skrud3021 님 코드 공부한거
N = int(input())

A,B,C,D = [],[],[],[]


for _ in range(N):
    a,b,c,d = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)


ab_sum = [i+j for i in A for j in B]
ab_sum.sort()
ab_sum.append(2<<29+1)
cd_sum = [i+j for i in C for j in D]
cd_sum.sort(reverse=True)
cd_sum.append(2<<29+1)
ab_ind = 0
cd_ind = 0
result = 0
while ab_ind <N**2 and cd_ind<N**2:
    sum_mid = ab_sum[ab_ind] + cd_sum[cd_ind]
    if sum_mid > 0:
        cd_ind += 1
    elif sum_mid < 0:
        ab_ind += 1
    else:
        ab_start_ind = ab_ind
        cd_start_ind = cd_ind
        ab_value = ab_sum[ab_ind]
        cd_value = cd_sum[cd_ind]
        while ab_value == ab_sum[ab_ind]:
            ab_ind += 1
        while cd_value == cd_sum[cd_ind]:
            cd_ind += 1
        
        result = result + (ab_ind-ab_start_ind)*(cd_ind-cd_start_ind)

print(result)

def founded(cnt):
    global result
    if cnt == 15:
        if sum(list(map(sum,win_draw_defeat))) == 0:
            result = 1
            return
    else:
        origin_number = origin_team[cnt]
        next_number = next_team[cnt]
        for idx in range(3):
            origin_team_score = idx
            next_team_score = 2-idx
            if win_draw_defeat[origin_number][origin_team_score] > 0 and win_draw_defeat[next_number][next_team_score]:
                win_draw_defeat[origin_number][origin_team_score] -= 1
                win_draw_defeat[next_number][next_team_score] -= 1
                founded(cnt+1)
                win_draw_defeat[origin_number][origin_team_score] += 1
                win_draw_defeat[next_number][next_team_score] += 1


from collections import deque
origin_team = [0,0,0,0,0,1,1,1,1,2,2,2,3,3,4]
next_team = [1,2,3,4,5,2,3,4,5,3,4,5,4,5,5]
answer = []
for _ in range(4):
    score = deque(map(int,input().split()))
    win_draw_defeat = []
    result = 0
    for _ in range(6):
        temp = []
        for _ in range(3):
            temp.append(score.popleft())
        win_draw_defeat.append(temp)
    founded(0)
    answer.append(result)
print(*answer)