An Asian Preliminary Regional（20151205）
(ICPC Dhaka 2015 Preliminary)
UVa 13032
$N$ 個の箱があって，$i$ 番目の箱には $M_i$ 個のビー玉が入っている．
$1$ つの箱を除き，ビー玉は全て $1$ グラムだが，ある箱に入っているビー玉だけは全部 $1.1$ グラムである．
重さをはかる測りを $1$ 度だけ使うことができる．
全ての箱から $1$ 個以上のビー玉を取って，合計の重さをはかる．
この時，どの箱に入っているビー玉が $1.1$ グラムなのかを確実に見分けることができる方法は何通りあるかを $\text{mod}\ 1000000007\ (10^9+7)$ で求める問題．
全ての箱に対して，箱から取り出したビー玉の数が等しい場合は，同じ方法と見なす．
要するに，全ての箱から，違う数のビー玉を選べば良い．
ビー玉の数が小さい順に箱をソートしておき，条件が厳しい方から順番に選んでいく．
すると，$i$ 番目の箱では，$1,2,\ldots,M_i$ という選択肢がある中で，
$i-1$ 番目の箱までで，$i-1$ 個は必ずすでに使われていて選べないから，
$i$ 番目の箱での選択肢の数は $M_i - i + 1$ となる．
よって，
\begin{align*}\prod_{i=1}^N \max(M_i - i + 1, 0)\end{align*}を求めれば良いことになる．
この部分を表示するには表示権限を持つユーザーでログインする必要があります．
Current time: 2024年04月19日18時23分00秒
Last modified: 2015年12月16日01時24分57秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151205_1
トップページに戻る
Logged in as: unknown user (not login)