【GESP】C++二级练习 luogu-P4956 [COCI 2017/2018 \#6] Davor

GESP二级练习，多层循环分支练习，难度★★☆☆☆。

luogu-P4956 [COCI 2017/2018 #6] Davor

题目要求

题目描述

After successfully conquering the South Pole, Davor is preparing for new challenges. Next up is the Arctic expedition to Siberia, Greenland and Norway. He begins his travels on 31 December 2018, and needs to collect ​N kunas (Croatian currency) by then. In order to do this, he has decided to put away ​X (​X ≤ 100) kunas every Monday to his travel fund, ​X + K kunas every Tuesday, ​X + 2* ​K every Wednesday, and so on until Sunday, when he will put away ​X + 6* ​K kunas. This way, he will collect money for 52 weeks, starting with 1 January 2018 (Monday) until 30 December 2018 (Sunday).

If we know the amount of money ​N​, output the values ​X and ​K so that it is possible to collect the ​exact money amount in the given timespan. The solution will always exist, and if there are multiple, output the one with the greatest ​X ​ and smallest ​K ​.

题意翻译

在征服南极之后，Davor 开始了一项新的挑战。下一步是在西伯利亚、格林兰、挪威的北极圈远征。他将在 2018 年 12 月 31 日开始出发，在这之前需要一共筹集 n 元钱。他打算在每个星期一筹集 x 元，星期二筹集 x+k 元，……，星期日筹集 x+6k 元，并连续筹集 52 个星期。其中 x,k 为正整数，并且满足 1≤x≤100。

现在请你帮忙计算 x,k 为多少时，能刚好筹集 n 元。

如果有多个答案，输出 x 尽可能大，k 尽可能小的。注意 k 必须大于 0。

输入格式

The first line of input contains the integer ​N​ (1456 ≤ ​N​ ≤ 145600), the number from the task.

输出格式

The first line of output must contain the value of ​X (​0 < ​X ​≤ 100 ​)​, and the second the value of K (K ​> 0 ​)​. 注：x 的范围是 0 < X ​≤ 100

输入 #1

1456

输出 #1

1
1

输入 #2

6188

输出 #2

14
1

输入 #3

40404

输出 #3

99
4

---

题目分析

解题思路

1. 首先，我们需要理解题目的核心要求：
   • Davor 需要在52周内攒够 N 克罗地亚库纳
   • 每周一存 X 库纳
   • 每周二存 X+K 库纳
   • 每周三存 X+2K 库纳
   • 以此类推到周日存 X+6K 库纳
   • 其中 0<X≤100，K>0
2. 解题思路：
   • 根据等差数列求和公式，每周存款为：7X + (0+1+2+3+4+5+6)K = 7X + 21K
   • 52周总和为：52(7X + 21K) = N
   • 从最大可能的X值(100)开始尝试
   • 通过公式计算对应的K值：K = (N/52 - 7X)/21
   • 如果K是正整数，则找到答案
   • 否则减小X继续尝试
   • 由于题目保证有解，该方法一定能找到满足条件的X和K

---

示例代码

#include <iostream>
using namespace std;
int main() {
    // 输入总金额n
    int n;
    cin >> n;
    // 初始化k为1（最小可能值）
    int k = 1;
    // 初始化x为100（题目要求的最大可能值）
    int x = 100;
    while(true) {
        // 根据等差数列求和公式计算k
        // 52周 * (7x + 21k) = n
        // 其中7x是每周基础金额之和，21k是每周增量金额之和
        double tmp_k = (n / 52 - 7 * x) /  21.0;
        // 如果k小于1，不符合题目要求，减小x继续尝试
        if (tmp_k < 1) {
            x--;
            continue;
        }
        // 将tmp_k转换为整数
        k = (int) tmp_k;
        // 如果k是整数（即tmp_k转换前后相等），说明找到了答案
        if (k == tmp_k) {
            cout << x << endl << k;
            break;
        } else {
            // 如果k不是整数，减小x继续尝试
            x--;
            continue;
        }
    }
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。