題目描述

2060年是云南中醫(yī)學(xué)院的百年校慶，于是學(xué)生會的同學(xué)們搞了一個連續(xù)猜謎活動：共有10個謎題，現(xiàn)在告訴所有人第一個謎題，每個謎題的答案就是下一個謎題的線索....成功破解最后一個謎題后，答案就是指向獎勵的線索
在所有同學(xué)們的努力下，全校同學(xué)們獲得了最后一個謎題，這個謎題有幾十張紙，上面全是密密麻麻的數(shù)字以及'.'
第一頁內(nèi)容如下：
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

有細(xì)心的同學(xué)發(fā)現(xiàn)，這是對一組1-2n的序列進(jìn)行如下移動：每次將前n個數(shù)字取出，按順序依次插入到位于n+1,n+2...2n的數(shù)字后面，最后的數(shù)字表示多少次移動后會變回原來的序列
第二頁內(nèi)容如下：
1,2,3,4....64
.............
.............
———?

1,2,3,4....140
.............
.............
———?

同學(xué)們發(fā)現(xiàn)，越往后翻，這個序列的長度就越長，前面十幾二十個數(shù)字的序列同學(xué)們還可以一步一步模擬做出來，但是到后來幾千甚至上萬的長度，就沒有辦法計(jì)算了，甚至中間一步做錯，就步步都錯。
這個謎題真是太過分了！但是獎勵就在眼前，只要計(jì)算出所有答案，所有答案就是指引同學(xué)們獲得獎勵的線索，那么現(xiàn)在問題來了，同學(xué)們除了發(fā)現(xiàn)上面的n=最后那個數(shù)字/2之外，沒有辦法給你任何幫助，而作為一個計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的大佬，你自然就成為了同學(xué)們心目中拯救他們的英雄，所以你能不能寫一個程序，當(dāng)你知道n是多少的時候，可以直接得出答案呢？

?

輸入

多組測試數(shù)據(jù).每組數(shù)據(jù)的第一行包含一個正整數(shù)n(1<= n<=10000).

?

輸出

每組數(shù)據(jù)輸出一行整數(shù)表示最少需要經(jīng)過幾次移動能變回原序列，若不能，則輸出"-1"

?

樣例輸入

復(fù)制樣例數(shù)據(jù)

3 16

樣例輸出

3 10

解決思路：

通過將前幾種情況，可以將一些規(guī)律大致推導(dǎo)出來，我們可以根據(jù)1所在的位置判斷出還需要進(jìn)行幾步到達(dá)第一位，當(dāng)1恢復(fù)原位后，會發(fā)現(xiàn)其他數(shù)也恢復(fù)原位，因此可以知道在經(jīng)過num步后，當(dāng)1到達(dá)n+1位置時，則還需要1步恢復(fù)原位，當(dāng)1到達(dá)n*2時，還需要num步恢復(fù)原位，對于其他的情況，則根據(jù)它所處的位置，假如1當(dāng)前的位置時x，當(dāng)n<x<=2*n時，下一步到達(dá)(x-n)*2-1，若1<=x<=n時，下一步到達(dá)x*2位，并標(biāo)記經(jīng)過的位置，若走到已走過的位置，則證明無法實(shí)現(xiàn)，輸出-1(ps:這題好像并不會出現(xiàn)這種情況)

代碼：

#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> #include <map> #include <stack> #include <queue> #include <vector> #include <bitset> #include <set> #include <utility> #include <sstream> #include <iomanip> using namespace std; typedef long long ll; typedef unsigned long long ull; #define inf 0x3f3f3f3f #define rep(i,l,r) for(int i=l;i<=r;i++) #define lep(i,l,r) for(int i=l;i>=r;i--) #define ms(arr) memset(arr,0,sizeof(arr)) //priority_queue<int,vector<int> ,greater<int> >q; const int maxn = (int)1e5 + 5; const ll mod = 1e9+7; bool vis[22000]; int main() {#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int n;while(scanf("%d",&n)!=EOF) {fill(vis+1,vis+1+2*n,false);int t=1;int num=0;for(int k=0;;k++) {t=t+(1<<k);if(t>2*n) {t=t-(1<<k);break;}num++;vis[t]=true;}if(t==n+1) printf("%d\n",num+1);else if(t==n*2) printf("%d\n",num*2);else {int nape=t;while(1) {if(nape>n) {nape=(nape-n)*2-1;num++;if(nape==n+1) {printf("%d\n",num+1);break;}if(nape==1) {printf("%d\n",num);break;}if(nape==n*2) {printf("%d\n",num*2);break;}if(vis[nape]==true) {printf("-1\n");break;}else {vis[nape]=true;continue;}}else {nape=nape*2;num++;if(nape==n+1) {printf("%d\n",num+1);break;}if(nape==1) {printf("%d\n",num);break;}if(nape==n*2) {printf("%d\n",num*2);break;}if(vis[nape]==true) {printf("-1\n");break;}else {vis[nape]=true;continue;}}}}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【思维】过分的谜题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。