ZeroJudge 解題筆記：k514. P2.解藥 (Medicine)

作者：王一哲
日期：2025年4月29日



ZeroJudge 題目連結：k514. P2.解藥 (Medicine)

解題想法

每組測資只有單筆。先找最小的比例數值，以這種材料的量為基準，檢查外三項材料的比例。

Python 程式碼

使用時間約為 20 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    ratio = list(map(int, line.split()))  # 4 㮔材料的比例
    imin = min(ratio)  # 最小的比例數值
    pmin = ratio.index(imin)  # 最小的比例索引值
    n = int(input())  # 每種材料各有 n 小包
    abcd = [list(map(int, input().split())) for _ in range(4)]  # 每小包的份量
    solve = False  # 是否有解
    if pmin == 0:  # 以第 0 種材料為基準
        for v in abcd[pmin]:  # 依序讀取第 0 種材料每小包的分量，檢查另外 3 項材料的比例
            if v*ratio[1] in abcd[1] and v*ratio[2] in abcd[2] and v*ratio[3] in abcd[3]:
                print(f"{v:d} {v*ratio[1]:d} {v*ratio[2]:d} {v*ratio[3]:d}")
                solve = True; break
    elif pmin == 1:  # 以第 1 種材料為基準
        for v in abcd[pmin]:  # 依序讀取第 1 種材料每小包的分量，檢查另外 3 項材料的比例
            if v*ratio[0] in abcd[0] and v*ratio[2] in abcd[2] and v*ratio[3] in abcd[3]:
                print(f"{v*ratio[0]:d} {v:d} {v*ratio[2]:d} {v*ratio[3]:d}")
                solve = True; break
    elif pmin == 2:  # 以第 2 種材料為基準
        for v in abcd[pmin]:  # 依序讀取第 2 種材料每小包的分量，檢查另外 3 項材料的比例
            if v*ratio[0] in abcd[0] and v*ratio[1] in abcd[1] and v*ratio[3] in abcd[3]:
                print(f"{v*ratio[0]:d} {v*ratio[1]:d} {v:d} {v*ratio[3]:d}")
                solve = True; break
    else:  # 以第 3 種材料為基準
        for v in abcd[pmin]:  # 依序讀取第 3 種材料每小包的分量，檢查另外 3 項材料的比例
            if v*ratio[0] in abcd[0] and v*ratio[1] in abcd[1] and v*ratio[2] in abcd[2]:
                print(f"{v*ratio[0]:d} {v*ratio[1]:d} {v*ratio[2]:d} {v:d}")
                solve = True; break
    if not solve: print(-1)  # 無解，印出 -1

C++ 程式碼

使用時間約為 2 ms，記憶體約為 284 kB，通過測試。

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    int ratio[4];  // 4 㮔材料的比例
    for(int i=0; i<4; i++) scanf("%d", &ratio[i]);
    int pmin = min_element(ratio, ratio+4) - ratio;  // 最小的比例索引值
    int n; scanf("%d", &n);  // 每種材料各有 n 小包
    set<int> a, b, c, d;  // 每小包的份量
    for(int i=0, v; i<n; i++) {
        scanf("%d", &v); a.insert(v);
    }
    for(int i=0, v; i<n; i++) {
        scanf("%d", &v); b.insert(v);
    }
    for(int i=0, v; i<n; i++) {
        scanf("%d", &v); c.insert(v);
    }
    for(int i=0, v; i<n; i++) {
        scanf("%d", &v); d.insert(v);
    }
    bool solve = false;  // 是否有解
    if (pmin == 0) {  // 以第 0 種材料為基準
        for(auto v : a) {  // 讀取第 0 種材料每小包的分量，檢查另外 3 項材料的比例
            if (b.count(v*ratio[1]) == 1 && c.count(v*ratio[2]) == 1 && d.count(v*ratio[3]) == 1) {
                printf("%d %d %d %d\n", v, v*ratio[1], v*ratio[2], v*ratio[3]);
                solve = true; break;
            }
        }
    } else if (pmin == 1) {  // 以第 1 種材料為基準
        for(auto v : b) {  // 讀取第 1 種材料每小包的分量，檢查另外 3 項材料的比例
            if (a.count(v*ratio[0]) == 1 && c.count(v*ratio[2]) == 1 && d.count(v*ratio[3]) == 1) {
                printf("%d %d %d %d\n", v*ratio[0], v, v*ratio[2], v*ratio[3]);
                solve = true; break;
            }
        }
    } else if (pmin == 2) {  // 以第 2 種材料為基準
        for(auto v : c) {  // 讀取第 2 種材料每小包的分量，檢查另外 3 項材料的比例
            if (a.count(v*ratio[0]) == 1 && b.count(v*ratio[1]) == 1 && d.count(v*ratio[3]) == 1) {
                printf("%d %d %d %d\n", v*ratio[0], v*ratio[1], v, v*ratio[3]);
                solve = true; break;
            }
        }
    } else { // 以第 3 種材料為基準
        for(auto v : d) {  // 讀取第 3 種材料每小包的分量，檢查另外 3 項材料的比例
            if (a.count(v*ratio[0]) == 1 && b.count(v*ratio[1]) == 1 && c.count(v*ratio[2]) == 1) {
                printf("%d %d %d %d\n", v*ratio[0], v*ratio[1], v*ratio[2], v);
                solve = true; break;
            }
        }
    }
    if (!solve) printf("-1\n");  // 無解，印出 -1
    return 0;
}