d351 - 10878 - Decode the tape

🔗 前往 ZeroJudge 原題

題目描述

題目要求解讀一卷舊式電腦帶子上的訊息。帶子上有一系列的小洞，每個洞代表一個二進位數，透過將這些二進位數轉換為相應的 ASCII 字元，即可得到帶子上的訊息。帶子的訊息以 "___________" 作為結束標記。

解題思路

題目給定的帶子實際上是一種二進位編碼，每個小洞代表一個 bit。從輸入的字串中，'o' 代表 1，其他字元（例如 '_'）代表 0。程式碼遍歷字串的前九個字元（索引 1 到 9），將 'o' 轉換為 1，並將其累積到一個整數 k 中。由於第 6 個 bit 沒有使用，因此在計算時跳過。最後，將得到的整數 k 轉換為對應的 ASCII 字元，並輸出。程式會持續讀取輸入，直到遇到 "___________" 為止。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入字串的長度。因為程式需要遍歷每個輸入字串的前九個字元。
• 空間複雜度: O(1)，程式只使用了常數額外的空間來儲存變數。

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	string a;
	while(getline(cin,a)){
		if(a!="___________"){
			int k=0;
			for(int i=1;i<=9;++i){
				if(i!=6)k*=2;
				if(a[i]=='o')
					k+=1;
			}
			char ans=k;
			cout << ans;
		}
	}
}