B. Neko Performs Cat Furrier Transform
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Cat Furrier Transform is a popular algorithm among cat programmers to create longcats. As one of the greatest cat programmers ever exist, Neko wants to utilize this algorithm to create the perfect longcat.
Assume that we have a cat with a number xx. A perfect longcat is a cat with a number equal 2m−12m−1 for some non-negative integer mm. For example, the numbers 00, 11, 33, 77, 1515 and so on are suitable for the perfect longcats.
In the Cat Furrier Transform, the following operations can be performed on xx:
The first applied operation must be of type A, the second of type B, the third of type A again, and so on. Formally, if we number operations from one in the order they are executed, then odd-numbered operations must be of type A and the even-numbered operations must be of type B.
Neko wants to produce perfect longcats at industrial scale, thus for each cat Neko only wants to perform at most 4040 operations. Can you help Neko writing a transformation plan?
Note that it is not required to minimize the number of operations. You just need to use no more than 4040 operations.
Input
The only line contains a single integer xx (1≤x≤1061≤x≤106).
Output
The first line should contain a single integer tt (0≤t≤400≤t≤40) — the number of operations to apply.
Then for each odd-numbered operation print the corresponding number nini in it. That is, print ⌈t2⌉⌈t2⌉ integers nini (0≤ni≤300≤ni≤30), denoting the replacement xx with x⊕(2ni−1)x⊕(2ni−1) in the corresponding step.
If there are multiple possible answers, you can print any of them. It is possible to show, that there is at least one answer in the constraints of this problem.
Examples
input
Copy
39
output
Copy
4 5 3
input
Copy
1
output
Copy
0
input
Copy
7
output
Copy
0
Note
In the first test, one of the transforms might be as follows: 39→56→57→62→6339→56→57→62→63. Or more precisely:
In the second and third test, the number already satisfies the goal requirement.
=========================================================================
这类改变的题目,如果没有通解的话会非常混乱,加1异或某数,各个位置一会是0一会是1,我们考虑一位一位修改,每次寻找一个最高位的0,异或上某个正好在这一位上的2^n-1,那么就成功完成了修改,然后下一个加1之后接着寻找即可,寻找之前别忘了判断是否全是1即可
‘
- #include
- # include
-
- using namespace std;
-
-
- bool check(int x)
- {
- for(int i=0;(1<
- {
- if((x&(1<0)
- return 0;
- }
- return 1;
- }
-
- int temp;
- int getpos(int x)
- {
- temp=0;
- for(int i=0;(1<
- {
- if((x&(1<0)
- {
- temp=i;
- }
- }
-
-
-
- int ans=(1<<(temp+1))-1;
-
-
- temp++;
-
- return ans;
-
- }
- vector<int>v;
-
- int main()
- {
-
- int x;
-
- cin>>x;
-
- for(int i=1;i<=40;i++)
- {
- if(check(x))
- {
- cout<-1<
-
- for(auto it:v)
- {
- cout<
" "; - }
-
- return 0;
- }
-
- if(i%2)
- {
- int now=getpos(x);
-
- x^=now;
-
- v.push_back(temp);
- }
- else
- {
- x++;
- }
- }
-
-
-
-
- return 0;
-
- }
-
相关阅读:
Rocky Linux 更新本地镜像源
day04 spring 声明式事务
从零开始打造一款基于SpringBoot+SpringCloud的后台权限管理系统
物联网毕业设计 - 基于Arduino单片机的便携抽湿加湿器
App买量越来越难,三大增长机遇不容错过
拒绝水文!八大排序(三)【适合初学者】快速排序
如何用jxTMS开发一个功能(五)
【前端必会】不知道webpack插件? webpack插件源码分析BannerPlugin
Lamda表达式的推演过程
Postman+Newman+Jenkins实现接口测试持续集成
-
原文地址:https://blog.csdn.net/jisuanji2606414/article/details/126344749