这题改自CSP-J2023的T1小苹果,原题见洛谷

本人参赛的时候0分,厚礼蟹!

今天我来造福大众

先看第一个问题:

要几轮才能拿完石子? 我们只需要模拟出来一轮会拿走几个石子,再一轮一轮拿,每轮计数器+1,直到拿完,输出计数器的值 至于每轮拿几个,上打表法! k=2时:

n=1,2,3 n=4,5,6 n=7,8,9 ...
1 2 3 ...

由此可以得出k=2时,每轮要拿(n+2)/3个石子 再然后另外两个打表也能得出来:

k=3时,每轮要拿(n+3)/4个石子

k=4时,每轮要拿(n+4)/5个石子

如果你特别聪明,一定发现了:

每轮你可以拿(n+k)/(k+1)个石子

再看第二个问题:

拿走第n个石子是在第几轮? 这个问题可以画图研究:

●○○○……○(k+1个)●○○○…○●……●○○○…○(k+1个)●

可以看出,在剩余石子能被分成若干个k+1还剩余一个时(即n%(k+1)==1),就能拿走第n个石子 那么只要满足这个条件就行吗?

NO!!!!

让我们看看n=7, k=2的情况

  1. ●○○●○○● 此时第7个已经被拿走
  2. ●○○●虽然也满足n%(k+1)==1,但如上面所说,第7个早被拿走了,不符合条件

所以,我们必须保证是第一次满足这个条件,第n个石子才会被拿走,那该怎么办呢?

Flag~~

只要用一个flag标记一下首次就行了

由此得代码:

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,k,a=0,ans,flag=0;  
    //a是拿的轮数, ans为拿走第n个石子的轮次,flag是标记“第一次满足n%(k+1)==1”
    cin>>n>>k;
    while(n!=0){
        a++; //每拿一轮轮次数+1
        if(n%(k+1)==1&&flag==0){ 
            ans=a;
            flag++; //若是第一次满足,就给flag+1,完成标记
        }
        n-=(n+k)/(k+1); //刚推的公式
    }
    cout<<a<<" "<<ans;
    return 0; //好习惯
}

看完这里,点个赞再走吧❤

2 条评论

  • @ 2024-1-24 21:31:01

    哇靠

    • @ 2024-1-24 21:24:55

      写题解不易,看客老爷们点个赞吧!

      👍 2
      • @ 2024-1-27 10:11:49

        没有点赞按钮

      • @ 2024-2-7 14:35:36

        @ 6

    • 1