Imgcity

Appearance

Imgcity✍️ Online Judge 題解Advent of Code202413

13 ​

https://adventofcode.com/2024/day/13

Prob ​

給定 a1,b1,c1,a2,b2,c2∈N

在這條件下，找 3x+y 的最小值

{a1x+b1y=c1a2x+b2y=c2x,y∈N

解法 ​

(假解)

解完聯立方程式時，理論上是要判斷 Δ=0 是可以去繼續確認其他事情的，但是看起來測試資料沒有這部分 😆

python
import sys

button_a_line = ''
button_b_line = ''
prize_line = ''

ans = 0
for line in sys.stdin:
    line = line.strip()
    if line.startswith('Button A'):
        button_a_line = line.removeprefix('Button A: ')
        continue
    elif line.startswith('Button B'):
        button_b_line = line.removeprefix('Button B: ')
        continue
    elif not line.startswith('Prize'):
        continue

    prize_line = line.removeprefix('Prize: ')

    a1, b1 = map(int, button_a_line.replace(
        'X+', '').replace('Y+', '').split(','))
    a2, b2 = map(int, button_b_line.replace(
        'X+', '').replace('Y+', '').split(','))
    x0, y0 = map(int, prize_line.replace(
        'X=', '').replace('Y=', '').split(','))
    a2, b1 = b1, a2

    x0 += 10000000000000
    y0 += 10000000000000

    '''
        a1x + b1y = x0
        a2x + b2y = y0
    '''
    print(a1, b1)
    print(a2, b2)

    det = a1*b2 - b1*a2
    if det == 0:
        continue

    x = x0*b2 - y0*b1
    if x % det != 0:
        continue
    x //= det

    y = - (x0*a2 - y0*a1)
    if y % det != 0:
        continue
    y //= det
    print(x, y)

    if x >= 0 and y >= 0:
        ans += 3*x + y

print(ans)

Changelog

Just observe 👀