o079. 4. 最佳選擇

 題目描述：

給一個長度為 n 的正整數序列 a1,a2...an ，你可以執行多次操作 (包含 0 次)，每次操作只能選擇這個序列的第一個或最後一個數字，再將這個數字從序列中刪除並自己搜集起來。

求滿足總和不超過 k 且搜集的數字奇數和偶數個數相同的條件下，所能搜集的數字總和最大為多少。

這題步驟比較多，簡單來說，怎麼選都是前面選幾個，後面選幾個，將總和加起來，所以第一步要先得出前後綴和。：

假設測資a1...an分別是1,2,3,4,5,6

1.先算出前後綴和pre = [1,3,6,10,15,21] , ends = [6,11,15,18,20,21]，

再來就是前後綴合的組合囉，想法是這樣，我們取出pre[0]去跟ends的每一個結合看看，可以結合的標準是範圍不重複，且奇偶數個數相同，且總和不超過k，的可能中求最大，先別管時間問題了，光要做這件事情，我們就必須在算前後綴和時，順便紀錄了每一個前後綴合的奇偶數個數，我把前綴和記錄成這樣：

pre = [[0,0],[1,-1],[3,0],[6,-1],[10,0],[15,-1],[21,0]]，這代表組成21的時候奇偶個數沒差別，15的時候奇偶個數差1。

再來end我記成這樣：

endIndex = {1: [-5, -3, -1], 0: [-4, -2, 0]}

endSum = {1: [6, 15, 20], 0: [11, 18, 21]}

代表偶數比奇數多一個的後綴和有6,15,20其最左邊的資料在第5,3,1個位置，解釋一下，以20為例，20是2,3,4,5,6相加的結果，其中，偶數多奇數一個，且資料起始位置是1(2在a的第一個位置)，補充一下，為什麼5,3,1記成-5,-3,-1，因為我希望保持結構是升序排序，那麼我後面做二分搜的時候比較容易。

所以有了pre,endIndex,endSum之後該怎麼做呢，依樣，依序取出pre的每一個資料，假設拿到pre[1]，那麼因為pre[1]又等於[1,-1]，其中1代表前綴和是1，1代表取到第一個位置，-1代表奇偶差是1，所以我們要的資料就是在endIndex[1],endSum[1]之中，那要怎麼快速找到位置不重複，且相加小於k的資料呢，這邊我們就是用二分搜了，我很懶，直接用工具了。

上面這段說明，記得跟一下文字的標色，會比較好閱讀。

以下是完整程式碼：

import bisect
n,k = [int(i) for i in input().split()]
d = [int(i) for i in input().split()]

pre = [[0,0]]
for i in range(0,len(d)):
    if d[i] % 2 == 0: 
        p = 1
    else:
        p = -1
    last = pre[-1]
    pre.append([last[0]+d[i] , last[1]+p])
    
ends = 0
endoe = 0
endSum = {}
endIndex = {}
for i in range(len(d)-1 , -1 , -1):
    if d[i] % 2 == 0: 
        endoe += 1
    else:
        endoe += -1
    ends += d[i]
    if endoe in endSum:
        endSum[endoe].append(ends)
        endIndex[endoe].append(-i)
    else:
        endSum[endoe] = [ends]
        endIndex[endoe] = [-i]
#print(pre)
#print(ends)
#print(endIndex)
#print(endSum)
ans = 0
for i in range(n+1):
    p = pre[i][1]
    if pre[i][0] > ans and p == 0 and pre[i][0] <= k:
        ans = pre[i][0]
    if -p in endSum:
        #print('endSum[-p]' , endSum[-p] , pre[i][0] , k - pre[i][0])
        q = bisect.bisect_left(endSum[-p], k - pre[i][0]+1)#找與pre[i][0](前綴)相加小於k的資料位置
        if q > 0:
            #print(pre[i][0] , endSum[-p][q-1])
            q = bisect.bisect_left(endIndex[-p][0:q],-i)#找到所有相加符合標準中，起始位置最左邊的後綴合(後綴起始位置越左邊越大)
            if q > 0:
                #print(q)
                ans = max(ans , pre[i][0] + endSum[-p][q-1])
                #print(ans)
        
print(ans)

o077. 2. 電子畫布

題目描述：

有一個 H ╳ W 的電子畫布，一開始數值都是 0 代表未填色，接下來請模擬 N 次畫筆操作。

每次畫筆操作為選一個座標 (r,c) 停留 t 秒，他會將曼哈頓距離 <= t 的區塊染上顏色 x。若有多個顏色重複填到相同區塊，顏色的數值會累加起來。

請輸出 N 次操作後的畫布狀態。

這題簡單來說就是要想個找出距中心點等距的菱形座標。

我思考的方式很簡單，首先找到中心點，並根據該點的資料找出他離他最遠單的Y座標端點。

得到,以下這個迴圈。

for y in range(r-t,r+t+1):

注意一下，菱形的關鍵就是從中心點到任一端點都是等距，所以我們先把中心點座標取這次拿到的Y座標算出差距得到：

ydif = abs(r-y)#ydif就是中心點與這次y座標的差距

已知ydif+xdif=t，現在t跟ydif都是已知，所以xdif = t-abs(ydif)，所以就可以得出下面這個迴圈：

for x in range(c-(t-ydif) , c+(t-ydif)+1):

菱形矩陣搞定後，這題就沒有其他問題囉，以下是完整程式。

def t():
    h,w,n = [int(i) for i in input().split()]
    tt = [[0 for i in range(w)] for j in range(h)]
    
    
    for j in range(n):
        r,c,t,q = [int(i) for i in input().split()]
        for y in range(r-t,r+t+1):
            if y < 0 or y > h-1: 
                continue
            ydif = abs(r-y)
            for x in range(c-(t-ydif) , c+(t-ydif)+1):
                if x < 0 or x > w-1:
                    continue
                tt[y][x] += q
    for i in tt:
        for j in i:
           print(j , end = ' ')
        print()
t()

o076. 1. 特技表演

有一個城鎮有 n 棟高樓，樓高分別為 h1,h2,.....hn，市長想要在城鎮中心舉辦高空特技表演，該特技表演會從某棟大樓上朝右側滑翔至地面。

為了表演人員的安全，滑翔的路徑樓高必須越來越低，請你找出一個最長的滑翔路徑。

簡單來說就是要從資料中找出最長的降冪集合，這題沒什麼時間問題，直接透過迴圈查找

def t():

    n = int(input())

    d = [int(i) for i in input().split()]

    c = 0

    k = 9999999999

    ans = 0

    for i in d:

        if i < k:

            c += 1

        else:

            if ans < c:

                ans = c

            c = 1

        k = i

    if ans < c:

        ans = c

    print(ans)

t()

o078. 3. 缺字問題

 題目敘述：

給定一個大小為 K 個字母的集合和字串 S，求出在使用該集合所組出長度為 L 字串中，不為字串 S 子字串的最小字典序字串為何。

自如字母集合{a,c,m}，其能組出長度為 2 的字串字典序由小到大排序為： aa < ac < am  < ca < cc < cm < ma < mc < mm。字串 S 為accaamcm，因此 ma 為不在 S 內的最小字典序字串。

這題看起來就很dfs，一般APCS第三題時間上是不會過關，但這題可以，想必官方考慮到國高中生期末考將至，難度有稍微調降了。簡單來說，想辦法求出a,c,m中不重複的所有排序組合。

以下是超白話思考順序

DFS思考的重點有兩個，每次要做什麼，終止條件是什麼。

啥都還沒想到的時候就先寫出

def dfs():#先把函式建起來

再來開始思考每次呼叫函示要做什麼，以這題為例，我們要嘗試在函式內組出不同的字母排列組合，所以應該需要一個字串參數帶入函式之中。所以：

def dfs(s):

有了參數後，可以想想看終止條件是什麼，終止條件就是組出長度為L的字串，所以：

def dfs(s):

    if len(s) == L:

        dosomething

長度到了之後呢，我們程式的目標是要找出不在字串S中的子字串啊，所以：

def dfs(s):

    if len(s) == L:

        if s not in S:#代表s不在S之中

            print(s)

            return False#不要繼續找了

        return True#繼續找吧

    for i in k:

        if dfs(ss+i) == False:

            return False

k = list(input())

l = int(input())

S = input()

dfs("" )

再加上剪枝(優化加速)，就變成以下這樣囉：

def dfs(ss):
    if ss in dic:
        return True
    dic[ss] = 1
    if len(ss) == l:
        if ss not in existStr:
            print(ss)
            return False
        return True
    for i in k:
        if dfs(ss+i) == False:
            return False

k = list(input())
l = int(input())
s = input()

existStr = set(s[i:i+l] for i in range(len(s) - l + 1))
dic = {}
dfs("" )

我把剪枝(用來加速)的部分標藍色，基本上這題不剪枝，也不會超時，非常佛心呢。

h206. 強者就是要戰，但......什麼才是強者呢？

         這題是很好的遞迴問題，每次遞迴的時候都要帶入此次遞迴的左右邊界、及這次是要取區間最大還是取區間最小的flag。

        完整程式如下：

def t(l , r , isBig):
    if l == r-1:
        return d[l]
    m = (l+r)//2
    if isBig: 
        g = max(t(l,m,0) , t(m,r,0))
    else:
        g = min(t(l,m,1) , t(m,r,1))
    return g
        
n = int(input())
d = [int(i) for i in input().split()]

print(t(0,n,1))

h631. 美麗人生

         白話來說，就是把測資去掉所有2、3、5的因數後，如果只剩下1，就顯示ugly，反之顯示beautiful，這邊就運用while來重複檢測輸入是否尚能被2、3、5整除，如果可以就將其整除後再檢查一次，直到不能在除2、3、5為止。

        程式碼如下：

def t():
    n = int(input())
    while n % 2 == 0:
        n //= 2
    while n % 3 == 0:
        n //= 3
    while n % 5 == 0:
        n //= 5
    if n == 1:
        print('ugly')
    else:
        print('beautiful')
        
t()

e315. NOIP2017 1.成绩

         三個輸入乘以固定的比率，算出最終答案，如果是使用python要小心浮點數運算預設是帶小數的資料，記得要取整數。

        以下附上完整程式：

try:
    while True:
        p,n,m = [int(i) for i in input().split()]
        print(int(p*0.2+n*0.3+m*0.5))
except:
    pass

APCS 2024.01 m931. 1. 遊戲選角

         考試中常常用到排序，只是往往不會只是單純排序，有些時候，會需要在排序的資料裡面，添加一些不必要排序的資料，就像這題，表面是針對戰鬥力排名，但輸出的時候是要輸出攻擊力與防禦力，所以基本上的做法就是依序將[戰鬥力、攻擊力、防禦力]當成一筆資料塞入陣列之中，透過sort指令，因為系統預設的sort指令會先依第一個欄位排序，如果第一個欄位相同就繼續比第二個，以此類推。

        完整程式如下：

n = int(input())
p = []
for i in range(n):
    q,m = [int(i) for i in input().split()]
    p.append([q**2 + m**2 , q , m])
p.sort()

print(p[-2][1] , p[-2][2])

i025. 真因數和 (小 n)

         沒有太過分的求因數，小心避開當輸入為1、找因數的迴圈終點記得開根號處理，很多神奇的技巧如6n+1,6n-1，找因數的時候一次間隔兩個數....技巧都不需用上。

        以下附上完整程式碼：

def t():
    n = int(input())
    if n == 1:
        print(0)
        return
    p = int(n**0.5) + 1
    
    total = 0
    for i in range(1,p):
        if n % i == 0:
            j = n//i
            if j == i or j == n:
                total += i
            else:
                total += i + j
    print(total)
    
t()

f327. 刪除欄位

         這題就是單純的16進制轉換題，如果同樣的題目，是十進制出題，那是絕對的送分題，以十進制來看，假設收到三個char(a,b,c)需要我們將它組成一個百位數數字，那麼程式作法拆解下來就是total = a - char(0) ，再來是total = total * 10 + b - char(0) ，最後是total = total * 10 + c - char(0) ，數學式子去理解就是total = a * 100 + b * 10 + c，那麼將同樣概念運用在這題就沒問題了。

        以下附上完整程式：

d = input().split()

ft,st = 0,0
f,s = d
for i in range(len(f)):
    ft = ft * 26 +  (ord(f[i]) - ord('A')+1) 
for i in range(len(s)):
    st = st * 26 +  (ord(s[i]) - ord('A')+1) 
print(st - ft + 1)

k740. 楊輝三角形

        這題是標準的DP問題，扣除每一行的頭跟尾(都是1)，每一行的資料都是由上一行的正上方與左上方提供。

        以下附上完整程式碼：

n = int(input())
d = [[1 for i in range(21)] for j in range(21)]

for i in range(1,n+1):
    for j in range(i):
        if j != 0 and j != i-1:
            d[i][j] = d[i-1][j] + d[i-1][j-1]
        print(d[i][j] , end = ' ')
    print()

m283. 螞蟻的擴散

         這是一題標準的DP題目，假設以dp[x][y]做為起點開始走，那麼從dp[x][y]走一步後，dp[x-1][y]跟dp[x][y-1],dp[x-1][y-1]這三個位置個會增加dp[x][y]/3的機率被走到，以此類推直到X或是Y軸為0，最後計算起點跟終點的比值即可。

        下列附上程式：

import math

def cal(x, y):
    # 初始化dp陣列
    dp = [[0] * 11 for _ in range(11)]
    
    # 設定起點的機率為1
    dp[x][y] = 1*3**(x+y)
    
    # 遞迴計算dp
    for i in range(x, 0, -1):
        for j in range(y, 0, -1):
            dp[i-1][j] += dp[i][j] / 3
            dp[i][j-1] += dp[i][j] / 3
            dp[i-1][j-1] += dp[i][j] / 3
    
    ans = int(dp[x][y] - dp[0][0])
    cc = math.gcd(int(ans), int(dp[x][y]))
    dp[x][y] //= cc
    ans //= cc
    print(str(ans) + "/" + str(dp[x][y]))
    # 將分數化簡
    '''common_factor = math.gcd(int(result), 81)
    result /= common_factor'''

try:
    while True:
        x,y = [int(i) for i in input().split()]
        cal(x,y)
except:
    pass

k862. 輩份比較

        假設B,C是A的祖先，D,E是A的子孫,F是E的子孫，如果我們先忽略輩分這件事情，單純從A點走到F，那就是一個單純的BFS就可以解決的事情，只要在BFS的基礎上，讓每個節點記錄自己的父輩與子孫輩的成員即可。

下列附上程式碼：

class Node:
    def __init__(self):
        self.father = []
        self.child = []
        self.dis = -99999999


s = set()
n = int(input())
d = {}
for i in range(n):
    c,f = input().split()
    if c not in d:
        d[c] = Node()
    if f not in d:
        d[f] = Node()
    d[c].father.append(f)
    d[f].child.append(c)
    
start,target = input().split()

d[start].dis = 0
p = [start]
keep = True
while keep:
    for i in p:
        for j in d[i].father:
            if j not in s:
                s.add(j)
                d[j].dis = d[i].dis-1
                p.append(j)
                if j == target:
                    keep = False
                    break
        for j in d[i].child:
            if j not in s:
                s.add(j)
                d[j].dis = d[i].dis+1
                p.append(j)
                if j == target:
                    keep = False
                    break
        if keep == False: break
print(d[target].dis)

m685. 三角形計數器

         辨別三角形相同的方式有很多，我們選其中一個方式來解題，假設兩個三角形，各三個邊由小到大分別是a,b,c  及  a1,b1,c1，如果a/b==a1/b1 and b/c == b1/c1 and c/a == c1/a1，那麼這兩個三角形及為相似三角形，最後用上set來濾掉重複的三角形即可。

n = int(input())
s = set()
for i in range(n):
    d = [int(i) for i in input().split()]
    d.sort()
    s.add(str(d[0]/d[1]) + str(d[1]/d[2]) + str(d[2]/d[0]))
print(len(s))

m702. 傑出校友票選活動

         題目要比對各個人名出現的次數，因為人名是字串，不方便直接用陣列做排序與索引，所以可以先放到map裡面去計次，記完之後再放回vector裡做排序即可。

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

int main()
{
    cin.tie(0) , cin.sync_with_stdio(0);
    int n,m;
    cin >> n >> m;
    map<string , int> t;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        t[s] += 1;
    }
    vector<pair<int , string>> v;
    for(auto it=t.begin(); it != t.end(); it++) {
        pair<int,string> p;
        p.first = it->second;
        p.second = it->first;
        v.push_back(p);
    }
    sort(v.begin() , v.end());
    for(int i = 0; i < m; i++) {
        cout << v[v.size()-1-i].second << " ";
    }
    cout << endl;

    return 0;
}

l960. 星期幾？

         題目明確給定正確的資料，將其放入清單中，再收取測資作比對即可。

h = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday']
s = input()
if s not in h:
    print('error')
else:
    print(h.index(s))

APCS 2024.01 m934. 4. 合併成本

        要計算最小合併成本，就需要用到DP，DP的精髓就是分而治之，假設今天只有3個資料要合併，-1,3,-5，那麼情形不外乎是(-1,(3,-5) ) 或是 ((-1, 3),-5)，從兩個之中找最小成本。如果這時候再增加一個資料如-1,3,-5,6那麼情形就是((-1,3,-5),6)或是((-1,3),(-5,6))或是(-1,(3,-5,6))之中找最小成本，我們可以發現，只要每次切割區間的左右邊界，直到找到1.左右邊界相同，代表沒有合併成本，2.左右邊界差一，那就是相鄰兩個合併，可以直接運算，3.這個左右邊界夾出來的最小成本已經算過，直接回傳資料。

        以下附上完整程式碼：

def check(left , right):
    if dp[left][right] != 9999999:
        return dp[left][right]
    if left == right: return 0
    elif left == right-1:
        return abs(d[left] - d[right])
    mm = 9999999
    for i in range(left , right):
        l,r = check(left , i) , check(i+1 , right)
        dp[left][right] = min(dp[left][right],abs((table[i+1] - table[left]) - (table[right+1] - table[i+1]))  + l+r)
        mm = min(mm,dp[left][right])
    return mm
        

n = int(input())
d = [int(i) for i in input().split()]
dp = [[9999999 for i in range(n)] for j in range(n)]
table = [0]
for i in d:
    table.append(table[-1] + i)

print(check(0,n-1))

APCS 2024.01 m932. 2. 蜜蜂觀察

         按照慣例，APCS的第二題就是考二維陣列的運用，特別是邊界的判別。解這題的時候如果你可以畫個圖，或是心中畫個圖的畫就會簡單許多。

        現實的資料

        但我們收到清單後，資料長成這樣s = ['TyuI','ABaB']。舉個例子，起點從A開始，假設先往右上走，從上圖來說會走到T，但從清單中的結構來說，位置只是往上跑而已，依照這樣的邏輯，依序將，六個方向對應到清單的變化整理出來，這題就沒有問題了。以下附上完整程式：

m,n,k = [int(i) for i in input().split()]
s = []
for i in range(m):
    s.append(input())
step = [int(i) for i in input().split()]

table = [[-1,0],[0,1],[1,1],[1,0],[0,-1],[-1,-1]]
x,y = 0,m-1

sets = set()
ans = ''
for i in step:
    yy,xx = table[i]
    if xx+x < 0 or xx+x >= n or yy+y < 0 or yy+y >= m: 
        ans += s[y][x]
        sets.add(s[y][x])
        continue
    y,x = yy+y,xx+x
    ans += s[y][x]
    sets.add(s[y][x])
print(ans)
print(len(sets))

        有問題歡迎留言，或email與我討論。

APCS 2024.01 m933. 3. 邏輯電路

        乍看之下，本來覺得可以直接硬解，所以沒多想便用了很多清單來解題，沒想到過程中發現要記錄的資訊量很大，寫著寫著程式越來越複雜，所幸從頭開始，運用自訂結構，將每個節點所需要的欄位明確定義出來，這題就會簡單許多。

        解題技巧運用到BFS再加上一些條件式判斷，依下圖為例：

        第0步的起點為g1,g2,g3,g4,g5，第一步的起點為g6,g7,g8,g9,第二步的起點為g6,g10,g11,第三步為g11，你會發現第一步的g6沒有馬上走到g12，這也是這題的重點之一，因為第一次走到g1->g6的時候，g6還算不出答案，它還在等待g7->g6，因為g6必須湊齊g1,g7才能得到輸出。

        以下附上完整程式：

class Node:
    def __init__(self):
        self.nexts = []#該節點是那些節點的輸入
        self.val = -1
        self.delay = 0
        self.gate = None
        self.ipt = []#那些節點是本節點的輸入

def t():
    pp,q,r,m = [int(i) for i in input().split()]
    p = [int(i) for i in input().split()]
    t = [int(i) for i in input().split()]
    nodes = []
    for i in range(pp+q+r):
        nodes.append(Node())
    for i in range(pp):
        nodes[i].val = p[i]
    for i in range(pp , pp+q):
        nodes[i].gate = t[i-pp]
    #print(nodes)
    
    for i in range(m):
        a,b = [int(i) for i in input().split()]
        a -= 1
        b -= 1
        nodes[a].nexts.append(b)
    
    p = [i for i in range(pp)]
    
    '''1 為 AND、2 為 OR、3 為 XOR、4 為 NO'''
    for i in p:
        if nodes[i].val == -1:continue
        for j in nodes[i].nexts:#i節點是j節點的輸入
            nodes[j].ipt.append(i)#j節點的輸入有添加i節點
            if nodes[j].gate == 4 and len(nodes[j].ipt) == 1:
                nodes[j].val = int(not nodes[nodes[j].ipt[0]].val)#j節點的值，是j的輸入的值的相反
                nodes[j].delay = nodes[nodes[j].ipt[0]].delay + 1
                p.append(j)
            elif nodes[j].gate != 4 and len(nodes[j].ipt) == 2:
                p1,p2 = nodes[nodes[j].ipt[0]] , nodes[nodes[j].ipt[1]]
                if nodes[j].gate == 1:
                    nodes[j].val = int(p1.val and p2.val)
                if nodes[j].gate == 2:
                    nodes[j].val = int(p1.val or p2.val)
                if nodes[j].gate == 3:
                    nodes[j].val = int(p1.val != p2.val)
                nodes[j].delay = max(p1.delay , p2.delay) + 1
                p.append(j)
    mm = 0
    for i in range(pp+q , pp+q+r):
        mm = max(nodes[nodes[i].ipt[0]].delay , mm)
    print(mm)
    for i in range(pp+q , pp+q+r):
        print(nodes[nodes[i].ipt[0]].val , end = ' ')
    print()
t()

        如果有問題，歡迎留言會email我。

e531: 10415 - Eb Alto Saxophone Player

UVA 10415

CPE 2020/12/22考題

解題心得：

每個音階都有對應的指法，如果欲彈奏下一個音階須按下的手指與上一個重複，則不用額外計算。

1.建立MAP來儲存每個音階要按的手指

2.建立一個狀態表(陣列)來儲存每個手指當前狀態(0沒按1按)，在建立一個記數表來記錄每個手指按下幾次。

3.每次讀到下一個音階時先去狀態表查閱當前手指狀態，如果該按而還沒按則按下(記數+1)。

4.依據MAP的資料把該放開的手指放開(狀態表)。

程式碼如下：

#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;

int main()
{
    cin.tie(0) , cin.sync_with_stdio(0);
    map<char , vector<int>> mc;
    mc['c'] = {0,0,1,1,1,0,0,1,1,1,1};
    mc['d'] = {0,0,1,1,1,0,0,1,1,1,0};
    mc['e'] = {0,0,1,1,1,0,0,1,1,0,0};
    mc['f'] = {0,0,1,1,1,0,0,1,0,0,0};
    mc['g'] = {0,0,1,1,1,0,0,0,0,0,0};
    mc['a'] = {0,0,1,1,0,0,0,0,0,0,0};
    mc['b'] = {0,0,1,0,0,0,0,0,0,0,0};
    mc['C'] = {0,0,0,1,0,0,0,0,0,0,0};
    mc['D'] = {0,1,1,1,1,0,0,1,1,1,0};
    mc['E'] = {0,1,1,1,1,0,0,1,1,0,0};
    mc['F'] = {0,1,1,1,1,0,0,1,0,0,0};
    mc['G'] = {0,1,1,1,1,0,0,0,0,0,0};
    mc['A'] = {0,1,1,1,0,0,0,0,0,0,0};
    mc['B'] = {0,1,1,0,0,0,0,0,0,0,0};
    int t;
    cin >> t;
    string s;
    getline(cin , s);
    while(t--){
        int finger[11] = {0};
        int fingerCount[11] = {0};
        getline(cin , s);
        for(int i = 0; i < s.length(); i++){
            if(mc.count(s[i]) == 0) continue;
            for(int j = 1; j < 11; j++) {
                if(mc[s[i]][j] == 1) {
                    if(finger[j] == 0) {
                        fingerCount[j]++;
                        finger[j] = 1;
                    }
                }
            }
            for(int k = 0; k <11; k++){
                finger[k] = mc[s[i]][k];
            }
        }
        
        for(int i = 1; i < 11 ;i++){
            cout << fingerCount[i] <<" ";
        }
        cout << "\n";
    }
    
    return 0;
}