Đề thi HSG môn Tin học (Đề thi thử)

# Đọc dữ liệu từ file input
with open('AMULB.INP', 'r') as file:
    a, b, c = map(int, file.readline().split())

# Tìm hai số lớn nhất
max1 = max(a, b, c)
if max1 == a:
    max2 = max(b, c)
elif max1 == b:
    max2 = max(a, c)
else:
    max2 = max(a, b)

# Tính tích lớn nhất
product = max1 * max2

# Ghi kết quả ra file output
with open('AMULB.OUT', 'w') as file:
    file.write(str(product))

# Đọc dữ liệu từ file input
with open('AMULB.INP', 'r') as file:
    a, b, c = map(int, file.readline().split())

# Sắp xếp các số giảm dần
numbers = sorted([a, b, c], reverse=True)

# Lấy hai số đầu tiên
max1, max2 = numbers[:2]

# Tính tích lớn nhất
product = max1 * max2

# Ghi kết quả ra file output
with open('AMULB.OUT', 'w') as file:
    file.write(str(product))

# Đọc dữ liệu từ file input
with open('BDIVMN.INP', 'r') as file:
    N, M = map(int, file.readline().split())

# Hàm đếm số lượng ước nguyên dương
def count_divisors(num):
    count = 0
    for i in range(1, int(num**0.5) + 1):
        if num % i == 0:
            count += 1
            # Nếu hai ước khác nhau thì cộng 2 vào count
            if num // i != i:
                count += 1
    return count

# Đếm số lượng ước cho N và M
count_N = count_divisors(N)
count_M = count_divisors(M)

# So sánh và xác định người thắng cuộc
winner = ""
if count_N > count_M:
    winner = "John"
    max_divisors = count_N
elif count_N < count_M:
    winner = "Jame"
    max_divisors = count_M
else:
    winner = "EQUAL"
    max_divisors = count_N  # hoặc count_M vì chúng bằng nhau

# Ghi kết quả ra file output
with open('BDIVMN.OUT', 'w') as file:
    file.write(f"{winner} {max_divisors}")

# Đọc dữ liệu từ file input
with open('CPRIMED.INP', 'r') as file:
    a, b, c, d = map(int, file.readline().split())

# Hàm kiểm tra số nguyên tố
def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

# Hàm đếm số lượng số nguyên tố trong đoạn [start, end]
def count_primes(start, end):
    count = 0
    for num in range(start, end + 1):
        if is_prime(num):
            count += 1
    return count

# Đếm số lượng số nguyên tố cho a, b và c, d
count_John = count_primes(a, b)
count_Jame = count_primes(c, d)

# So sánh và xác định người thắng cuộc
winner = ""
if count_John > count_Jame:
    winner = "John"
    max_primes = count_John
elif count_John < count_Jame:
    winner = "Jame"
    max_primes = count_Jame
else:
    winner = "EQUAL"
    max_primes = count_John  # hoặc count_Jame vì chúng bằng nhau

# Ghi kết quả ra file output
with open('CPRIMED.OUT', 'w') as file:
    file.write(f"{winner} {max_primes}")

# Đọc dữ liệu từ file input
with open('DCOUNTST.INP', 'r') as file:
    S1 = file.readline().strip()
    S2 = file.readline().strip()

# Hàm đếm số lần xuất hiện của xâu trong một xâu
def count_occurrences(main_str, sub_str):
    count = 0
    start = 0
    while start < len(main_str):
        start = main_str.find(sub_str, start)
        if start == -1:
            break
        count += 1
        start += 1
    return count

# Đếm số lần xuất hiện của S2 trong S1 và ngược lại
count_S1_in_S2 = count_occurrences(S2, S1)
count_S2_in_S1 = count_occurrences(S1, S2)

# So sánh và xác định người thắng cuộc
winner = ""
max_occurrences = 0

if count_S1_in_S2 > count_S2_in_S1:
    winner = "John"
    max_occurrences = count_S1_in_S2
elif count_S1_in_S2 < count_S2_in_S1:
    winner = "Jame"
    max_occurrences = count_S2_in_S1
else:
    winner = "EQUAL"
    max_occurrences = count_S1_in_S2  # hoặc count_S2_in_S1 vì chúng bằng nhau

# Ghi kết quả ra file output
with open('DCOUNTST.OUT', 'w') as file:
    file.write(f"{winner} {max_occurrences}")

def find_min_diff_partition(arr):
    n = len(arr)
    total = sum(arr)

    # Tạo một mảng boolean để lưu trữ các cách chia quà
    dp = [[False] * (total // 2 + 1) for _ in range(n + 1)]
    
    # Khởi tạo trường hợp cơ bản
    for i in range(n + 1):
        dp[i][0] = True

    # Tìm cách chia quà
    for i in range(1, n + 1):
        for j in range(1, total // 2 + 1):
            dp[i][j] = dp[i - 1][j]
            if arr[i - 1] <= j:
                dp[i][j] |= dp[i - 1][j - arr[i - 1]]

    # Tìm độ chênh lệch nhỏ nhất
    diff = float('inf')
    for j in range(total // 2, -1, -1):
        if dp[n][j]:
            diff = total - 2 * j
            break

    return diff

def print_partition(arr, diff):
    n = len(arr)
    total = sum(arr)
    target_sum = (total - diff) // 2

    # Tìm cách chia quà
    subset = []
    i, j = n, target_sum
    while i > 0 and j > 0:
        if not dp[i - 1][j]:
            subset.append(i - 1)
            j -= arr[i - 1]
        i -= 1

    # In kết quả ra file output
    with open('EGIFTF.OUT', 'w') as file:
        file.write(f"{len(subset)} {diff}\n")
        for idx in reversed(subset):
            file.write(f"{idx + 1}\n")

# Đọc dữ liệu từ file input
with open('EGIFTF.INP', 'r') as file:
    N = int(file.readline())
    gifts = list(map(int, file.readline().split()))

# Gọi hàm để tìm và in kết quả ra file output
diff = find_min_diff_partition(gifts)
print_partition(gifts, diff)

def find_min_diff_partition(arr):
    n = len(arr)
    total = sum(arr)

    # Khởi tạo một mảng 2D để lưu trữ trạng thái bitset
    dp = [[0] * (total // 2 + 1) for _ in range(n + 1)]

    # Tìm cách chia quà
    for i in range(1, n + 1):
        for j in range(total // 2 + 1):
            dp[i][j] = dp[i - 1][j]
            if arr[i - 1] <= j:
                dp[i][j] |= dp[i - 1][j - arr[i - 1]] | (1 << (i - 1))

    # Tìm độ chênh lệch nhỏ nhất
    diff = float('inf')
    for j in range(total // 2, -1, -1):
        if dp[n][j]:
            diff = total - 2 * j
            break

    return diff, dp

def print_partition(arr, diff, dp):
    n = len(arr)
    total = sum(arr)
    target_sum = (total - diff) // 2

    # Tìm cách chia quà
    subset = []
    i, j = n, target_sum
    while i > 0 and j > 0:
        if (dp[i][j] & (1 << (i - 1))) != 0:
            subset.append(i - 1)
            j -= arr[i - 1]
        i -= 1

    # In kết quả ra file output
    with open('EGIFTF.OUT', 'w') as file:
        file.write(f"{len(subset)} {diff}\n")
        for idx in reversed(subset):
            file.write(f"{idx + 1}\n")

# Đọc dữ liệu từ file input
with open('EGIFTF.INP', 'r') as file:
    N = int(file.readline())
    gifts = list(map(int, file.readline().split()))

# Gọi hàm để tìm và in kết quả ra file output
diff, dp = find_min_diff_partition(gifts)
print_partition(gifts, diff, dp)