高中生程式競賽:d547: 4. 秘密(secrets)－資工趴趴熊的小天地

內容

傳說 17 世紀著名的海盜船長基德曾將搶來一筆巨額財產藏匿在某無名小島上的洞穴中。因為是筆龐大的財富，所以在他死後，世界各地的寶藏探險家都想找到他寶藏的藏匿之處。但傳說因為基德船長怨靈的詛咒，進入洞穴的人都難逃一死，至今還沒有人活著出來過！因為恐懼，慢慢的大家不再提起這批寶藏，而寶藏的謎一直延續到現在。

傑克船長是一知名的寶藏探險家，至今已經找到許多傳說中藏匿的寶藏。某一天，傑克在酒吧裡因緣際會地得到這筆寶藏的藏寶圖，藏寶圖上除了揭露寶藏的所在地外還有一串由 0 與 1 組成的奇怪數字串。傑克船長於是根據藏寶圖率領他的船員順利地找到這無名的小島並進入洞穴中，最後抵達寶藏藏匿的地點。但他們卻發現藏匿寶藏的地點有無數道門，而每一扇門上都有一串奇怪的數列(包含 0 與 1 以外的其他整數值，整數之間有空格間隔)。而從白骨遍地的情景來推斷，這些門之中可能只有一扇門中有真正的寶藏，只有找對那扇門才能順利取得寶藏；而若開錯門，可能會引來殺身之禍！

傑克船長幾經推敲，終於發現門上的數列跟藏寶圖上的 0、1 數字串有某種關連，於是他將解法教給他的船員，要他們找出正確的門是哪一扇門。聰明的你(妳)，請幫助傑克船長的船員，寫一組程式算出看看哪一扇門後才是真正藏有寶藏，使他們能順利地取得寶藏！

例如，有 3 扇門，門上的數字串如下：藏寶圖上提示密碼為：
27 13 45 57 30 0 1 0 1
3 7 21 30 81
20 42 61 123 145

解法過程

先解第一扇門的數字串 27 13 45 57 30
由後往前(即右往左)推算，最後兩個數字先比大小，後面大於等於前面則為 1，反之為 0
30 < 57→ 0
接著後兩個數字相減的值取絕對值跟第三個數字比大小，若大於等於第三個數字為 1，反之為 0
30–57 = -27，取絕對值為 27 < 45 → 0
以此類推，若前面已無數字可比，則結束
57–45 = 12 < 13 → 0
45–13 = 32 > 27 → 1
所以 27 13 45 57 30 對應的 0、1 數字串為 1 0 0 0
同樣推算出第二串與第三串數字對應的 0、1 數字串
3 7 21 30 81 → 1 1 1 1
20 42 61 123 145 → 0 1 0 1
三扇門的數字串中唯一與提示密碼 0 1 0 1 符合者為 20 42 61 123 145，則此一扇門後即是真正藏有寶藏

輸入說明

輸入檔案中的第一行為兩正整數 N 與 M 其中 N 表示門的個數，M 代表地圖上的 0、1 數字串的個數

第二行為一串由 0、1 組成的數字串，以空格隔開，為提示密碼。

接著有 N 行，每一行對應某一扇門的數字串、數字間一樣以空格隔開，這 N 行中有一行的數字串為正確解答。

輸出說明

輸出正確解答的數字串，以空格隔開。

範例輸入 #1

範例輸出 #1

3 5 4

C++

/*
2(門的個數) 2(01個數) 
0 0(密碼) 
3 5 4(第一扇門) 
12 45 47(第二扇門) 

輸出
3 5 4  
*/
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	int pass[m];
	for(int i=0;i<m;i++){
		cin>>pass[i];// 0101
	}
	
	string s;
	getline(cin,s); //清除緩衝
	
	while(n--) {
		getline(cin,s); // 27 13 45 57 30
		stringstream ss(s);
		int x;
		vector<int> num,ans;
		while(ss>>x){
			num.push_back(x);
		}
		
		/*test*
		for(int h=0;h<num.size();h++) {
			cout<<num[h]<<" ";
		}*/
		
		int n1=-1,n2=-1;
		for(int j=m;j>0;j--){
			if(n1==-1){n1=num[j];} //跑第一次迴圈 27 13 45 57 [30] 
			else {n1=abs(num[j+1]-num[j]);} //第二次開始  27 13 45 [57 30] 
			n2=num[j-1]; //n2= 27 13 45 [57] 30
			
			//cout<<"n1"<<n1<<" n2"<<n2<<"\n"; //test
			
			//30跟57比 
			if(n1<n2) ans.push_back(0);
			else ans.push_back(1);
		}
		
		/*for(int h=0;h<ans.size();h++){
			cout<<ans[h]<<" ";
		}*/
		//cout<<"789789";
		reverse(ans.begin(),ans.end()); //將0001轉1000
		
		/*測試
		for(int h=0;h<ans.size();h++){
			cout<<ans[h]<<" ";
		}*/
		
		
		bool flag=true; //檢查是否跟密碼相同 
		
		for(int j=0;j<m;j++) {
			if(ans[j]!=pass[j]){
			flag=false;
			//cout<<456465;
			break;
			}
		}
		
		if(flag==true){
			for(auto i:num){ //自動疊帶 i:vector ans 
				cout<<i<<" ";
			}
			cout<<"\n";
		}
	}	
	return 0;
}

python:

n,m=map(int,input().split())
#n(門的個數) m(01個數)   
ps=list(map(int,input().split()))
for _ in range(n):
    door=list(map(int,input().split()))
    n1=-1
    n2=-1
    ans=[]
    for j in range(m,0,-1):
        if n1==-1:n1=door[j]
        else: n1=abs(door[j+1]-door[j])
        n2=door[j-1]
        
        if n1<n2:ans.append(0)
        else:ans.append(1)
    ans.reverse();
    #print(ans)
    flag=True
    
    for i in range(m):
        if ps[i]!=ans[i] :
            
            flag=False
            break
    if flag==True:print(*door)