PDD 03/12 机试题

"""
1. 压缩字符串解码，aaabbc可以压缩为3a2b1c，现在给了压缩字符串问原字符串是啥。模拟一下就好了
"""
s = input()
i = 0
n = len(s)
res = ''
while i < n:
    j = i
    while j < n and s[j].isdigit():
        j += 1
    res += s[j]*int(s[i:j])
    i = j + 1
print(res)

"""
2. 游戏有t个独立关卡，每个关卡里有n个敌人，你可以发射两种炮弹一种能够直接秒杀一个敌人。一种能发射两个子弹飞别扣两个敌人1滴血（两个飞弹不能都命中同一敌人），问每一关最少需要发射几次？ （血量为1的，一起用双发的划算，大于等于2的直接单发）
"""
t, n = map(int, input().split())
res = []
for i in range(t):
    a = list(map(int, input().split()))
    eq1 = 0
    for x in a:
        if x == 1:
            eq1 += 1
    eq2 = len(a) - eq1
    res.append((eq1+1)//2 + eq2)
for x in res:
    print(x)



"""
3. 有A B C三种方案，给定每种方案的成本和容纳的人数上限，以及n个人和每个人的若干个意向，问是否能够满足所有人的意向，如果能，最低成本是多少，如果不能，最多满足的人数是多少？ 暴力法，先选最便宜的，超过上限就往贵的转（90%）
"""
def s2nums(s):
    res = []
    if 'A' in s:
        res.append(0)
    if 'B' in s:
        res.append(1)
    if 'C' in s:
        res.append(2)
    return res


n = int(input())
a = [s2nums(input()) for i in range(n)]
b = []
# limit coin id
for i in range(3):
    b.append(list(map(int, input().split())) + [len(b)])
# 优先选价格低的
rank = sorted(b[:], key=lambda x: x[1])
allo = [-1]*n

for r in range(3):
    for i in range(n):
        if rank[r][-1] in a[i] and allo[i] == -1:
            # cnt[rank[r][-1]] += 1
            allo[i] = rank[r][-1]
    sm = 0
    for x in allo:
        if x == rank[r][-1]:
            sm += 1
    if sm > rank[r][0]:
        for k in [1, 2]:
            if r + k > 2:
                break
            nr = r + k
            for i in range(n):
                if sm <= rank[r][0]:
                    break
                # send to another
                if rank[nr][-1] in a[i] and allo[i] == rank[r][-1]:
                    allo[i] = rank[nr][-1]
                    # cnt[rank[nr][-1]] += 1
                    sm -= 1

# check
if sum(x == 0 for x in allo) <= b[0][0] and sum(x == 1 for x in allo) <= b[1][0] and sum(x == 2 for x in allo) <= b[2][0]:
    print("YES")
    sm = 0
    for x in allo:
        sm += b[x][1]
    print(sm)
else:
    print("NO")
    # 优先选容量小的
    rank = sorted(b[:], key=lambda x: x[0])
    allo = [-1] * n

    for r in range(3):
        for i in range(n):
            if rank[r][-1] in a[i] and allo[i] == -1:
                # cnt[rank[r][-1]] += 1
                allo[i] = rank[r][-1]
        sm = 0
        for x in allo:
            if x == rank[r][-1]:
                sm += 1
        if sm > rank[r][0]:
            for k in [1, 2]:
                if r + k > 2:
                    break
                nr = r + k
                for i in range(n):
                    if sm <= rank[r][0]:
                        break
                    # send to another
                    if rank[nr][-1] in a[i] and allo[i] == rank[r][-1]:
                        allo[i] = rank[nr][-1]
                        # cnt[rank[nr][-1]] += 1
                        sm -= 1

    print(min(b[0][0], sum(x == 0 for x in allo)) + min(b[1][0], sum(x == 1 for x in allo)) + min(b[2][0], sum(x == 2 for x in allo)))

"""
4 给定一个长为n的序列，求前i个数的中位数和平均值（i取1-n），结果四舍五入。 对顶堆求中位数，只过了40%，有大佬看看问题在哪？不知道是不是精度出错了导致取整有问题。
"""
import heapq
class WrapLow:
    def __init__(self, x):
        self.x = x

    def __lt__(self, other):
        return self.x > other.x

# python 默认小根堆，大根堆直接对值取负数也行，但是习惯用wrapper了
class WrapHigh:
    def __init__(self, x):
        self.x = x

    def __lt__(self, other):
        return self.x < other.x


n = int(input())
a = list(map(int, input().split()))
s = 0
mean = []
median = []
hp_low, hp_high = [WrapLow(-1e9)], [WrapHigh(1e9)]


for i in range(n):
    s += a[i]
    mean.append(round(s / (i + 1) + 0.1))
    if a[i] <= hp_high[0].x:
        heapq.heappush(hp_low, WrapLow(a[i]))
    else:
        heapq.heappush(hp_high, WrapHigh(a[i]))

    while len(hp_low) - len(hp_high) > 1:
        x = heapq.heappop(hp_low).x
        heapq.heappush(hp_high, WrapHigh(x))

    while len(hp_high) - len(hp_low) > 0:
        x = heapq.heappop(hp_high).x
        heapq.heappush(hp_low, WrapLow(x))

    if (i+1) & 1:
        median.append(hp_low[0].x)
    else:
        median.append(int(round(0.1 + (hp_high[0].x + hp_low[0].x) / 2)))

print(' '.join(map(str, mean)))
print(' '.join(map(str, median)))