e665 - 108 p3. 彩珠的計算

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個數字 a，代表彩珠的層數。每一層有 2^i 個彩珠，其中 i 是層數 (從 1 開始)。彩珠的顏色依照順序循環分配：第一種顏色、第二種顏色、第三種顏色、第一種顏色...。題目要求計算每一種顏色的彩珠數量，分別是紅色、綠色和藍色。

解題思路

這題的解題思路是模擬彩珠的分配過程。我們使用一個迴圈來遍歷每一層彩珠，然後在每一層中，我們使用另一個迴圈來遍歷每一顆彩珠，並根據彩珠的索引來確定它的顏色。紅色對應索引模 3 等於 1，綠色對應索引模 3 等於 2，藍色對應索引模 3 等於 0。

複雜度分析

• 時間複雜度: O(2^a)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int main(){
	int a;
	while(cin >> a){
		int i=1,r=0,g=0,b=0;
		while(a>0){
			for(int j=1;j<=i;j++){
				if(j%3==1)
					r++;
				else if(j%3==2)
					g++;
				else if(j%3==0)
					b++;		
			}
			a--;
			i*=2;
		}
		cout << r << " " << g << " " << b << endl;
	}
}