|
LEN |
|
#25112
500円所有者＝”+1”， 1000円所有者＝”-1”， 輪の任意の開始位置をi=0とおき（f(0)=0)、そこから時計回りに進むとき、 所有者に遭うごとに、iを1インクリメントし、 500円所有者ならば、f(i)=f(i-1)+1, 1000円所有者ならば、f(i)=f(i-1)-1とする。 開始位置に戻ると、f(2n)=0=f(0)になる。 上の関数f(i)は、iの初期値0と終値間2nにおいて、最大値と最小値をもつ。 よって、f(i)が最小になる位置から始めれば、 釣り銭が不足することはありません。 反時計回りに進むときは、時計回りのときにf(i)が最大になる位置で f*(i)が最小になります。 f*(i)：開始位置をi=2nとおき(f*(2n)=0)、そこから反時計回りに進むとき、 所有者に遭うごとに、iを1デクリメントし、 500円所有者ならば、f*(i)=f*(i-1)+1, 1000円所有者ならば、f*(i)=f*(i-1)-1とする。 このとき、f(i)+f*(i)=0 |
|
5月21日（土） 3:25:24
25128 |