[COCI 2017/2018 #6] Davor

题意

每周七天存的钱分别是：

text

1X, X+K, X+2K, ..., X+6K

一共存 52 周，给出总额 N，求满足条件的 X 和 K。如果有多组答案，要求输出最大的 X，同时 K 最小。

思路

先把一周的总额合并：

text

17X + (0+1+2+3+4+5+6)K = 7X + 21K

一年 52 周，所以：

text

1N = 52 * (7X + 21K) = 364X + 1092K

题目限制 X <= 100，范围很小。为了得到最大的 X，直接从 100 到 0 倒着枚举 X。对每个 X，检查剩下的钱是否能被 1092 整除，且 K > 0。

第一个找到的合法 X 就是最大 X，对应的 K 也满足题目要求。

这题的枚举空间很小，正解已经是直接枚举，不创建额外 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：用 int(input()) 读取总额。
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md：本题只用整数加减乘除，Python int 足够稳定。
range(100, -1, -1) 表示从 100 倒着枚举到 0。
rest % 1092 == 0 用来判断能否整除。

代码

python

1
2
3
4
5
6
7
8
9target = int(input())

for x in range(100, -1, -1):
    rest = target - 364 * x
    if rest > 0 and rest % 1092 == 0:
        k = rest // 1092
        print(x)
        print(k)
        break

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/**
 * 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-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; // 一年存的总钱数
    cin >> N;
    // 代数化简后：N = 364 * X + 1092 * K
    // 要输出最大的 X，所以从 100 倒着枚举
    for (int x = 100; x >= 0; x--) {
        int rest = N - 364 * x;
        // 剩下的钱要能被 1092 整除，且 K > 0
        if (rest > 0 && rest % 1092 == 0) {
            int k = rest / 1092;
            cout << x << endl << k << endl;
            break;
        }
    }
    return 0;
}

复杂度

最多枚举 101 个 X，时间复杂度是 $O(1)$ ，空间复杂度是 $O(1)$ 。

总结

这题先做代数化简，再利用 X 范围很小倒序枚举。倒序枚举让“最大 X”这个要求自然满足。

[COCI 2017/2018 #6] Davor

目录

题意

思路

Python 知识

代码

复杂度

总结