小苹果 (CSP-J 2023)

一共 $n$ 个苹果，每轮都按隔两个拿走一个的方式拿走一批，问一共需要多少轮才能拿完。

$n < 10^9$ ，所以初看可能会觉得不能直接模拟。但是我们注意到每次基本拿走 $1/3$ 的苹果，所以苹果数量是指数级下降的。要确认这一点可以直接列出大体多少次拿完的公式：

$\frac{3}{2} ^ {\text{ans}} \approx n$

$\text{ans} \approx \log(n) / \log \frac{3}{2}$

所以ans是个很小的数，可以直接模拟。每次取走的苹果数量是 $\lceil \frac{x}{3} \rceil$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
 
int main() {
    scanf("%d", &n);
    int ans = 0, ans2 = 0;
    int x = n;
    for (; x > 0; ans++) {
        if (x % 3 == 1 && ans2 == 0)
            ans2 = ans + 1;
        x -= (x + 2) / 3;
    }
    printf("%d %d\n", ans, ans2);
 
    return 0;
}