結果

問題 No.2104 Multiply-Add
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:51:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,687 bytes
コンパイル時間 386 ms
コンパイル使用メモリ 82,328 KB
実行使用メモリ 54,464 KB
最終ジャッジ日時 2025-06-12 19:51:54
合計ジャッジ時間 5,438 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def readints():
    return list(map(int, sys.stdin.readline().split()))

def main():
    a, b, c, d = readints()
    
    if a == 0 and b == 0:
        if c == 0 and d == 0:
            print(0)
        else:
            print(-1)
        return
    
    g = math.gcd(a, b)
    g_target = math.gcd(c, d)
    if g != g_target:
        print(-1)
        return
    
    if a == c and b == d:
        print(0)
        return
    
    steps = []
    
    # Try two-step approach
    success = False
    
    # First adjust x to c
    if b != 0 and (c - a) % b == 0:
        k1 = (c - a) // b
        steps.append(('1', k1))
        new_x = c
        new_y = b
        if new_y != 0 and (d - new_y) % new_x == 0:
            k2 = (d - new_y) // new_x
            steps.append(('2', k2))
            success = True
    
    if not success:
        steps = []
        # Try adjusting y to d first
        if a != 0 and (d - b) % a == 0:
            k2 = (d - b) // a
            steps.append(('2', k2))
            new_y = d
            new_x = a
            if new_y != 0 and (c - new_x) % new_y == 0:
                k1 = (c - new_x) // new_y
                steps.append(('1', k1))
                success = True
    
    if success:
        print(len(steps))
        for t, k in steps:
            print(f"{t} {k}")
        return
    
    # Four-step approach inspired by the sample
    # Try to make x = a + k1*b, then y = b + k2*(a + k1*b)
    # Then x = (a + k1*b) + k3*(b + k2*(a + k1*b))
    # Then y = (b + k2*(a + k1*b)) + k4 * x_new
    # We need x_new = c and y_new = d
    
    steps = []
    x = a
    y = b
    
    # Find k1 such that x becomes something, then k2, etc.
    # This is a heuristic approach, not guaranteed to work
    found = False
    for k1 in [3, -2]:
        new_x = x + k1 * y
        steps.append(('1', k1))
        x = new_x
        for k2 in [1, -1]:
            new_y = y + k2 * x
            steps.append(('2', k2))
            y = new_y
            for k3 in [-2]:
                new_x = x + k3 * y
                steps.append(('1', k3))
                x = new_x
                for k4 in [-1]:
                    new_y = y + k4 * x
                    steps.append(('2', k4))
                    y = new_y
                    if x == c and y == d:
                        found = True
                        break
                if found:
                    break
            if found:
                break
        if found:
            break
    
    if found:
        print(len(steps))
        for t, k in steps:
            print(f"{t} {k}")
        return
    
    print(-1)

if __name__ == '__main__':
    main()
0