题解 P9748 [CSP-J 2023] 小苹果

· · 题解

撞上我曾经出给 CROI R1 的原题了，很强。

思路

假设这一天还剩 x 个苹果。
我们每 3 个苹果分一组，剩余分不满一组的也分一组。显然从每组中会拿走 1 个 苹果。
所以这一天将拿走 \left\lceil\dfrac{x}{3}\right\rceil 个苹果。

每次拿走的是一组中的第 1 个苹果，而一组一共有 3 个苹果。
所以当且仅当 i \operatorname{mod} 3=1 时，第 i 个苹果会被拿走。
那么我们每天重新算一下 n 前面有几个苹果，我们就可以知道 n 在这一天排在第几个。当某天 n \operatorname{mod} 3=1 时，将在这一天被拿走。

代码

#include<bits/stdc++.h>
using namespace std;
int n,x;
int ans,cnt;
int main(){

    scanf("%d",&n);
    x=n;

    while(x){//还剩了苹果就一直取
        cnt++;
        x-=(x+2)/3;//这个相当于想上取整
    }
    printf("%d ",cnt);

    while(1){
        ans++;
        if(n%3==1)break;//取走了
        n-=(n+2)/3;//下一天剩多少苹果
    }
    printf("%d",ans);
    return 0;
}