Tube's World

Q: http://uva.onlinejudge.org/external/100/10030.html

個人認為這題是我目前為止寫過最難的一題

我想題目難以理解是原因之一

不過網路上竟然沒有任何人有po這題的解法

讓我感到相當驚訝(查了之後才發現有過這題的人不到200個......)

光是要了解題意就要耗上不少時間

所以在這裡先講解題意

首先有一個server兩個client

server存有檔案,而兩個client都知道在server上的所有檔案的完整檔名(以下簡稱full)

一個檔案的檔名包含主檔名(以下簡稱name)和副檔名(以下簡稱ext)

例如有一檔案WIN32.LOG

則full為WIN32.LOG

name為WIN32

ext為LOG

現在server會將一個檔案的name傳給其中一個client(以下簡稱name方)

而檔案的ext則傳給另外一個client(以下簡稱ext方)

client端會想辦法依據現有的資訊拼湊出真正的完整檔名為何

如果有一方沒有辦法依據現有的資訊來拼湊出真正的完整檔名時

就會發出一個疑問訊息給另一方(注意,他們只會傳疑問訊息,不會傳其他訊息)

首先發出疑問訊息的一定是ext方(題目說的)

像是以題目的範例input為例,傳WIN32.LOG時

name方會收到WIN32, ext方會收到LOG

此時因為server上面只有一個LOG檔,所以ext方馬上就知道說server傳的檔案為WIN32.LOG

所以ext方就不會發出疑問訊息,所以這個檔案所需要的訊息數為0

如果是ZLIB32.DLL這個檔案,因為DLL檔不只一個

ext方無法馬上得知此檔案的完整檔名為何

所以他會傳一個疑問訊息給name方,告訴name方說他不知道檔名為何

此時name方"才"開始檢查他收到的name,發現name為ZLIB32的檔案,server上只有一個

所以name方可以馬上確定說此檔案為何,訊息交換於是結束,所以ZLIB32.DLL這個檔案所需要的訊息數為1

再來看PSTOTXT3.DLL

ext方無法立即得知完整檔名-->傳訊息給name方

此時name方發現server上name為PSTOTXT3的檔案也不只一個

所以他也無法立即得知完整檔名,所以他也傳一個疑問訊息給ext方,告訴他說他現在也無法得知完整檔名為何

此時ext方就會開始想"什麼樣的DLL檔,在我傳疑問訊息給name方時,name方也會傳一個疑問訊息給我呢?"

答案只有PSTOTXT3.DLL這個檔案

因為如果是像其他的GSVW32DE.DLL, GSVW32EN.DLL和ZLIB32.DLL的話

name方馬上就可以知道答案而不會傳疑問訊息給ext方(因為他們的name在server上都是獨特的)

只有PSTOTXT3.DLL這個檔案才會讓name方回傳疑問訊息給ext方

所以ext方就可以得知,server傳的檔案是PSTOTXT3.DLL這個檔案(是有沒有這麼聰明orz)

所以PSTOTXT3.DLL所需要的訊息數為2

而我們要做的,就是在知道message數目的情況下

推出目前server再傳的檔案有哪些可能解

像是範例測資message數為2

則答案可能有6種情況

其中PSTOTXT3.DLL ,PSTOTXT3.EXE的message數為2

其他4個檔案則是雙方不管再怎麼傳message都不可能得知(這種情況也要印出來,因為題目有說message會一直傳到他們能夠得知檔案or他們放棄得知)

另外補充一種題目沒說明到的情況

就是如果此檔案沒有副檔名,則ext方會收到一個空字串

此時如果server上只有一個檔案沒有副檔名

那麼ext方也有辦法馬上得知此檔案為何

大家應該可以發現這個問題的題意跟撲克牌推裡是一樣的道理

當然上面的例子並不是很完整

像message數為1的情況可不只我剛剛舉的那一種

還有其他的情況也會導致message數為1

乍看之下好像很麻煩,需要考慮很多種情況(如果有那種互傳100次message才有辦法得知檔名的情況發生時該怎麼辦)

我一開始也是卡在這,想說怎麼會這麼麻煩

甚至還推出"如果message數超過2次的話就表示這個檔案不可能找到"這種錯誤結論

最後請教同學之後才知道怎麼做

答案是刪去法

假設message數為3

則設個迴圈跑三次

每次都去檢查有哪些檔案是獨特檔案

第一次先檢查副檔名,把有獨特副檔名的檔案刪掉

第二次則從剩下的檔案中檢查主檔名,把有獨特主檔名的檔案刪掉

第三次再換回檢查副檔名......如此這樣循環下去

最後把沒被刪掉的檔案全部印出來

為什麼要這樣做呢?

其實想一想就知道

一開始一定是由ext方檢查副檔名

如果有傳訊息給name方,則由name方接手開始檢查主檔名

如果又傳訊息給ext方,則繼續由ext方接手檢查副檔名

一直這樣循環下去,直到找到檔案or放棄尋找

講了這麼多終於要開始講code的實作部分了

我個人是用map來記錄name和ext的數目

只要令個map<string, int>,就可以直接用string來當作index, 進行數目的運算和檢查,相當方便

一開始讀取檔名時,把每個檔案的完整檔名,主檔名和副檔名都記錄起來

如果沒有副檔名,則將副檔名標示為一個空白(這也是字串啊)

然後將name和ext的數目都用map記錄起來(注意,要用2個不同的map分別記錄,要不然如果有EXE.EXE這種name和ext長得一樣的檔案就會發生錯誤)

記錄完所有資料後就用個for迴圈去檢查,刪除檔案

最後將沒被刪除的檔案全印出來

要注意印出格式(不同case兩兩之間要隔一個blank)

這篇應該是我目前為止寫得最長的一篇詳解吧@@

獻給那些被UVA-10030搞死卻苦無參考資料的夥伴們QQ