upc组队赛1 过分的谜题【找规律】

过分的谜题

题目描述

2060年是云南中医学院的百年校庆，于是学生会的同学们搞了一个连续猜谜活动：共有10个谜题，现在告诉所有人第一个谜题，每个谜题的答案就是下一个谜题的线索....成功破解最后一个谜题后，答案就是指向奖励的线索

在所有同学们的努力下，全校同学们获得了最后一个谜题，这个谜题有几十张纸，上面全是密密麻麻的数字以及'.'

第一页内容如下：

1,2,3,4,5,6

4,1,5,2,6,3

2,4,6,1,3,5

1,2,3,4,5,6

———3

1,2,3,4....32

.............

.............

———10

有细心的同学发现，这是对一组1-2n的序列进行如下移动：每次将前n个数字取出，按顺序依次插入到位于n+1,n+2...2n的数字后面，最后的数字表示多少次移动后会变回原来的序列

第二页内容如下：

1,2,3,4....64

.............

.............

———?

1,2,3,4....140

.............

.............

———?

同学们发现，越往后翻，这个序列的长度就越长，前面十几二十个数字的序列同学们还可以一步一步模拟做出来，但是到后来几千甚至上万的长度，就没有办法计算了，甚至中间一步做错，就步步都错。

这个谜题真是太过分了！但是奖励就在眼前，只要计算出所有答案，所有答案就是指引同学们获得奖励的线索，那么现在问题来了，同学们除了发现上面的n=最后那个数字/2之外，没有办法给你任何帮助，而作为一个计算机科学与技术专业的大佬，你自然就成为了同学们心目中拯救他们的英雄，所以你能不能写一个程序，当你知道n是多少的时候，可以直接得出答案呢？

输入

多组测试数据.每组数据的第一行包含一个正整数n(1<= n<=10000).

输出

每组数据输出一行整数表示最少需要经过几次移动能变回原序列，若不能，则输出"-1"

样例输入

3

16

样例输出

3

10

题解

打表找规律 可以只看1，看他是怎么回到原来的位置的

很明显的规律就是 如果x小于n就 x乘2，如果大于n超过了循环位数，就x = (x - n) * 2 - 1;

代码

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,n) for(int i=a;i<n;i++)

#define per(i,a,n) for(int i=n-1;i>=a;i--)

#define readc(x) scanf("%c",&x)

#define read(x) scanf("%d",&x)

#define read2(x,y) scanf("%d%d",&x,&y)

#define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define print(x) printf("%d\n",x)

int T;

int n,m;

int ans;

int main(){

  while(read(n) != EOF){

    int x = 1;

    ans = 0;

    while(x!=1 || !ans){

      ans++;

      if(x > n) {

        x = (x - n) * 2 - 1;

      }

      else

        x *= 2;

    }

    print(ans);

  }

}