a264 - 骰子疊疊樂

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算用最少骰子疊成一疊，使得表面點數總和為 n 的最少骰子數量。如果無法達成，則輸出 -1。

解題思路

題目觀察發現，一個骰子的六個面點數和為 21。因此，如果 n 小於 21，則無法用骰子疊成，輸出 -1。如果 n 等於 21，則只需要一個骰子。 當 n 大於 21 時，可以考慮用多個骰子疊起來。 題目中給的例子暗示了骰子疊起來的特性，每個骰子除了頂面和底面外，還有四個側面。 如果 n 在 21 到 30 之間，則無法用骰子疊成，輸出 -1。 如果 n 在 30 到 40 之間，則需要兩個骰子。 如果 n 大於 40，則可以通過計算 (n-42) / 14 來確定需要的骰子數量。 如果 (n-42) % 14 小於 2 或大於 12，則無法用骰子疊成，輸出 -1。 否則，需要的骰子數量為 (n-42) / 14 + 3。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int n;
int main(){
	while(cin >> n){
		if(n<21){
			cout << "-1\n";
		}
		else if(n==21){
			cout << "1\n";
		}
		else if(n<30){
			cout << "-1\n";
		}
		else if(n<=40){
			cout << "2\n";
		}
		else{
			int rm=(n-42)%14;
			if(rm<2||rm>12){
				cout << "-1\n";
			}
			else{
				cout << (n-42)/14+3 << "\n";
			}
		}
	}
}