카테고리: swea

test_case = int(input())

def chk_test():
    chk_a_list = [0] * k
    chk_b_list = [1] * k

    for w_i in range(w):
        is_success = False

        for d_i in range(d - k + 1):
            cur_chk = [film[tmp_i][w_i] for tmp_i in range(d_i, d_i + k)]
            if cur_chk == chk_a_list or cur_chk == chk_b_list:
                is_success = True
                break
        if not is_success:
            return False
    return True


def test_film(film, depth=0, cnt_inject=0, chk_list=[]):
    global min_inject
    
    if cnt_inject >= min_inject:
        return

    if chk_test():
        min_inject = min(min_inject, cnt_inject)
        return

    if depth >= d:
        return
    
    origin_membrane = film[depth][:]

    # 현재 층을 그대로
    test_film(film, depth + 1, cnt_inject)

    # 현재 층을 a로
    film[depth] = inject_a
    test_film(film, depth + 1, cnt_inject + 1)
    film[depth] = origin_membrane

    # 현재 층을 b로
    film[depth] = inject_b
    test_film(film, depth + 1, cnt_inject + 1)
    film[depth] = origin_membrane

for t in range(test_case):
    d, w, k = map(int, input().split())

    film = [list(map(int, input().split())) for _ in range(d)]
    
    inject_a = [0] * w
    inject_b = [1] * w

    min_inject = float('inf')

    test_film(film)
    print(f"#{t + 1} {min_inject}")

def max_subset_sum(arr):
    dp = [[0, 0] for _ in range(c + 1)]

    for num in arr:
        for j in range(c, num - 1, -1):
            if dp[j - num][0] + num > c:
                continue
            next_sq_value = dp[j - num][1] + num ** 2
            if next_sq_value > dp[j][1]:
                dp[j][0] = dp[j - num][0] + num
                dp[j][1] = next_sq_value
    _, max_sum = max(dp, key=lambda x: x[1])
    return max_sum

test_case = int(input())

for t in range(test_case):
    n, m, c = map(int, input().split())
    honey_map = [list(map(int, input().split())) for _ in range(n)]
    total_max = 0

    for fst_i in range(n):
        for fst_j in range(n - m + 1):

            fst_max = max_subset_sum(honey_map[fst_i][fst_j:fst_j + m])

            for snd_i in range(n):
                start = 0
                if snd_i == fst_i:
                    start = fst_j + m
                for snd_j in range(start, n - m + 1):
                    snd_max = max_subset_sum(honey_map[snd_i][snd_j:snd_j + m])

                    total_max = max(total_max, fst_max + snd_max)

    print(f"#{t + 1} {total_max}")

# 계산

def calculate(num1, num2, operator):

    if operator == '+':
        num1 += num2
    elif operator == '-':
        num1 -= num2
    elif operator == '*':
        num1 *= num2
    elif operator == '/':
        num1 = int(num1 / num2)
    return num1

# 수식 완성
def search_expression(i, result):
    if i == n:
        global max_num, min_num
        max_num = max(max_num, result)
        min_num = min(min_num, result)
        return

    for operator in operators:
        if operator_dict[operator] > 0:
            operator_dict[operator] -= 1
            search_expression(i + 1, calculate(result, nums[i+1], operator))
            operator_dict[operator] += 1



test_case = int(input())

for t in range(test_case):
    n = int(input()) - 1
    operators = ['+', '-', '*', '/']
    operator_dict = {operator: cnt for operator, cnt in zip(operators, map(int, input().split()))}

    nums = list(map(int, input().split()))

    max_num = float('-inf')
    min_num = float('inf')
    result_dict = {}
    visited = []

    search_expression(0, nums[0])

    print(f"#{t + 1} {max_num - min_num}")

test_case = int(input())

def search_recipe(index_list, n):
    if n == 1 :
        return [[i] for i in index_list]
    result = []
    for i in range(len(index_list) - 1):
        for j in search_recipe(index_list[i+1:], n - 1):
            result.append([index_list[i]] + j)
    
    return result


for t in range(test_case):
    n = int(input())
    min_diff = float('inf')

    recipe = [list(map(int, input().split())) for _ in range(n)]
    
    index_set = set(range(n))

    comb_list = [[0] + c for c in search_recipe(list(range(1, n)), n // 2 - 1)]

    for comb in comb_list:
        comb2 = list(index_set - set(comb))
        food1, food2 = 0, 0

        for i_idx, (i1, i2) in enumerate(zip(comb, comb2)):
            for j1, j2 in zip(comb[i_idx + 1:], comb2[i_idx + 1:]):
                food1 += recipe[i1][j1] + recipe[j1][i1]
                food2 += recipe[i2][j2] + recipe[j2][i2]
        min_diff = min(min_diff, abs(food1 - food2))

    print(f"#{t + 1} {min_diff}")

test_case = int(input())


# 제한 칼로리 내에서 최대의 맛
def search_best(hamburgers, sum_cal=0, sum_score=0):
    global max_score
    max_score = max(max_score, sum_score)

    for i, (score, cal) in enumerate(hamburgers):
        if sum_cal + cal > l:
            continue
        search_best(hamburgers[i + 1:], sum_cal + cal, sum_score + score)


for t in range(test_case):
    n, l = map(int, input().split())

    hamburgers = [list(map(int, input().split())) for _ in range(n)]

    max_score = 0

    search_best(hamburgers)

    print(f"#{t + 1} {max_score}")