体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

第160回「今週のアルゴリズム:パズルゲーム「2048」の組み合わせは何通り?」正解者発表

「今週のアルゴリズム」とは

「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。

第160回は「今週のアルゴリズム:パズルゲーム「2048」の組み合わせは何通り?」の問題です。

問題文「第160回 今週のお題:パズルゲーム「2048」の組み合わせは何通り?」

2048というパズルゲームがあります。(Wikipedia)

イメージ

iPhoneやAndroidなどのアプリだけでなく、Web上で楽しむこともできます。

実際の動かし方は試してみるとよくわかるのですが、ここでは動かし方は問いませんので、以下の遊び方は理解しなくても問題ありません。

以下、Wikipediaによる「遊び方」からの抜粋です。

4×4のマスに数字が書かれたタイルがあり、スライドさせるとそれらはマスの端まで移動し、同時に新たなタイルが出現する。
同じ数字のタイルがぶつかると2+2=4、4+4=8というように数字が足し合わされていく。
最終的に2048のタイルができればゲームクリアだが、それ以後も続けることはできる。
また、完全にタイルが動かせない状態になるとゲームオーバーとなる。

ここでは、ゲームオーバーとなった状態、つまり隣同士(各マスの上下左右)に同じ数字が並んでおらず、すべてのマスが埋まった状態だけを考えます。
このときのスコアは、それぞれのマスを作るときに足し合わされた数の和です。

例えば、「4」のマスは「2」と「2」のマスが足しあわされたもの、「8」のマスは「4」と「4」のマスが足しあわされたものですので、「4」のマスを作ると2+2=4点、「8」のマスを作るときは「4」のマスを作り、さらに足し合わせた(2+2)+(2+2)+4+4=16点、「n」のマスを作ると n×(log2n – 1)点です。この点数をすべてのマスについて足し合わせてスコアを求めます。

※iPhoneアプリなどでは最初から「4」のマスが登場する場合があるため、冒頭のスクリーンショットでは合計が一致しませんが、今回は最初にすべて「2」のマスで始まるため、「2」のマスのみ点数に加算されないものとします。
(※上記の図の場合、今回の計算方法でのスコアは52536点になります。)

標準入力からスコアが与えられたとき、ゲームオーバーとなった状態が何通りあるかを求め、標準出力に出力してください。
なお、入力されるスコアは500以下の正の整数とします。
例えば、スコアが32のとき、以下の2パターンがありますので、以下のような入出力になります。
パターン1

パターン2

2
4
2
4
4
2
4
2
2
4
2
4
4
2
4
2

4
2
4
2
2
4
2
4
4
2
4
2
2
4
2
4

【入出力サンプル】
標準入力
32

標準出力
2

正解者

おめでとうございます!正解者のみなさんです。(新着順)

haruya様 

CodeIQ MAGAZINEの記事一覧をみる
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

山寺宏一&高木渉で『ポプテピピック』

GetNews girl / GetNews boy