小 Y 的桌子上放着nnn 个苹果从左到右排成一列,编号为从111 到nnn。
小苞是小 Y 的好朋友,每天她都会从中拿走一些苹果。
每天在拿的时候,小苞都是从左侧第111 个苹果开始、每隔222 个苹果拿走111 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。
小苞想知道,多少天能拿完所有的苹果,而编号为nnn 的苹果是在第几天被拿走的?
输入格式输入的第一行包含一个正整数nnn,表示苹果的总数。
输出格式输出一行包含两个正整数,两个整数之间由一个空格隔开,分别表示小苞拿走所有苹果所需的天数以及拿走编号为nnn 的苹果是在第几天。
样例 #1 样例输入 #1 8 样例输出 #1 5 5 提示【样例 11 1 解释】
小苞的桌上一共放了888 个苹果。 小苞第一天拿走了编号为111、 444、 777 的苹果。 小苞第二天拿走了编号为222、 666 的苹果。 小苞第三天拿走了编号为333 的苹果。 小苞第四天拿走了编号为555 的苹果。 小苞第五天拿走了编号为888 的苹果。
【样例 22 2】
见选手目录下的 apple/apple2.in 与 apple/apple2.ans。
【数据范围】
对于所有测试数据有: 1 ≤ n ≤ 1 09 1\leq n\leq 10^91≤n≤109。
测试点n≤n\leq n≤特殊性质1∼21\sim 2 1∼21010 10无3∼53\sim 5 3∼51 0 310^3 103无6∼76\sim 7 6∼71 0 610^6 106有8∼98\sim 9 8∼91 0 610^6 106无1010 101 0 910^9 109无特殊性质:小苞第一天就取走编号为nnn 的苹果。
【解析】 最朴素的做法,使用数组标记苹果是否被取走,模拟即可。算法复杂度为O(nlogn),(理论上为90分) 详见代码:
#include using namespace std;bool a[1000005];//切记不能定义为1000000005,会直接报0;int n;int ans=0;//一共用几轮拿空int ans2;//最后一个第几轮拿走int main() {cin>>n;for (int i=1;i//只要还有苹果int x=0;ans++;//增加一轮for(int i=1;ix++;if (x%3==1){//如果是第1.4.7....则拿走a[i]=0;cnt++;if(i==n){//如果是最后一个,记录第几轮ans2=ans;}}}}}cout//只要还有苹果int x=0;ans++;//增加一轮for(int i=1;ix++;if (x%3==1){//如果是第1.4.7....则拿走a[i]=0;cnt++;if(i==n){//如果是最后一个,记录第几轮ans2=ans;}}}}}couti++;if (n%3==1&&ans==0){//当最后一个苹果位置为三的倍数多1,就会被拿走,一旦拿走,不再判断。ans=i;}n-=(n+2)/3;//每次拿走n/3向上取整个苹果}cout