usaco-3.2.4 饲料调配

题目描述

三种混合饲料调配目标饲料：求非负整数份数 $a,b,c$ 与正整数 $k$ 使 $aF_1+bF_2+cF_3=kT$ 且 $a+b+c$ 最小，无解输出 NONE（份数均小于 100）。

思路

按 $s=a+b+c$ 从 0 到 297 递增枚举、同 $s$ 内按 $a,b$ 递增检查，对每组候选由 $T$ 首个非零位定出倍数 $k$ ，回代验证 $M=kT$ 且 $k\ge1$ ，首个命中即最小。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 05:22
# update_at: 2026-10-01 05:22

import sys

PARTS = 3                   # 原料种数：大麦、燕麦、小麦
LIMIT = 100                 # 每种饲料份数的上限（题面：份数都小于 100）
MOST = PARTS * (LIMIT - 1)  # 三种饲料份数之和的上限 99+99+99，用来封顶枚举
ZERO = (0, 0, 0)            # 零配比，用于目标配比全为 0 的退化情形
NONE = 0                    # "混合结果不是目标配比的整数倍"的统一哨兵


def portions(mix: tuple[int, ...], target: tuple[int, ...], axis: int | None) -> int:
    """混合结果 mix 相当于几份目标饲料：是整数倍 k ≥ 1 时返回 k，否则返回 NONE。

    axis 是目标配比里第一个非零原料的下标，也是唯一可以拿来定倍数的位置：
    先用它整除出候选 k，再回代校验另外两味原料的比例是否一致。
    """
    if axis is None:  # 目标配比全为 0：只有零混合才是它的（1）倍
        return 1 if mix == ZERO else NONE
    k = mix[axis] // target[axis]
    same_ratio = mix == tuple(k * x for x in target)
    return k if k > 0 and same_ratio else NONE


def blend(target: tuple[int, ...], feeds: list[tuple[int, ...]]) -> tuple[int, ...] | None:
    """按份数总和递增枚举三种饲料的份数，返回第一组能配出目标配比的 (a, b, c, k)。

    总和 s 从 0 递增，同一 s 内按 a 递增、再按 b 递增检查，所以第一组命中的方案
    天然同时满足「总和最小、a 最小、b 最小、c 最小」，也就是题目要求的用量最少；
    无需记录候选最优解，也不可能在中途被更小的总和截胡。
    """
    axis = next((j for j in range(PARTS) if target[j]), None)
    first, second, third = feeds
    for total in range(MOST + 1):
        for a in range(min(total, LIMIT - 1) + 1):
            b_low = max(0, total - a - (LIMIT - 1))  # b 太小会让 c 超过份数上限
            b_high = min(total - a, LIMIT - 1)
            for b in range(b_low, b_high + 1):
                c = total - a - b
                mix = tuple(a * first[j] + b * second[j] + c * third[j] for j in range(PARTS))
                k = portions(mix, target, axis)
                if k:
                    return (a, b, c, k)
    return None  # 枚举完所有份数组合仍无解，对应题面的 NONE


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    target = tuple(next(data) for _ in range(PARTS))                              # 第 1 行：目标饲料
    feeds = [tuple(next(data) for _ in range(PARTS)) for _ in range(PARTS)]       # 第 2..4 行：三种饲料

    ans = blend(target, feeds)
    print("NONE" if ans is None else " ".join(map(str, ans)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:29
 * update_at: 2026-10-06 10:29
 */
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const ll PARTS = 3;     // 原料种数：大麦、燕麦、小麦
const ll LIMIT = 100;   // 每种饲料份数的上界（题面：份数都小于 100）

ll target[PARTS];       // 目标配比
ll feed[PARTS][PARTS];  // 三种饲料的配比，feed[i][j] 表示第 i 种饲料的第 j 味原料

// 判断混合结果 mix 是否是目标配比的正整数倍；若是返回 k，否则返回 0
// axis 是目标配比中第一个非零下标，用于确定候选倍数 k
ll check_ratio(ll mix[], ll axis) {
    if (axis < 0) { // 目标配比全为 0：只有零混合符合
        return (mix[0] == 0 && mix[1] == 0 && mix[2] == 0) ? 1 : 0;
    }
    if (mix[axis] % target[axis] != 0) return 0;
    ll k = mix[axis] / target[axis];
    if (k <= 0) return 0;
    for (ll j = 0; j < PARTS; ++j) {
        if (mix[j] != k * target[j]) return 0;
    }
    return k;
}

// 按份数总和递增枚举，返回第一组可行解 (a, b, c, k)；无解返回 false
bool solve(ll ans[]) {
    ll axis = -1;
    for (ll j = 0; j < PARTS; ++j) {
        if (target[j] != 0) {
            axis = j;
            break;
        }
    }
    ll most = (LIMIT - 1) * PARTS; // 份数总和的上界 99+99+99
    for (ll total = 0; total <= most; ++total) {
        ll a_max = min(total, LIMIT - 1);
        for (ll a = 0; a <= a_max; ++a) {
            ll b_low = max(0LL, total - a - (LIMIT - 1)); // 保证 c 不超过 99
            ll b_high = min(total - a, LIMIT - 1);
            for (ll b = b_low; b <= b_high; ++b) {
                ll c = total - a - b;
                ll mix[PARTS];
                for (ll j = 0; j < PARTS; ++j) {
                    mix[j] = a * feed[0][j] + b * feed[1][j] + c * feed[2][j];
                }
                ll k = check_ratio(mix, axis);
                if (k > 0) {
                    ans[0] = a; ans[1] = b; ans[2] = c; ans[3] = k;
                    return true;
                }
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (ll j = 0; j < PARTS; ++j) cin >> target[j];
    for (ll i = 0; i < PARTS; ++i)
        for (ll j = 0; j < PARTS; ++j)
            cin >> feed[i][j];
    ll ans[4];
    if (solve(ans)) {
        cout << ans[0] << " " << ans[1] << " " << ans[2] << " " << ans[3] << "\n";
    } else {
        cout << "NONE\n";
    }
    return 0;
}

usaco-3.2.4 饲料调配

目录

题目描述

思路

参考代码