[zerojudge] f164: 萬球同心移位之章

'''
這一題我的解法 1  :  NA (score:91%)
因為測資 #11 的 n 值比較大，第一個寫法
使用了比較大的記憶體，解法 2 才 AC
請看說明。
'''

# 解法 1

from sys import *

n, m, q = map(int, stdin.readline().split())
N = {k: [k-1, k+1] for k in range(n)} 
# 建立一個 dict ，且預設每個 key 的逆鄰及順鄰。
# n 值太大時，記憶體會不夠用，題目只有開 64MB

N[0][0] = n-1  # 頭尾手牽手
N[n-1][1] = 0

for _ in range(m):
    d, a, b = stdin.readline().split()
    a, b = int(a), int(b)
    if(a == b): continue # a, b 相等時，不處理。
    afk = N[a][1]        # 因為 a 要抽走，先找出 a 的順鄰 afk 及逆鄰 ark
    ark = N[a][0]
    N[afk][0] = ark      # 讓 afk 和 ark 手牽手，修補這個缺口。
    N[ark][1] = afk
    if(d == 'F'):        # 如果指令是 F  a 要放在 b 的順鄰。
        bfk = N[b][1]    # 先找出 b 原本的順鄰 bfk
        N[bfk][0] = a    # 設定 bfk 的逆鄰為 a
        N[a][1] = bfk    # 設定 a 的順鄰為 bfk
        N[a][0] = b      # 設定 a 的逆鄰為 b
        N[b][1] = a      # 設定 b 的順鄰為 a

    else:                # 如果指令是 R  a 要放在 b 的逆鄰。
        brk = N[b][0]    # 先找出 b 原本的逆鄰 brk
        N[brk][1] = a    # 設定 bfk 的順鄰為 a
        N[a][0] = brk    # 設定 a 的逆鄰為 brk
        N[a][1] = b      # 設定 a 的順鄰為 b
        N[b][0] = a      # 設定 b 的逆鄰為 a

Q = [N[int(x)] for x in stdin.readline().split()]
r = ' '.join(['{} {}'.format(a, b) for a, b in Q])
print(r)

# 解法 2

from sys import *

n, m, q = map(int, stdin.readline().split())
N = {}
# 建立一個空的 dict ，不給初值，有用到的 key 才給值。
# 因為 m < 10^3 ，須建立的 key 不多，相信不會爆。

N[0] = [n-1,1]    # 先建立頭尾的 key，一樣是頭尾手牽手
N[n-1] = [n-2, 0]

def initX(x): # 如果這個 key 值沒有出現過，它的 value 肯定是 [[x-1, x+1]]
    global N
    if(not N.__contains__(x)):
        N[x] = [x-1, x+1]
    return

def gp(x):    # 這是要輸出的 string ，原理同 initX
    global N
    if(not N.__contains__(x)):
        return '{} {}'.format(x-1, x+1)
    else:
        return '{} {}'.format(*N[x])
        
for _ in range(m):
    d, a, b = stdin.readline().split()
    a, b = int(a), int(b)
    if(a == b): continue # a, b 相等時，不處理。
    initX(a) # 對沒出現過的 key 給初值，底下同。
    initX(b) #
    afk = N[a][1]
    ark = N[a][0]
    initX(afk) #
    initX(ark) #
    N[afk][0] = ark
    N[ark][1] = afk
    if(d == 'F'):
        bfk = N[b][1]
        initX(bfk) #
        N[bfk][0] = a
        N[a][1] = bfk
        N[a][0] = b
        N[b][1] = a
    else:
        brk = N[b][0]
        initX(brk) #
        N[brk][1] = a
        N[a][0] = brk
        N[a][1] = b
        N[b][0] = a
Q = [gp(int(x)) for x in stdin.readline().split()]
r = ' '.join(Q)
print(r)

[zerojudge] e287: 機器人的路徑

import sys

n, m = [int(x) for x in sys.stdin.readline().split()]
f = []
for _ in range(n): f += [int(x) for x in sys.stdin.readline().split()]
v = f.index(min(f))
y, x, r = v // m, v % m, 0
while(1):
    ind = y * m + x
    r += f[ind]
    f[ind] = -1
    c = [[y, x+1], [y+1, x], [y, x-1], [y-1, x]]
    c = [z for z in c if z[0] >= 0 and z[0] < n and z[1] >= 0 and z[1] < m]
    if(not c): break
    c = [(z[0], z[1], f[z[0] * m + z[1]]) for z in c]
    c = [z for z in c if z[2] >= 0]
    if(not c): break
    c.sort(key = lambda z: z[2])
    y, x, _ = c[0]
        
print(r)

[zerojudge] e990: 奇怪的隕石

from sys import *
from math import log
for s in stdin:
    t, n = map(float, s.split())
    r = (log(n)/log(0.5))*t
    print('%.3f' % r)

[zerojudge] a225 明明愛排列

import sys

for s in sys.stdin: print(' '.join(sorted(sys.stdin.readline().strip().split(), key = lambda x: (int(x)%10, -int(x)))))

[zerojudge] f012: 奶油機器人

# 蘭頓螞蟻  Langton's ant python asnewchien@gmail.com

from sys import *
dot = {(0,0): 0} # 某點的顏色  0:white, 1:black
x, y = 0, 0      # position
direction = 0    # 方向  0:up, 1:right, 2:down, 3:left
r = [(0,0)]      # 某一步的座標

rule = ({(0,0):(1,0,1,1), (0,1):(0,-1,2,1),(0,2):(-1,0,3,1),(0,3):(0,1,0,1),
         (1,0):(-1,0,3,0),(1,1):(0,1,0,0), (1,2):(1,0,1,0), (1,3):(0,-1,2,0)})
# key of rule   : (color, direction)
# value of rule : (deltaX, deltaY, newDirection, newColor)

for i in range(1, 10104):
    op = (x, y)       # 原來的點座標
    oc = dot[op]      # 原來的點顏色
    dx, dy, direction, nc = rule[(oc,direction)]
    dot[(x,y)] = nc   # 給原來的點一個新顏色
    x += dx
    y += dy
    if(not dot.__contains__((x,y))): dot[(x,y)] = 0
    # 下一個點如果沒有拜訪過，設定為白色
    r.append((x,y))

'''
我們現在要以 r[10000] 為基準點, 循環節為 104
我先做了一個測試，
發現 r[10000]=(-16, 10), r[10104]=(-18, 8), r[10208]=(-20, 6)
每個循環的起點對應上一個起點的  deltaX = -2, deltaY = -2
以下我要對 r[10000] ~ r[10103] 建立對 r[10000] 的相對位置
'''
# md = [(0, 0), (-1, 0), (-1, -1), (-2, -1), (-2, -2), (-3, -2), (-3, -1), (-2, -1), (-2, -2), (-1, -2), (-1, -3), (0, -3), (0, -2), (-1, -2), (-1, -3), (-2, -3), (-2, -2), (-1, -2), (-1, -3), (0, -3), (0, -4), (-1, -4), (-1, -5), (-2, -5), (-2, -4), (-1, -4), (-1, -5), (0, -5), (0, -4), (-1, -4), (-1, -5), (-2, -5), (-2, -6), (-3, -6), (-3, -5), (-2, -5), (-2, -6), (-1, -6), (-1, -7), (-2, -7), (-2, -6), (-1, -6), (-1, -5), (-2, -5), (-2, -6), (-1, -6), (-1, -7), (0, -7), (0, -8), (-1, -8), (-1, -7), (0, -7), (0, -6), (1, -6), (1, -5), (0, -5), (0, -4), (1, -4), (1, -3), (0, -3), (0, -4), (1, -4), (1, -5), (0, -5), (0, -6), (1, -6), (1, -7), (0, -7), (0, -6), (1, -6), (1, -5), (0, -5), (0, -4), (1, -4), (1, -3), (2, -3), (2, -2), (1, -2), (1, -1), (0, -1), (0, -2), (-1, -2), (-1, -3), (-2, -3), (-2, -4), (-1, -4), (-1, -5), (-2, -5), (-2, -4), (-1, -4), (-1, -3), (-2, -3), (-2, -2), (-3, -2), (-3, -3), (-4, -3), (-4, -2), (-3, -2), (-3, -3), (-2, -3), (-2, -2), (-1, -2), (-1, -3), (-2, -3), (-2, -2)]

md = []
baseX, baseY = r[10000]
for i in range(104):
    x, y = r[10000+i]
    md.append((x-baseX, y-baseY))

for s in stdin:
    n = int(s)
    try: 
        # n <= 10000
        print('({},{})'.format(*r[n]))
    except:
        # n > 10000
        v, u = divmod(n-10000, 104)
        tx, ty = baseX+(-2)*v, baseY+(-2)*v
        tx += md[u][0]
        ty += md[u][1]
        print('({},{})'.format(tx,ty))

[zerojudge] e998: S形矩陣

from sys import *

A = list(map(str, range(1, 10001)))
# 一次建好型態為 string 的表
opt = '' # 最後一次印
for s in stdin:
    n = int(s)
    for i in range(n):
        if(i%2==0): opt += ' '.join(A[i*n:i*n+n]) + ' \n'
        else: opt += ' '.join(A[i*n:i*n+n][::-1]) + ' \n'
        # i 為奇數時取出值，先反轉再 join
        # i 為偶數時，直接 join
    opt += '\n'
stdout.write(opt)

[zerojudge] a450: 棒棒糖比身高

from sys import stdin
import bisect
# 請參考 https://docs.python.org/3/library/bisect.html

n, q = map(int, stdin.readline().split())
f = sorted([int(x) for x in stdin.readline().split()])
# 先排序
# 例如  8 5 10 11 8 會排序成 5 8 8 10 11
# 考慮到會有重複的元素
# 使用 bisect.bisect_left  取左邊位置
#      bisect.bisect_right 取右邊位置
for _ in range(q):
    a, b = map(int, stdin.readline().split())
    a = bisect.bisect_left(f, a)
    b = bisect.bisect_right(f, b)
    r = b - a
    if(r): print(r)
    else: print('The candies are too short')

[zerojudge] a121: 質數又來囉

from sys import stdin 

def isPrime(n):
    '''
    參考 http://www.csie.ntnu.edu.tw/~u91029/Prime.html
    質數判定
    ''' 
    if(n == 1): return 0
    # 傳進來的 n 都已經過濾過，底下這 3 行先 mark 起來
    #if(n in (2, 3)): return 1
    #if(n % 2 == 0): return 0
    #if(n%6 not in [1,5]): return 0
    u = n - 1
    t = 0
    while(u % 2 == 0):
        u >>= 1
        t += 1
    sprp = [2, 7, 61]
    for sk in sprp:
        a = sk % n
        if (a == 0 or a == 1 or a == n-1): continue
        x = pow(a, u, n)
        if (x == 1 or x == n-1): continue
        for i in range(t-1):
            x = pow(x, 2, n)
            if (x == 1): return 0
            if (x == n-1): break
        if (x != n-1): return 0
    return 1
    

for s in stdin:
    a, b = map(int, s.split())
    r = 0
    k = a//6
    v = 1
    while(v):
        for n in (k*6+1, k*6+5):
            # 為了節省時間，只檢測 6p+1, 6p-1
            # 其實除了 5 以外， 5 的倍數也不必測
            if(n < a): continue
            if(n > b): # 超過上界
                v = 0            
                break
            r += isPrime(n)
        k += 1
    if(a <= 2 and b >= 2): r += 1
    if(a <= 3 and b >= 3): r += 1
    # 上面的檢測會遺漏 2, 3 在這裡補
    print(r)

[zerojudge] d984: 棄保效應

from sys import stdin

op = 'ABC'
for s in stdin:
    f = [[i, int(c)] for i, c in enumerate(s.split())]
    f.sort(key = lambda z: z[1])
    t = f.pop(0)
    f[0][1] += t[1]
    f.sort(key = lambda z: -z[1])
    print(op[f[0][0]])

[zerojudge] a091: 今晚打老虎

import sys, bisect
'''
你如果把每個值都塞到 list
list 太長造成每個 insert , sort , pop 都很耗時
可以用一個 dict 來記錄每個值出現的次數
'''
f = []   # 要維護的 list
d = {}   # 記錄每個值出現的次數
for s in sys.stdin:
    if(s == '2\n'): # Query MAX
        p = f[-1]
        print(p)   
        d[p] -= 1  
        if(d[p] == 0): f.pop()
        '''
        印出尾部最大值
        計數減一
        計數為零才 pop()
        '''
    elif(s == '3\n'): # Query MIN
        p = f[0]
        print(p)
        d[p] -= 1
        if(d[p] == 0): f.pop(0)
        '''
        印出頭部最小值
        計數減一
        計數為零才 pop(0)
        '''
    else: # Insert
        t = int(s.replace('1 ',''))
        if(d.__contains__(t)): d[t] += 1
        else: d[t] = 1
        '''
        計數不存在時設為 1
        反之加 1
        '''
        if(d[t] == 1):
            bisect.insort_left(f, t)
        '''    
        如為新成員才 insert
        利用 bisect.insort_left = insert and sort
        '''

[zerojudge] e974: 2. 座位安排 (Seats)

from sys import stdin 
from collections import deque
r, c, n = map(int, stdin.readline().split())
h = deque([deque([x for x in range(i,i+c)]) for i in range(1, r*c+1, c)])
n -= 1
odd = even = n//2
even += n%2
h.rotate(odd % r)
for u in h:
    u.rotate(even % c)
    u = list(map(str, u))
    print(' '.join(u))

[zerojudge] b331: NOIP2013 2.表达式求值

import sys
from functools import reduce
import operator

def fn(x):
    x = [int(c) for c in x.split('*')]
    return(reduce(operator.mul, x, 1))

s = sys.stdin.readline().strip().split('+')
print(sum([fn(x) for x in s])%10000)

[zerojudge] e942: pC. 數字排列

'''
一開始擔心記憶體不夠
使用索引值求全排列
將索引值對應的值印出
0.8s
'''
from sys import stdin, stdout
from itertools import permutations

ind = [0,1,2,3,4,5,6,7,8]
n = int(stdin.readline())
f = sorted(stdin.readline().strip().split(), key = int)
# 為了節省輸出時要轉回 str 的時間，這裡保留 str
p = ind[:n]
U = permutations(p)
for u in U: stdout.write(' '.join([f[i] for i in u]) + '\n')


#################################
# 直接全排列 0.3s
#

from sys import stdin, stdout
from itertools import permutations

n = int(stdin.readline())
f = sorted(stdin.readline().strip().split(), key = int)
U = permutations(f)
for u in U: stdout.write(' '.join(u) + '\n')

[zerojudge] c463: apcs 樹狀圖分析 (Tree Analyses)

class node:
    def __init__(self):
        self.index = 0
        self.parent = 0
        self.height = 0
        self.child = False
    
from sys import stdin
n = int(stdin.readline())
nodes = {k: node() for k in range(1, n+1)} 
# 初始化節點   
for i in range(1, n+1):
    s = stdin.readline().strip()
    nodes[i].index = i
    if(s != '0'):
        tmp = [int(x) for x in s.split()][1:]
        nodes[i].child = True
        for x in tmp: nodes[x].parent = i
    # 依序讀入測資，紀錄每個 node 的屬性
    
root = [v for v in nodes.values() if v.parent == 0][0]
print(root.index)
# 尋找 root , root 沒有 parent
  
leaves = [v for v in nodes.values() if not v.child]
# 尋找 leaf , leaf 沒有 child
# 由 leaf 往上數，並記錄 height  
for leaf in leaves:
    cnt = 1
    nxt = leaf.parent
    while(1):
        if(cnt <= nodes[nxt].height): break
        nodes[nxt].height = cnt
        '''
        數到某一個 node 發現有 height
        如果 cnt > height 表示這個深度較深，
        繼續往上，反之脫離。
        '''
        nxt = nodes[nxt].parent
        if(nxt == 0): break
        # 繼續往上推
        cnt += 1
ans = sum([v.height for v in nodes.values()])
# 加總每個節點的高度
print(ans)

[zerojudge] b964: 第 1 題 成績指標

from sys import stdin

opt = ''
for s in stdin:
    s = stdin.readline().strip()
    f = sorted([int(x) for x in s.split()])
    opt += ' '.join(map(str, f)) + '\n'
    n = [x for x in f if x < 60]
    if(n): opt += str(n[-1]) + '\n'
    else: opt += 'best case\n'
    n = [x for x in f if x >= 60]
    if(n): opt += str(n[0]) + '\n'
    else: opt += 'worst case\n'
       
print(opt.strip()) # 嚴格比對

[zerojudge] d828: Pascal's triangle's secret (II)

'''
依題意手算了幾個 n 發現是個 Fibonacci numbers
看到這種 n 很大，且要求取模輸出
猜想輸出的值大概會在 n 在某值時循環
google 發現是 Pisano period
網路上有求 Pisano period 的公式
此題我先算好 m = 10000, pisano = 15000
底下先建表，讀取測資後查表輸出
'''

from sys import stdin

f = [1,1,2,3,5,8]

pisano = 15000
for i in range(6, pisano):
    t = (f[-1]+f[-2])%10000
    f.append(t)

for s in stdin:
    n = int(s) % pisano
    print(f[n])

[zerojudge] e583: 11040 - Add bricks in the wall

from sys import stdin

N = int(stdin.readline())

for _ in range(N):
    for __ in range(3): 
        s = stdin.readline()    
        # 前 3 行資料不重要
    s4 = [int(x) for x in stdin.readline().split()]
    s5 = [int(x) for x in stdin.readline().split()]
    base = []
    for i in range(len(s4)):
        base.append(s5[i])
        base.append((s4[i]-s5[i]-s5[i+1])//2)
    base.append(s5[-1])  
    '''
    關鍵在最下 2 層
    最下層每 2 個數中要插入一個值
    這個值 = (s4[i]-s5[i]-s5[i+1])//2
    先把最下層每個數都求出
    '''    
    r = [base]
    for i in range(8):
        tmp = []
        for j in range(len(r[-1])-1):
            tmp.append(r[-1][j]+r[-1][j+1])
        r.append(tmp)
        
    for z in r[::-1]: print(*z)

[zerojudge] e799: p6. 資工系的浪漫

from sys import stdin
n, m = [int(c) for c in stdin.readline().split()]
ch = stdin.readline().strip() + ' '
for _ in range(n):
    s = bin(int(stdin.readline()))[2:].zfill(m)
    s = s.replace('1', ch).replace('0', '. ').strip()
    print(s)

[zerojudge] e929: pC. 分解質因數

import sys 
import math

limit = 20000000
u = int(math.sqrt(limit))
sieve = [0, 0, 2, 3] + [1] * (u - 4)
prime = [2]
for i in range(3, u, 2):
    if(sieve[i] == 0): continue
    prime.append(i)
    for j in range(i * i, u, i): 
        sieve[j] = 0

def fact(n):
    r = []
    k = math.sqrt(n)
    for x in prime:
        if(x > k): break
        if(x > n): break 
        c = 0
        while(n % x == 0):
            c += 1
            n //= x
        if(c): r.append([x,c])
    if(n > 1): r.append([n,1])
    return r

def op(z):
    if(z[1] == 1): return str(z[0])
    return '{}^{}'.format(*z)
    
for s in sys.stdin:
    n = int(s)
    f = fact(n)
    r = list(map(op, f))
    print('{} = {}'.format(n, ' * '.join(r)))

[zerojudge] e924: pC. 括號配對

from sys import stdin

chk =  ['()','[]','<>','{}']

T = int(stdin.readline())
for _ in range(T):
    s = stdin.readline().strip()
    while(s):
        p1 = len(s)
        for z in chk: s = s.replace(z, '')
        p2 = len(s)
        if(p2 == p1): break
        # p2 == p1 表示找不到成對的括號
        
    print('N' if s else 'Y')

[zerojudge] d563: 等值首尾和

from sys import stdin
from itertools import accumulate
# accumulate([1,2,3,4,5]) --> 1 3 6 10 15
# https://docs.python.org/3/library/itertools.html#itertools.accumulate

f = [int(x) for x in stdin.readline().split()][1:]
a = set(accumulate(f))
b = set(accumulate(f[::-1]))
c = a & b
print(len(c))

'''
這題測資沒有斷行
所以 input 取  f[1:]
以  7 3 6 2 1 4 5 2
f = [3, 6, 2, 1, 4, 5, 2]
accumulate(f) =       [3, 9, 11, 12, 16, 21, 23] # 從前面累計
accumulate(f[::-1]) = [2, 7, 11, 12, 14, 20, 23] # 從後面累計
a = set(accumulate(f)) =       {3, 9, 11, 12, 16, 21, 23}
b = set(accumulate(f[::-1])) = {2, 7, 11, 12, 14, 20, 23}
c = a & b 是交集
print(len(c)) 交集的個數
'''

[zerojudge] e346. 區間和練習

import sys 
from itertools import accumulate
opt = ''
while(1):
    try:
        s = sys.stdin.readline()
        s = '0 ' + sys.stdin.readline()
        q = [int(x) for x in s.split()]
        q = list(accumulate(q))
        m = int(sys.stdin.readline())
        for i in range(m):
            l, r = [int(x) for x in sys.stdin.readline().split()]
            opt += '{}\n'.format(q[r]-q[l-1])
    except: break
print(opt.strip())

[zerojudge] a007: 判斷質數

from sys import stdin

def isPrime(n):
    '''
    參考 http://www.csie.ntnu.edu.tw/~u91029/Prime.html
    質數判定
    ''' 
    if(n in [2,3,5]): return 1
    if(n%2 == 0): return 0
    if(n%6 not in [1,5]): return 0
    u = n - 1
    t = 0
    while(u % 2 == 0):
        u >>= 1
        t += 1
    sprp = [2, 7, 61]
    for sk in sprp:
        a = sk % n
        if (a == 0 or a == 1 or a == n-1): continue
        x = pow(a, u, n)
        if (x == 1 or x == n-1): continue
        for i in range(t-1):
            x = pow(x, 2, n)
            if (x == 1): return 0
            if (x == n-1): break
        if (x != n-1): return 0
    return 1
    
r = ['非質數', '質數']
for s in stdin:
    v = isPrime(int(s))
    print(r[v])

[zerojudge] d387: 10235 - Simply Emirp

from sys import stdin

def isPrime(n):
    '''
    參考 http://www.csie.ntnu.edu.tw/~u91029/Prime.html
    質數判定
    ''' 
    if(n == 2): return 1
    if(n%2 == 0): return 0
    if(n%6 not in [1,5]): return 0
    u = n - 1
    t = 0
    while(u % 2 == 0):
        u >>= 1
        t += 1
    sprp = [2, 7, 61]
    for sk in sprp:
        a = sk % n
        if (a == 0 or a == 1 or a == n-1): continue
        x = pow(a, u, n)
        if (x == 1 or x == n-1): continue
        for i in range(t-1):
            x = pow(x, 2, n)
            if (x == 1): return 0
            if (x == n-1): break
        if (x != n-1): return 0
    return 1

ans = ['not prime.', 'prime.', 'emirp.']

for s in stdin:
    s = s.strip()
    sr = s[::-1]
    v = isPrime(int(s))
    # 先檢查 int(s) 是否為質數 
    if(v and sr != s):
        # s 是質數才檢查 sr
        v += isPrime(int(sr))
    print('{} is {}'.format(s, ans[v]))

[zerojudge] a223: 10298 - Power Strings

from sys import stdin
import math

'''
題目說 字串長度 <= 1000000
所以先來建立一個質數表
'''
limit = 1000000
u = int(math.sqrt(limit))
sieve = [0, 0, 2, 3] + [1] * (u - 4)
prime = [2]
for i in range(3, u, 2):
    if(sieve[i] == 0): 
        # sieve[i] 為 0 表示被篩掉了    
        continue
    prime.append(i)
    for j in range(i*i, u, i): 
        sieve[j] = 0
########

def fact(n): # 因數分解
    r = []
    k = math.sqrt(n)
    for x in prime:
        if(x > k): break
        # 檢查到 n 的平方根
        c = 0
        while(n % x == 0):
            c += 1
            n //= x
        if(c): r.append([x,c])
        # c 是試除的次數        
    if(n > 1): r.append([n,1])
    # 剩餘的數 > 1 必定是質因數
    return r

def expand(v, i): 
    if(i == len(prt)): return
    for h in range(prt[i][1]+1):
        tmp = v
        tmp *= prt[i][0] ** h
        f.add(tmp)
        expand(tmp, i+1)

for s in stdin: # 開始 input
    s = s.strip()
    if(s == '.'): break
    n = len(s) # 字串長度
    if(s[0] * n == s):
        # 如果出現 aaaaa 直接輸出 5
        print(n)
        continue
    prt = fact(n)
    # 先對字串長度做質因數分解
    # 如果 n = 6,  fact(6) = [[2,1],[3,1]]
    f = set()
    expand(1, 0)
    # 遞迴將 prt 展開為正因數
    # fact(6) = [[2,1],[3,1]] = [1,2,3,6]
    正因數表 = sorted(list(f))
    '''
    接下來要針對字串長度的正因數來比對
    1 就不用了，上面檢查過了
    '''
    for 長度 in 正因數表[1:]:
        檢查字串 = s[:長度]
        倍數 = n // 長度
        if(檢查字串 * 倍數 == s):
            print(倍數)
            break
 

[zerojudge] d713: 中位數

import sys
from heapq import *
# https://docs.python.org/zh-tw/3/library/heapq.html
heapL = []
heapR = []
'''
heapL 放 <= 中位數的值，
因為我取左半部，都會取最大值，所以我存入負數。
heapR 放 >= 中位數的值，
因為我取右半部，都會取最小值，所以我存入原數。

heappop     : 從 heap 取出並回傳最小的元素
heappush    : only push
heappushpop : push and pop  
'''
heapify(heapL)
heapify(heapR)
# heapify() 將一個 list 轉成一個 heap
count = 0  
# 讀取記數，判斷 element 數量奇偶
# 奇數時，讓左邊多一個
# 偶數時，讓兩邊一樣多

for s in sys.stdin: # 開始 input
    n = int(s)
    count += 1
    if(count == 1):
        heappush(heapL, -n)
        print(n)
        continue
        # first element, 直接印出, 存入負值
        # 直接 continue 讀取下一個值
    largestL = -heapL[0]
    # heapL[0] 是 heapL 的最小值，
    # 加負號 = 左邊最大值 
    if(count % 2 == 0): 
        # element count 偶數時
        if(n >= largestL):
            heappush(heapR, n)  
            # 把 n 存入右邊，2 側數量相等
            smallestR = heapR[0]
            # 查詢 heapR[0] , 這是右邊的最小值
            r = (largestL + smallestR) // 2
        else:
            heappushpop(heapL, -n)
            # 把 n 存入左邊, 同時刪除 largestL
            heappush(heapR, largestL)
            # 把 largestL 存入右邊，2 側數量相等
            smallestR = largestL
            largestL = -heapL[0]
            # 新的左側最大值
            r = (largestL + smallestR) // 2
    else:    
        # element count 奇數時
        smallestR = heapR[0]
        if(n > smallestR):
            # 此時 n 要放在右邊
            # 右邊多一個要移到左邊
            heappush(heapL, -(smallestR))
            # smallestR 直接塞左邊
            heappushpop(heapR, n)
            # 把 n 放右邊並刪除原本最小值
            r = -(heapL[0])
            # 左邊比右邊多一個, 最大的數就是中位數
        else:
            heappush(heapL, -(n))
            # 直接把值塞左邊
            r = -(heapL[0])
            # 左邊比右邊多一個, 最大的數就是中位數
    print(r)

[zerojudge] e080: read and write

import sys

mx = 200000  
# 設定每次讀取的長度，請自行調整。
# 設太大會 MLE 太小會 TLE
sp = 0
# space 的位置，也是 x 的長度。
pr = 0
# 找到 space 會開啟列印狀態， 
while(1):
    tmp = sys.stdin.buffer.read(mx).decode()
    # 每次讀取一段
    本次讀取長度 = len(tmp)
    if(pr):
        print(tmp, end = '')
        # 列印模式已打開，讀到的都要印出
    else:
        # 還沒開始列印
        v = tmp.find(' ')
        # 看看本次有沒有讀到 space
        if(v == -1): 
            sp += mx
            # 沒看到 space 先紀錄 x 的長度
        else:
            pr = 1
            sp += v
            print(tmp[v+1:], end = '')
            # 有看到 space 先開啟列印模式
            # 把 space 前的長度加到 sp
            # 把 space 後面的字先印出
    if(本次讀取長度 < mx): break
    # 到檔尾了
    
print(' ', end = '') # y 印好了補個 space        
sys.stdin.seek(0)    # 倒回原點

while(sp):
    tmp = sys.stdin.buffer.read(mx).decode()
    本次讀取長度 = len(tmp)
    本次列印長度 = min(sp, 本次讀取長度)
    本次列印內容 = tmp[:本次列印長度]
    print(本次列印內容, end = '')
    sp -= 本次列印長度

[zerojudge] d366: 00294 - Divisors

from sys import stdin
import math

# 先用篩法建一小段質數
u = 100
sieve = [0, 0, 2, 3] + [1] * (u - 4)
prime = [2]
for i in range(3, u, 2):
    if(sieve[i] == 0): continue
    prime.append(i)
    for j in range(i * i, u, i): 
        sieve[j] = 0
#######################    
def isPrime(n):
    '''
    參考 http://www.csie.ntnu.edu.tw/~u91029/Prime.html
    質數判定
    ''' 
    if(n == 2): return 1
    if(n%2 == 0): return 0
    if(n%6 not in [1,5]): return 0
    u = n - 1
    t = 0
    while(u % 2 == 0):
        u >>= 1
        t += 1
    sprp = [2, 7, 61]
    for sk in sprp:
        a = sk % n
        if (a == 0 or a == 1 or a == n-1): continue
        x = pow(a, u, n)
        if (x == 1 or x == n-1): continue
        for i in range(t-1):
            x = pow(x, 2, n)
            if (x == 1): return 0
            if (x == n-1): break
        if (x != n-1): return 0
    return 1

def factorize(n):
    # 因數分解   
    # 參考網路上的解法，非原創
    if(isPrime(n)): return 1, n, 1
    x_fixed = 2
    cycle_size = 2
    x = 2
    factor = 1

    while factor == 1:
        count = 1
        while count <= cycle_size and factor <= 1:
            x = (x*x + 1) % n
            factor = math.gcd(x - x_fixed, n)
            count += 1
        cycle_size *= 2
        x_fixed = x
    c = 0
    while(n % factor == 0):
        n //= factor
        c += 1
    return n, factor, c
    
def 計算因數(n):
    if(n == 1): return 1
    if(isPrime(n)): return 2
    k = int(n ** 0.5) # 上限
    r = 1
    for x in prime:
        if(x > k): break
        c = 0
        while(n % x == 0):
            c += 1
            n //= x
        r *= (c + 1)
    '''
    先用建立好的一小段質數表試除
    剩餘的用 factorize 分解
    '''    
    while(n > 1):
        n, y, z = factorize(n)
        r *= (z + 1)
        if(n == 1): break
    return r

N = int(stdin.readline()) # 測資筆數
for i in range(N):
    L, U = map(int, stdin.readline().split())
    P, D = 0, 0
    for j in range(L, U+1):
        tmp = 計算因數(j)
        if(tmp > D):
            P, D = j, tmp
    print('Between {} and {}, {} has a maximum of {} divisors.'.format(L, U, P, D))

[zerojudge] c636: 十二生肖

import sys
ani = '鼠牛虎兔龍蛇馬羊猴雞狗豬'
for s in sys.stdin:
    n = int(s)
    if(n > 0): n = (n-1) % 12
    else: n = n % 12
    
    print(ani[n])

[zerojudge] d120: 10699 - Count the factors

from sys import stdin
import math  

'''
題目說 n <= 1000000
而  n 的質因數 <= sqrt(n)
所以先來建立一個質數表
'''
limit = 1000000
u = int(math.sqrt(limit))
sieve = [0, 0, 2, 3] + [1] * (u - 4)
prime = [2]
for i in range(3, u, 2):
    if(sieve[i] == 0): continue
    # sieve[i] 為 0 表示被篩掉了    
    prime.append(i)
    for j in range(i*i, u, i): 
        sieve[j] = 0
# 你可以 print(prime) 來核對
# print(prime)  

def 質因數計次(n):
    tmp = n
    res = 0
    k = math.sqrt(n)
    for pr in prime:
        if(pr > k): break
        # 檢查到 n 的平方根
        c = 0
        while(tmp%pr == 0):
            c = 1
            tmp //= pr
        res += c
        # c 是試除符合       
    if(tmp > 1): res += 1
    # 剩餘的數 > 1 必定是質因數
    return '{} : {}'.format(n, res)

opt = []
for s in stdin:
    n = int(s)
    if(n == 0): break
    opt.append(質因數計次(n))
    
print('\n'.join(opt))
# 一次輸出        

[zerojudge] d139: Compressed String

from sys import stdin

for s in stdin:
    s = s.strip()
    ans = ''
    while(s):
        原長度 = len(s)
        c = s[0]  # 第一個字元
        s = s.lstrip(c)
        新長度 = len(s) 
        長度差 = 原長度 - 新長度
        if(長度差 < 3):
            ans += c * 長度差        
        else:
            ans += '{}{}'.format(長度差, c)
    print(ans)

[zerojudge] a565: 2.p&q的邂逅

from sys import stdin

T = int(stdin.readline())
for _ in range(T):
    s = stdin.readline().replace('.', '')
    # 先將 . 去掉 
    原長度 = x = len(s)    
    while(x):
        s = s.replace('pq', '')
        # 把 pq 抽走
        y = len(s)
        if(y == x): break
        x = y
    print((原長度-x)//2)

[zerojudge] e446: 排列生成

import sys

a = int(input()) # 只有一行輸入
f = [str(c) for c in range(1, a+1)]
# 輸入 3  -->  ['1', '2', '3']
d = permutations(f)
'''
利用 permutations 求全排列
print(list(d)) 可以觀察 d
[('1', '2', '3'), ('1', '3', '2'), 
 ('2', '1', '3'), ('2', '3', '1'), 
 ('3', '1', '2'), ('3', '2', '1')]
'''
for u in d: 
    sys.stdout.write(' '.join(u) + '\n')

[zerojudge] d518: 文字抄寫 II

import sys
opt = ''
for s in sys.stdin:
    w = int(s)
    c = 1 # counter init
    f = [{} for i in range(26)] 
    # 每個字母獨立一個 dict              
    for i in range(w):
        s = sys.stdin.readline()
        ch = ord(s[0]) - 97
        # 讀入字串的第一個字母的 ascii 值
        # 在 f 的位置  f[0] 就是 a 的字典
        if(f[ch].__contains__(s)):
            opt += 'Old! {}\n'.format(f[ch][s])
            # 字典已有此字
        else:
            opt += 'New! {}\n'.format(c)
            f[ch][s] = c
            # 字典沒有這個字，將 c 紀錄起來。
            c += 1
sys.stdout.write(opt.strip())
# 一次印出

[zerojudge] d057: 11494 - Queen

import sys 

for s in sys.stdin:
    if(s == '0 0 0 0\n'): break
    x1, y1, x2, y2 = [int(z) for z in s.split()]
    m, n = abs(x1-x2), abs(y1-y2)
    r = 2
    if(m + n == 0): r = 0    # 同一點
    elif(m * n == 0): r = 1  # 同一軸
    elif(m == n): r = 1      # 同斜率
    print(r)

[zerojudge] d596: 1. 猜九宮格裡的地雷

import sys

# 把每個九宮格的鄰居先建表
d = ({'1': set(['2','4']),     
      '2': set(['1','3','5']),
      '3': set(['2','6']),
      '4': set(['1','5','7']),
      '5': set(['2','4','6','8']),
      '6': set(['3','5','9']),
      '7': set(['4','8']),
      '8': set(['5','7','9']),
      '9': set(['6','8'])})
      
w = int(sys.stdin.readline())
for i in range(w):
    a, b, c = sys.stdin.readline().strip().split()
    # d[a] 是可能地雷， d[b] 及 d[c] 是排除的
    r = sorted(list(d[a] - d[b] - d[c]))
    # 使用減法可以省去很多判斷
    # r 為空，表示矛盾。
    if r: print(*r)
    else: print('Empty')

[zerojudge] a010: 因數分解

# a010 因數分解 python
import sys
import math
'''
題目說 n <= 1000000
而  n 的質因數 <= sqrt(n)
所以先來建立一個質數表
'''
limit = 1000000
u = int(math.sqrt(limit))
sieve = [0, 0, 2, 3] + [1] * (u - 4)
prime = [2]
for i in range(3, u, 2):
    if(sieve[i] == 0): 
        # sieve[i] 為 0 表示被篩掉了    
        continue
    prime.append(i)
    for j in range(i * i, u, i): 
        sieve[j] = 0
# 你可以 print(prime) 來核對
# print(prime)  

def fact(n):
    r = []
    k = math.sqrt(n)
    for x in prime:
        if(x > k): break
        # 檢查到 n 的平方根
        c = 0
        while(n % x == 0):
            c += 1
            n //= x
        if(c): r.append([x,c])
        # c 是試除的次數        
    if(n > 1): r.append([n,1])
    # 剩餘的數 > 1 必定是質因數
    return r

def op(z):
    if(z[1] == 1): return str(z[0])
    return '{}^{}'.format(z[0], z[1])
    
# 主程式    
for s in sys.stdin:
    n = int(s)
    f = fact(n) # 先分解
    # print(f) 看結果對不對
    r = list(map(op, f))
    print(' * '.join(r))
    '''
    假設 n = 100
    fact(n) = [[2, 2], [5, 2]]
    r = ['2^2', '5^2']
    '''

[zerojudge] e700: 星座

import sys 
for s in sys.stdin:
    m, d = s.strip().split('/')
    md = m.rjust(2, '0') + d.rjust(2, '0')
    if(md < '0121'): print('摩羯座')
    elif(md >= '0121' and md <= '0219'): print('水瓶座')
    elif(md >= '0220' and md <= '0320'): print('雙魚座')
    elif(md >= '0321' and md <= '0420'): print('牡羊座')
    elif(md >= '0421' and md <= '0521'): print('金牛座')
    elif(md >= '0522' and md <= '0621'): print('雙子座')
    elif(md >= '0622' and md <= '0722'): print('巨蟹座')
    elif(md >= '0723' and md <= '0821'): print('獅子座')
    elif(md >= '0822' and md <= '0923'): print('處女座')
    elif(md >= '0924' and md <= '1023'): print('天秤座')
    elif(md >= '1024' and md <= '1122'): print('天蠍座')
    elif(md >= '1123' and md <= '1222'): print('射手座')
    elif(md >= '1223'): print('摩羯座')