問題
1マス目には1粒の穀粒があります。それ以降の各マスには、直前のマスの2倍の穀粒が置かれます。指定されたマスの穀粒数と、1〜64マスすべての合計を返してください。合計値は符号付き64ビット整数では表せないほど大きくなるため、各値は10進数の文字列で返してください。
chessboard_grains(square) を実装してください。
入力
square: 求めるマスの番号(1から始まります)。
出力
2つの10進数文字列を返してください: [指定したマスの穀粒数, 全64マスの合計穀粒数]。
制約
1 ≤ square ≤ 64。出力の文字列は10進数字のみで構成し、カンマ、スペース、先頭のゼロは含めないでください。
例
入力:
square = 6
期待される出力:
expected = ["32", "18446744073709551615"]
入力:
long long square = 6;
期待される出力:
std::vector<std::string> expected = {"32", "18446744073709551615"};
入力:
long square = 6;
期待される出力:
string[] expected = new string[] {"32", "18446744073709551615"};
解説
最初の6マスの穀粒数は1, 2, 4, 8, 16, 32です。全体の合計は 1 + 2 + … + 2⁶³ = 2⁶⁴ − 1 となります。
入力:
square = 1
期待される出力:
expected = ["1", "18446744073709551615"]
入力:
long long square = 1;
期待される出力:
std::vector<std::string> expected = {"1", "18446744073709551615"};
入力:
long square = 1;
期待される出力:
string[] expected = new string[] {"1", "18446744073709551615"};
解説
1マス目には1粒の穀粒があります。2つ目の出力は常に全64マスの合計であり、指定したマスまでの合計ではありません。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
各マスで前のマスの2倍になるので、求める個数は位置だけで決まる。
ヒント 2
64マス全体の合計は等比数列で、通常の整数範囲をはるかに超える。
ヒント 3
両方の値をそのまま10進文字列で返す。最初のマスは0ではなく1。
目安の計算量
時間 O(1)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。