f045 - 3. 身分驗證機制 (Verification)

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取一個九位數的字串，並驗證其是否符合特定的身分驗證規則。驗證規則是：前七位數不重要，但第八和第九位數需要根據前七位數中最大的兩個數字來計算。具體來說，將前七位數中最大的兩個數字分別平方後相加，結果應該等於後三位數（第八、第九位）組成的整數減去 5328。如果驗證通過，則輸出 "Good Morning!"，否則輸出 "SPY!"。

解題思路

這題的解題思路是先從輸入的九位數字串中找出最大的兩個數字。然後，計算這兩個數字的平方和。最後，將字串的後三位轉換為整數，減去 5328，並將結果與先前計算的平方和進行比較。如果兩者相等，則輸出 "Good Morning!"，否則輸出 "SPY!"。程式碼直接使用字元比較來找到最大的兩個數字，避免了字串到整數的轉換，提高了效率。

複雜度分析

• 時間複雜度: O(n)，其中 n 是字串的長度（在本例中為 9）。程式碼需要遍歷字串一次來找到最大的兩個數字，然後進行一些常數時間的操作。
• 空間複雜度: O(1)。程式碼只使用了幾個整數變數來存儲最大值和中間結果，空間使用是固定的，不隨輸入大小變化。

程式碼

#include <stdio.h>
int main(){
	char a[9];
	while(scanf("%s",&a)>0){
		int max1=48,max2=48;
		for(int i=0;i<9;++i){
			if(a[i]>max1){
				max2=max1;
				max1=a[i];
			}
			else if(a[i]>max2)
				max2=a[i];
		}
		max2-=48;max1-=48;
		max1*max1+max2*max2==a[6]*100+a[7]*10+a[8]-5328?puts("Good Morning!"):puts("SPY!");
	}
}