题目描述
小的桌子上放着几个苹果从左到右排成一列,编号为从1 到 。小苞是小的好朋友,每天她都会从中拿走一些苹果。每天在拿的时候,小苞都是从左侧第1个苹果开始、每隔2个苹果拿走1个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。小苞想知道,多少天能拿完所有的苹果,而编号为 的苹果是在第几天被拿走的?
输入格式
输入的第一行包含一个正整数 ,表示苹果的总数。
输出格式
输出一行包含两个正整数,两个整数之间由一个空格隔开,分别表示小苞拿走所有苹果所需的天数以及拿走编号为 的苹果是在第几天。
样例输入
8
样例输出
5 5
思路
(本蒟蒻也是参加了本次CSP-J组的复赛,不过也是掉进了第一题的坑里)
注意:单纯的数组模拟是不能AC的(本蒟蒻使用此方法:50分,是TLE),因为数组模拟必须要用二重循环,时间复杂度为
我们可以发现6~10测试点的数据范围均为 以上,如果还用的算法,必然会超时(TLE),所以必须要用级别的算法。我们可以画一个图来模拟一下,应该不难发现每次拿去的苹果数量都是 ,也就是 除以 3 的向上取整,那么有了这一结论,问题就迎刃而解了!
贴代码!!!
参考代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
//const int N = ;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int i, n, ans = 0; //i 表示共进行多少轮,ans 表示第 n 个苹果被拿走时的轮数
cin>>n;
while(n) // n 不等于0
{
i++;
if(n % 3 == 1 && ans == 0) // 仅剩一个苹果时,当3个3个的苹果被拿完后,便是答案
ans = i;
n -= (n + 2) / 3; // n 减去向上取整再除3
}
cout << i << " " << ans;
return 0;
}
后续CSP-J组真题持续更新,喜欢的点个关注+赞!