結果

問題 No.3320 yiwiwiy
コンテスト
ユーザー みうね
提出日時 2025-10-06 09:54:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,868 bytes
コンパイル時間 428 ms
コンパイル使用メモリ 82,588 KB
実行使用メモリ 62,008 KB
最終ジャッジ日時 2025-10-31 18:53:15
合計ジャッジ時間 3,942 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 72
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

def compute_P_from_layout(a, b, center_seq, d, e):
    """
    center_seq: list of chars 'i' or 'w'
    a,b,d,e: counts for y(left), i(left), i(right), y(right)
    Return exact P for the full string: y^a i^b + center_seq + i^d y^e
    """
    n = len(center_seq)
    pref_i = [0] * (n+1)
    for i,ch in enumerate(center_seq):
        pref_i[i+1] = pref_i[i] + (1 if ch == 'i' else 0)
    total_i_inside = pref_i[n]
    total = 0
    for pos,ch in enumerate(center_seq):
        if ch == 'w':
            i_before = b + pref_i[pos]
            i_after = d + (total_i_inside - pref_i[pos+1])
            total += i_before * i_after
    P = a * e * total
    return P

def build_center_sequence(i_b, w_b, W_rem, side):
    """
    Build center sequence where:
      - i_b, w_b are counts used in alternating block (may be 0)
      - W_rem extra w's placed either 'left' or 'right' of that alternating block
    Returns list of chars.
    """
    center = []
    # build alternating block starting with 'i' if i_b>0
    ic = i_b
    wc = w_b
    turn_i = True
    # if both ic and wc are zero, alternating block is empty
    while ic > 0 or wc > 0:
        if turn_i:
            if ic > 0:
                center.append('i'); ic -= 1
            else:
                turn_i = not turn_i
                continue
        else:
            if wc > 0:
                center.append('w'); wc -= 1
            else:
                turn_i = not turn_i
                continue
        turn_i = not turn_i
    # place extra w's on chosen side
    if W_rem > 0:
        if side == 'left':
            center = ['w'] * W_rem + center
        else:
            center = center + ['w'] * W_rem
    return center

def best_string_for_case(Y, I, W, A, B):
    # candidates for a (left y). we try floor/ceil
    a_candidates = [Y // 2]
    other = Y - (Y // 2)
    if other != a_candidates[0]:
        a_candidates.append(other)
    a_candidates = sorted(set(a_candidates))

    best_val = None
    best_S = None

    # Always consider the "no alternating block" case (q = 0 but i_b=0,w_b=0)
    # Also consider q >= 1 up to min(I-2, W-1) where alternating block is possible.
    q_max_possible = max(-1, min(I - 2, W - 1))
    q_values = [0]
    if q_max_possible >= 1:
        q_values.extend(range(1, q_max_possible + 1))

    for q in q_values:
        if q == 0:
            i_b = 0
            w_b = 0
            q_value = 0
        else:
            i_b = q + 2
            w_b = q + 1
            q_value = q
            if i_b > I or w_b > W:
                continue

        I_rem = I - i_b
        W_rem = W - w_b

        # candidate b splits for I_rem: try center and neighbors
        b_base = I_rem // 2
        b_candidates = set([b_base, I_rem - b_base])
        for delta in (-1, 1):
            v = b_base + delta
            if 0 <= v <= I_rem:
                b_candidates.add(v)

        # also include extremes (all left or all right) to be safe
        b_candidates.add(0)
        b_candidates.add(I_rem)

        for b in sorted(b_candidates):
            d = I_rem - b
            for a in a_candidates:
                e = Y - a
                for side in ('left', 'right'):
                    center_seq = build_center_sequence(i_b, w_b, W_rem, side)
                    P = compute_P_from_layout(a, b, center_seq, d, e)
                    val = A * P + B * q_value
                    if best_val is None or val > best_val:
                        # construct actual string S = y^a + i^b + center_seq + i^d + y^e
                        S = []
                        if a > 0:
                            S.append('y' * a)
                        if b > 0:
                            S.append('i' * b)
                        if center_seq:
                            S.append(''.join(center_seq))
                        if d > 0:
                            S.append('i' * d)
                        if e > 0:
                            S.append('y' * e)
                        S_full = ''.join(S)
                        # Sanity: verify counts match
                        if S_full.count('y') != Y or S_full.count('i') != I or S_full.count('w') != W:
                            # this should not happen, but skip if it does
                            continue
                        best_val = val
                        best_S = S_full
    # As a fallback (shouldn't be necessary), if best_S is still None, return a default arrangement using all letters:
    if best_S is None:
        best_S = 'y'*Y + 'i'*I + 'w'*W
    return best_S

def solve():
    T = int(input().strip())
    out = []
    for _ in range(T):
        Y,I,W,A,B = map(int, input().split())
        s = best_string_for_case(Y,I,W,A,B)
        out.append(s)
    print("\n".join(out))

if __name__ == "__main__":
    solve()
0