[CSP-J 2023] 小苹果
小 Y 的桌子上放着 \(n\) 个苹果从左到右排成一列,编号为从 \(1\) 到 \(n\)。
小苞是小 Y 的好朋友,每天她都会从中拿走一些苹果。
每天在拿的时候,小苞都是从左侧第 \(1\) 个苹果开始、每隔 \(2\) 个苹果拿走 \(1\) 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。
小苞想知道,多少天能拿完所有的苹果,而编号为 \(n\) 的苹果是在第几天被拿走的?
分析
解法1:模拟过程,大概有50分,加上一些乱搞做法可以优化到80+分
解法2:正解,问题1所求的是天数,每3个看作一个周期,每次拿走的是 \(\lceil n/3 \rceil\);问题2,找规律发现每次一定是当 元素位序 x%3==1是才被拿走。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
void brute_force() {
int n; cin >> n;
int a = 0, b = 0, t = n;
vector<int> st(n + 1);
for (int i = 1; i <= n; i++) st[i] = i;
int cnt = 0;
while (cnt < n) {
int i = 1, p = 1;
while (i <= n) {
if (st[i] == 0) i++;
else if (st[i] && p % 3 != 1) i++, p++;
else if (st[i] && p % 3 == 1) {
if (i == n) b = a + 1;
st[i++] = 0, p++, cnt++;
}
}
a++;
}
cout << a << " " << b << endl;
}
void solve() {
int n; cin >> n;
int a = 0, b = 0;
while (n > 2) {
a++;
if (!b && n % 3 == 1) b = a;
n -= ceil(n / 3.0);
}
a += n;
if (b == 0) b = a;
cout << a << " " << b;
}
int main() {
freopen("apple.in", "r", stdin);
freopen("apple.out", "w", stdout);
solve();
fclose(stdin), fclose(stdout);
return 0;
}