熱門文章

2025年9月6日 星期六

ZeroJudge 解題筆記:d623. 反方陣

作者:王一哲
日期:2025年9月6日


ZeroJudge 題目連結:d623. 反方陣

解題想法


假設矩陣 $$ M = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} $$ 其行列式值 $det(M) = ad - bc$。如果 $det(M) \neq 0$,$M$ 是可逆的,其反矩陣 $$ M^{-1} = \frac{1}{det(M)} \begin{bmatrix} d & -b \\ -c & a \\ \end{bmatrix} $$ 另外要注意,題目的說明是4個0表示結束實際測資以一個零表示結束

Python 程式碼


使用時間約為 28 ms,記憶體約為 3.3 MB,通過測試。
while True:
    line = list(map(int, input().split()))
    if len(line) == 1 and line[0] == 0: break  # 只有一個 0,中止迴圈
    a, b = line  # 方陣 [[a, b], [c, d]]
    c, d = map(int, input().split())
    det = a*d - b*c  # 行列式值
    if det == 0:  # 沒有反方陣
        print("cheat!")
    else:  # 反方陣 (1/det)*[[d, -b], [-c, a]]
        print(f"{d/det:.5f} {-b/det:.5f}")
        print(f"{-c/det:.5f} {a/det:.5f}")

使用時間約為 24 ms,記憶體約為 3.6 MB,通過測試。
import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    if lines[idx].strip() == "0": break  # 只有一個 0,中止迴圈
    a, b = map(int, lines[idx].split())  # 方陣 [[a, b], [c, d]]
    idx += 1
    c, d = map(int, lines[idx].split())
    idx += 1
    det = a*d - b*c  # 行列式值
    if det == 0:  # 沒有反方陣
        result.append("cheat!\n")
    else:  # 反方陣 (1/det)*[[d, -b], [-c, a]]
        result.append(f"{d/det:.5f} {-b/det:.5f}\n")
        result.append(f"{-c/det:.5f} {a/det:.5f}\n")
sys.stdout.write("".join(result))


C++ 程式碼


使用時間約為 5 ms,記憶體約為 376 kB,通過測試。
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; stringstream ss;  // 暫存資料用的字串 s,容器 ss
    while(getline(cin, s)) {  // 讀取整行資料直到沒有資料為止
        if (s.size() == 1 && s == "0") break;  // 如果整行只有一個 0,中止迴圈
        ss.clear(); ss << s;  // 清空 ss,將 s 存入 ss
        int a, b, c, d;  // 方陣 [[a, b], [c, d]]
        ss >> s; a = stoi(s);  // 資料存入 a, b
        ss >> s; b = stoi(s);
        getline(cin, s);  // 再讀取一行
        ss.clear(); ss << s;  // 清空 ss,將 s 存入 ss
        ss >> s; c = stoi(s);  // 資料存入 c, d
        ss >> s; d = stoi(s);
        int det = a*d - c*b;  // 行列式值
        if (det == 0) {  // 沒有反方陣
            cout << "cheat!\n";
        } else {  // 反方陣 (1/det)*[[d, -b], [-c, a]]
            cout << fixed << setprecision(5) << 1.0*d/det << " " << -1.0*b/det << "\n";
            cout << fixed << setprecision(5) << -1.0*c/det << " " << 1.0*a/det << "\n";
        }
    }
    return 0;
}

上面的寫法太複雜了,這個寫法比較好,使用時間約為 2 ms,記憶體約為 68 kB,通過測試。
#include <cstdio>
using namespace std;

int main() {
    int arr[4], idx = 0, v;
    while(scanf("%d", &v) != EOF) {
        arr[idx] = v;
        idx++;
        if (idx == 4) {  // 讀完一組矩陣資料
            int det = arr[0]*arr[3] - arr[2]*arr[1];  // 行列式值
            if (det == 0) {  // 沒有反方陣
                puts("cheat!\n");
            } else {  // 反方陣 (1/det)*[[d, -b], [-c, a]]
                printf("%.5f %.5f\n", 1.0*arr[3]/det, -1.0*arr[1]/det);
                printf("%.5f %.5f\n", -1.0*arr[2]/det, 1.0*arr[0]/det);
            }
            idx = 0;  // 歸零
        }
    }
    return 0;
}


沒有留言:

張貼留言