[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)