CSP-J 2023 T1 小苹果 题解

· · 题解

Description

求共要拿几轮才能拿完和**最开始的**最后一个苹果第几轮被拿走。 ### Solution ----- 题意化简后如上，一般的人都不会想到找每轮拿走苹果原先编号的规律然后死磕磕不出来罢（除了我）。 对于第一个问题，显然可以从每轮减少的苹果数入手。 可以找找规律： ${\color{red}{1}},2,3,{\color{red}{4}},5,6,{\color{red}{7}},8,9,{\color{red}{10}}$。 设共拿走 $k$ 个苹果，则 $n=1\dots 10$ 的结果如下： $n=1,k=1$。 $n=2,k=1$。 $n=3,k=1$。 $n=4,k=2$。 $n=5,k=2$。 $n=6,k=2$。 $n=7,k=3$。 $n=8,k=3$。 $n=9,k=3$。 $n=10,k=4$。 然后就可以发现 $k = \left\lfloor\dfrac{n+2}{3}\right\rfloor$。 由于 $n \le 10^9$，所以可以一轮轮减去拿走的苹果数量，直至没有苹果。 第二问和上面相似。 首先，设最后一个苹果的编号为 $m=n-s$（$s$ 为该轮**前**拿走苹果总和），那么当 $m \bmod 3 = 1$ 时，该轮会拿走最后一个苹果。 当第一次出现 $m \bmod 3 = 1$ 时，显然，该轮会拿走**最开始的**最后一个苹果，记录该轮编号即可。 比如样例 $1$（下标为**初始编号**）： ${\color{red}{1_{(1)}}},2_{(2)},3_{(3)},{\color{red}{4_{(4)}}},5_{(5)},6_{(6)},{\color{red}{7_{(7)}}},8_{(8)}(s=0,m=8,m \bmod 3 = 2) {\color{red}{1_{(2)}}},2_{(3)},3_{(5)},{\color{red}{4_{(6)}}},5_{(8)}(s=3,m=5,m \bmod 3 = 2) {\color{red}{1_{(3)}}},2_{(5)},3_{(8)}(s=5,m=3,m \bmod 3 = 0) {\color{red}{1_{(5)}}},2_{(8)}(s=6,m=2,m \bmod 3 = 2) {\color{red}{1_{(8)}}}(s=7,m=1,{\color{red}{m \bmod 3 = 1}})

所以最开始的最后一个苹果在第 5 轮被拿走。

时间复杂度 \mathcal{O}(\log_3 n)。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,y=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')y=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x*y;
}
int n,a,b; 
int main(){
    n=read();
    while(n>0){
        a++;
        if(b==0&&n%3==1)b=a;
        n-=(n+2)/3;
    }
    printf("%lld %lld",a,b);
    return 0;
}