網頁

2014年1月2日 星期四

UVa 10666 The Eurocup is Here!

題意:
  • Team 4贏過Team 6,而Team 6贏過Team 7,那麼表示Team 4確定贏過(優於)Team 7,也可說Team 7比Team 4差。
  • Team 0同時贏過Team 4和Team 2,則Team 4和Team 2關係無法確定。
  • 因為隊伍與隊伍之間關係有些確定有些不確定,本題要求出Team X可能最佳為第幾名,以及最差為第幾名
想法:
  • 1.找最佳:只要找到贏過Team X的共有n隊,那麼n+1即是Team X的最佳名次。
  • 1.做法:win(x)函數找到贏過Team X的隊伍(設為a),再繼續win(a)找到贏過Team a的隊伍(設為b),一直找到底(Team 0)為止,計算途中總共幾隊。
  • 2.找最差:計算比Team X差的隊伍總共有幾隊,那麼Team X的最差名次就是全部隊伍數減掉比Team X還差的隊伍數
  • 2.做法:Team X如果在Round r輸掉,那麼比Team X差的隊伍數為(2^(r-1)-1),可多次觀察樹狀圖r=1,2,3,4...其結果為0,1.3,7...得知