BAEKJOON : 1212, 2089, 17103

No. 1212

1. Problem

2. My Solution

第1の方法(直接実施)

import sys

def oct_to_bin(oct_num):

    result = ''

    for i in oct_num:

        temp = ''

        while True:
            a,b = divmod(i,2)
            if a == 0:
                temp += str(b)
                temp += str(a)
                break
            else:
                temp += str(b)
                i = a

        if len(temp) == 2:
            temp += '0'
        elif len(temp) == 4:
            temp = temp.rstrip('0')

        result += temp[::-1]
   
    while result[0]=='0':
        result = result.lstrip('0')

    return result

oct_num = list(map(int,list(str(sys.stdin.readline().rstrip()))))

if oct_num[0] == 0:
    print(0)
else:
    print(oct_to_bin(oct_num))

bin()関数

を使用

oct_num = int(sys.stdin.readline().rstrip(), 8)
print(bin(oct_num)[2:])

No. 2089

1. Problem

2. Others' Solutions

バイナリ変換原理により

を実現する.

2、-2

で割る

import sys

n = int(sys.stdin.readline().rstrip())

if n == 0:
    print(0)
    exit()

result =''

while(True):
    a,b = divmod(n,-2)
    
    if n == 0:
        break
    elif n % -2:
        result += '1'
        n = n//-2 +1
    else:
        result += '0'
        n //= -2

print(result[::-1])

3. Learned

十進法をバイナリに変換する原理を利用して、

-13 = -2*(7) + 1
 7  = -2*(-3) + 1
-3  = -2*(2) + 1
 2  = -2*(-1) + 0
-1  = -2*(1) + 1
 1  = -2*(0) + 1

しかしPythonで負数を用いる残りの演算を実行すると、残りの無条件は正数(C言語は正数)

となる.

No. 17103

1. Problem

2. My Solution

テストステロン受容体

を利用

は、n/2のみを判断する、同じペア

を除去する.

import sys
import math

test_n = int(sys.stdin.readline().rstrip())

prime = [False,False] + [True] * 999999

for i in range(2,int(math.sqrt(1000000))+2,1):
    if prime[i] == False:
        continue
    else:
        for j in range(i+i, 1000001, i):
            prime[j] = False

for _ in range(test_n):

    n = int(sys.stdin.readline().rstrip())

    gold_num = []

    for i in range(2, (n//2)+1, 1):
        if prime[i] == True and prime[n-i] == True:
            gold_num.append([i,n-i])
    
    print(len(gold_num))

3. Others' Solutions

素数リストに少数しか追加しない->時間短縮3420 ms->1264 ms

import sys
input = sys.stdin.readline

nums = [1] * 1000001
prime = []
for i in range(2, 1000001):
    if nums[i] == 0:
        continue
    prime.append(i)
    for j in range(2*i, 1000001, i):
        nums[j] = 0

for _ in range(int(input())):
    n = int(input())
    count = 0
    for i in prime:
        if i > n//2:
            break
        if nums[i] and nums[n-i]:
            count += 1
    print(count)

4. Learned

と

を比較して、同じ要素対を除去する

時間を最小限に抑える方法を考えてみましょう.

n = 10 일 때
1 2 3 4 5 6 7 8 9 10  5를 기준으로 양쪽의 조합이 같음