Knockout Tournaments (UVa Live Archive Asia - Site 9 (Bangladesh) - 2010/2011 Dhaka (Bangladesh))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4859

問題

256人が戦うトーナメントが複数回ある。ある人が複数のトーナメントでw回勝って、l回負けた。その人が平均どのくらいのラウンドまで進んだかを求めよ。
0<=l,w<=200000000

解法

まずl=0でwが8の倍数でない場合はImpossibleとなる。それ以外の場合は、トーナメントが行われた回数がT回だとすると、その人は平均(w+l)/Tラウンドまで進む。なのでupper=w/8+l,lower=max(0,(w-7*l+7))/8+l+1

となる。普通に計算すると間に合わないので十分値が小さくなると考えられる場所はlogで近似する。