全問題一覧

カテゴリ
以上
以下
13月前

4

問題文

初めに$N$枚のコインを持っています。下記のルールを守ってゲームを$m$回するとき、最後に持っているコインの枚数としてありえる枚数は$K$通りあります。このとき場合の数$K$を最大化するための$m$を答えてください。

ルール
  • コインゲーム筐体は$n$台あり一列に並んでいます。
  • 左から$i$番目の筐体でゲームをするにはコインを$i$枚消費します。
  • 1つの筐体につき一度しかゲームをできません。
  • ゲームに成功するとその筐体で消費した枚数の倍の枚数のコインが手に入ります。
  • ゲームに失敗するとコインは一枚も手に入りません。
  • 筐体は好きな順番でゲームをすることができます。
制約
  • $1 \le m \le n$
  • $2 \le n $
  • $ n^2 < N $

解答形式

半角英数と下記の半角記号で答えてください。

半角記号

()+-/^!

x^(n-1)/(x+y)!

ハノイの塔

KNKR_UT 自動ジャッジ 難易度:
14月前

2

問題文

3本の杭と中央に穴のあいた大きさの異なる$n$枚の円盤があります。いま、杭の1つにすべての円盤が小さいものが上にくるように積み重なっています(初期状態)。この状態から下記のルールを守りながら操作を行うとき、初期状態から到達し得る状態は何通りありますか。ただし初期状態も1通りと数え、また3本の杭は区別することとします。

例えば「左端の杭に大きさ1から$n$の全ての円盤が積み重なっている状態」を1つ、そこから操作を一回だけ行い、「左端に大きさ2から$n$の円盤、真ん中に大きさ1の円盤が積み重なっている状態」を1つ、のように状態の数をカウントします。また、「真ん中の杭に大きさ1から$n$の全ての円盤が積み重なっている状態」と、「右端の杭に大きさ1から$n$の全ての円盤が積み重なっている状態」のように杭が異なる場合もそれぞれ別の状態としてカウントします。

ルール
  • 円盤は一回に一枚ずつしか移動できない。
  • 小さな円盤の上に大きな円盤を乗せることはできない。

解答形式

半角英数字と下記の半角記号で答えてください。式中にスペースを含めないでください。

使える記号
  • 「+」加算
  • 「-」減算
  • 「*」乗算
  • 「/」除算(分数)
  • 「( )」かっこ
  • 「^」冪乗
  • 「!」階乗