【QED】高昂的猫 Ⅰ

本文主要是介绍【QED】高昂的猫 Ⅰ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目背景

这是小橘。因为它总是看起来很高傲，所以人送外号“高昂的猫”。

题目描述

"锕狗"的房间里放着$n$$(1\le n\le 10^9)$个猫粮罐头。它们从左到右排成一列，上面写有编号，分别为从$1$到$n$的正整数。

"小橘"是一只贪吃的猫，每天它都会从左往右巡视一遍这些罐头，并且从中吃掉一些。

每天在巡视罐头的时候，小橘都会将它在最左侧遇到的第$1$个罐头吃掉，然后每间隔$2$个罐头吃掉$1$个罐头。

锕狗想知道，这些罐头一共能供小橘这只肥猫吃几天？而编号为$x$$(1\le x\le n)$的超级大罐头将会在第几天被吃掉？请你帮他解决这两个问题。

输入格式

输入仅一行，包含两个用空格分隔开的正整数$n、x$，分别表示猫粮罐头的总数和超级大罐头的编号。

输出格式

输出仅一行，包含两个正整数。两个数之间由一个英文空格隔开，分别表示小橘吃完所有罐头所需的天数，以及吃掉编号为$x$的罐头是在第几天。

测试样例

8 6

5 2

样例说明

锕狗的房间里一共放了$8$个猫粮罐头。

小橘第$1$天吃掉了编号为$1、4、7$的罐头。

小橘第$2$天吃掉了编号为$2、6$的罐头，其中包括编号为$6$的超级大罐头。

小橘第$3$天吃掉了编号为$3$的罐头。

小橘第$4$天吃掉了编号为$5$的罐头。

小橘第$5$天吃掉了编号为$8$的罐头。

数据范围

$1\le n\le 10^9$

$1\le x\le n$

思路

这个题目询问了两个问题，第一个是罐头一共能吃几天，还有一个是编号为$x$的罐头是第几天吃掉的，首先我们来看第一个问题：
假设有罐头编号分别为：
1、2、3、4、5、6、7、8、9、10
第一天：1 、2、3、4、5、6、7、8、9、10
第二天：2、3、5、6、8、9
第三天：3、5、8、9
第四天：5、8
第五天：8
加入对每一天进行重新编码：
第一天：1 、2、3、4、5、6、7、8、9、10
第二天：1 、2、3、4、5、6
第三天：1 、2、3、4
第四天：1 、2
第五天：1
我们可以发现：对于重新编码的数字，每一天都是吃掉除以上余1的数字，根据这个我们可以更新每一天吃掉了多少个罐头推理出剩下的罐头数量，然后又可以继续推理出下一次的情况，一直到没有罐头
对于第二个问题：我们可以推理编号$x$是当前第几个数字，如果是除以三余1的数那么就是被吃掉的日子。

核心代码

#include <bits/stdc++.h>
#define debug(x) cout<<#x<<" = "<<x<<"\n"
using namespace std;
typedef long long LL;int main() {int n,x;cin>>n>>x;int a=0,b=0;while(n>0){n-=(n+2)/3;a++;}while(x>0){b++;if(x%3==1)break;x-=(x+2)/3;}cout<<a<<" "<<b;return 0;
}

这篇关于【QED】高昂的猫 Ⅰ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---