c096 - 00700 - Date Bugs

🔗 前往 ZeroJudge 原題

題目描述

題目描述了多台電腦在特定年份出現日期錯誤的問題。每台電腦在到達某個年份時，會將年份重置為另一個較早的年份。給定每台電腦的錯誤資訊（顯示的年份、錯誤發生的年份、重置後的年份），要求找出最早的可能實際年份，該年份必須大於或等於所有重置年份中的最大值，並且在所有電腦上顯示的年份都與實際年份一致。如果找不到這樣的年份（小於 10000），則輸出 "Unknown bugs detected."。

解題思路

程式碼使用暴力法來解決問題。對於每組測試資料，程式首先讀取電腦的數量 n，然後讀取每台電腦的資訊 y_i, a_i, b_i。對於每個可能的年份 j，程式會檢查該年份是否滿足所有電腦的條件。具體來說，對於每台電腦，程式會計算如果實際年份為 j，則該電腦顯示的年份。如果該電腦顯示的年份與給定的年份 y_i 不一致，則 j 不是一個可能的實際年份。程式會從 max(a_i) 開始，依次檢查每個可能的年份，直到找到第一個滿足所有條件的年份或達到 10000。

複雜度分析

• 時間複雜度: O(n * 10000)，其中 n 是電腦的數量。程式需要遍歷所有可能的年份（最多 10000 個），並且對於每個年份，需要檢查所有電腦的條件（n 台）。
• 空間複雜度: O(10000)，程式使用一個大小為 10001 的陣列 ans 來記錄每個年份被多少台電腦顯示。

程式碼

#include <iostream>
using namespace std;
int main(){
	int n,ca=0;
	while(cin >> n){
		if(n==0)break;
		if(ca)cout << "\n";
		bool chat=0;
		int ans[10001]={0},a,b,c;
		for(int i=0;i<n;++i){
			cin >> a >> b >> c;
			c-=b;
			for(int j=a,i=0;j+i*c<10000;++i){
				++ans[j+i*c];
			}
		}
		cout << "Case #" << ++ca << ":\n";
		for(int i=0;i<10000;++i){
			if(ans[i]==n){
				cout << "The actual year is " << i << ".\n";
				chat=1;
				break;
			}
		}
		if(chat==0){
			cout << "Unknown bugs detected.\n";
		}
	}
	cout << "\n"; // for UVA
}