2023CSP-J 第二轮认证试题 第一题 (小苹果)
2023CSP-J 第二轮认证试题 第一题 (小苹果)
2 题目分析CSP-J 第一题一般编程不难，难在数学思想，例如上面这题，实际上是数学题。
首先说错误思路：因为题目要求苹果数量有 10^9 个，所以模拟法效率会很低，我们不能建立一个大数组或者链表，去模拟题目中的顺序一个一个取苹果。也不能使用递归，栈可能会爆掉。
2.1 拿走苹果的总天数我们先分析多少天可以拿走所有苹果
分析题目的关键点，观察苹果是如何取的：每隔两个取走一个
这句话提醒我们，如果每3个苹果分成一组，那么就是每组的第一个苹果会被拿走。
根据数学知识，任何一个数都可以表示为被3 整除的部分，和余数部分，也就是:
n = 3*p r
其中, 3*p 是可以被三整除的部分，r 是余数部分，0 <= r <3
因此，取苹果的过程可以看作，从 p 个分组中，每次取一个，从余数部分中（如果有的话），每次取一个。
因此每次取苹果的个数为：
if (r > 0) {
n -= p 1; // 每个组拿一个，余数组拿一个
} else {
n -= p; // 每个组拿一个，没有余数组
}
需要注意的是，如果只有余数组了，每次只能拿一个苹果:
if (p > 0) {
// 正常从所有组拿苹果
......
} else {
// 仅从余数组拿苹果，每次只能拿一个
n -= 1;
}
所以，完整的程序如下，使用 while 循环持续拿苹果，并记录天数即可:
#include <vector>
#include <iostream>
using namespace std;
int main() {
int n = 0;
cin >> n;
int days = 0;
// n = 3p r;
while (n > 0 ) {
int p = n / 3;
int r = n % 3;
if (p > 0) {
if (r > 0) {
// 每个组拿一个，余数组拿一个
n -= p 1;
} else {
// 每个组拿一个
n -= p;
}
} else {
// 余数组一个一个拿
n -= 1;
}
days ;
}
cout << days;
return 0;
}2.2 第几天拿走最后一个苹果
考虑取苹果的过程，如果余数组苹果个数为 1, 那么这天就是取最后一个苹果的日子，
如果余数组苹果数量始终不为1, 那么最后一个苹果一定是最后一天拿走的。
因此，我们增加一个标志位，表示在取苹果的过程中，是否取走过最后一个，如果取走了，就记录天数；否则，就是最后一天。
if (p > 0) {
if (r > 0) {
......
if (!flag && r == 1) {
lastDay = days 1;
flag = true;
}
} else {
......
}
} else {
......
}
if (!flag) {
lastday = days
}
完整代码如下：
#include <vector>
#include <iostream>
using namespace std;
int main() {
int n = 0;
cin >> n;
int days = 0;
int lastDay = 0;
bool flag = false;
// n = 3p r;
while (n > 0 ) {
int p = n / 3;
int r = n % 3;
if (p > 0) {
if (r > 0) {
// 每个组拿一个，余数组拿一个
n -= p 1;
if (!flag && r == 1) {
lastDay = days 1;
flag = true;
}
} else {
// 每个组拿一个
n -= p;
}
} else {
// 余数组一个一个拿
n -= 1;
}
days ;
if (!flag) {
lastDay = days;
}
}
cout << days << ' ' << lastDay;
return 0;
}3 总结
解决本题需要的编程知识较少，会使用 while 循环，会计数即可。本题的难点在于初等数论的知识，也就是
“任何一个整数，可以表示为被三整除的部分加上余数部分”：
n = 3*p r
理解了这一点，此题也就应刃而解了。
