案例1：假金币

《案例1：假金币》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、案例1：假金币题目来源：POJ1029FalsecoinTimeLimit:3000MS MemoryLimit:10000KDescriptionThe"GoldBar"bankreceivedinformationfromreliablesourcesthatintheirlastgroupofNcoinsexactlyonecoinisfalseanddiffersinweightfromothercoins(whileallothercoinsareequalinweight).Aftertheeconomiccrisisthe

2、yhaveonlyasimplebalanceavailable(likeoneinthepicture).Usingthisbalance,oneisabletodetermineiftheweightofobjectsintheleftpanislessthan,greaterthan,orequaltotheweightofobjectsintherightpan.Inordertodetectthefalsecointhebankemployeesnumberedallcoinsbytheintegersfrom1toN,thu

3、sassigningeachcoinauniqueintegeridentifier.Afterthattheybegantoweightvariousgroupsofcoinsbyplacingequalnumbersofcoinsintheleftpanandintherightpan.Theidentifiersofcoinsandtheresultsoftheweightingswerecarefullyrecorded.Youaretowriteaprogramthatwillhelpthebankemployeestodet

4、erminetheidentifierofthefalsecoinusingtheresultsoftheseweightings.InputThefirstlineoftheinputfilecontainstwointegersNandK,separatedbyspaces,whereNisthenumberofcoins(2<=N<=1000)andKisthenumberofweightingsfulfilled(1<=K<=100).Thefollowing2Klinesdescribeallweightings.Twocon

5、secutivelinesdescribeeachweighting.ThefirstofthemstartswithanumberPi(1<=Pi<=N/2),representingthenumberofcoinsplacedintheleftandintherightpans,followedbyPiidentifiersofcoinsplacedintheleftpanandPiidentifiersofcoinsplacedintherightpan.Allnumbersareseparatedbyspaces.Theseco

6、ndlinecontainsoneofthefollowingcharacters:'<','>',or'='.Itrepresentstheresultoftheweighting:'<'meansthattheweightofcoinsintheleftpanislessthantheweightofcoinsintherightpan,'>'meansthattheweightofcoinsintheleftpanisgreaterthantheweightofcoinsintherightpan,'='meansthatthew

7、eightofcoinsintheleftpanisequaltotheweightofcoinsintherightpan.OutputWritetotheoutputfiletheidentifierofthefalsecoinor0,ifitcannotbefoundbytheresultsofthegivenweightings.SampleInput5321234<114=125=SampleOutput3假金币时间限制:3000MS 内存限制:10000K描述“GoldBar”银行收到可靠消息：在前次的N个金币中有一枚重量不

8、同的假金币(其他金币的重量都相同)。经济危机之后他们只有一台天平可用。用这台天平，可以称量出左边托盘中的物体是轻于、重于或等于右边托盘中的物体。为了分辨出假金币，银行职员将所有的金币编为1到N号。然后用天平