♐ CSP_J 组真题
2023年
1. apple

线上OJ:

https://www.jisuanke.com/problem/T3917 (opens in a new tab)
https://www.luogu.com.cn/problem/P9748 (opens in a new tab)

题目分析:

  1. 第一问:几天拿完 直接计算每一天拿去后的苹果个数,设拿之前有 n 个苹果,拿完后剩 n − ⌈3/n⌉(向上取整) 个苹果。
  2. 第二问:编号为n的苹果(即:最后一个苹果)在第几天被拿走 设每一天有 n 个苹果,当 n mod 3 == 1 时即可,且第一次出现。
💡

向上取整 的代码 (m+(n1))n\dfrac{(m+ (n-1))}{n} ,所以每天最少拿走多少个为 m+23\dfrac{m+2}{3}

核心思想:

由于从编号 1开始,每隔 2个取走1个,所以实际是每3个取走1个...
假设每一轮开始前的总数为 m,由数学归纳法得这一轮要取走的数量是 (m+2)/3 。(因为每一组取走的都是第1个),所以每一轮取走的总数量是 (m+2)/3

比如:当前 m=8, 则
第一轮取走 10/3=3个,剩余5个;
第二轮取走 (5+2)/3=2个,剩余3个,
第三轮取走 (3+2)/3=1个,剩余2个,
第四轮取走(2+2)/3=1个,剩余1个;
第五轮取完

所以第一个问题:几天取完可以根据每天剩余 m-(m+2)/3,while循环直至m变为0

第二个问题问的是 编号为 n 的第几天被取走,由于编号为n的永远是在最后一个,所以当第一次剩余数量 m为3倍余1时,最后一个会被取走,记录此时的天数即可

题解代码:

#include <bits/stdc++.h>
using namespace std;
 
int n, m;
int cnt = 0; 	// 第 cnt 天
int day = 0;	// 记录编号为n被取走的那天
 
int main()
{
	cin >> n;
	m = n;
	
	while(m)
	{
		cnt++;	// 第 cnt 天 
		
		if((!day) && (m%3 == 1))	// 如果day还没被更新,且当前总数 m为3的倍数+1,说明本轮的最后一个数会被取走,也就是编号n会被取走 
			day = cnt;	
		
		m -= (m+2) / 3;	 // 取走 (m+2)/3,剩余 m - (m+2)/3 
	} 
 
	cout << cnt << " " << day;
	return 0;
}