結果

問題 No.47 ポケットを叩くとビスケットが２倍
コンテスト
ユーザー Takuya Ito
提出日時 2022-12-17 18:14:40
言語 TypeScript
(5.7.2)
結果
AC  
実行時間 69 ms / 5,000 ms
コード長 2,487 bytes
コンパイル時間 8,740 ms
コンパイル使用メモリ 229,220 KB
実行使用メモリ 39,680 KB
最終ジャッジ日時 2024-12-31 16:48:37
合計ジャッジ時間 10,879 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

function Main(input: string): void {
  // 最終的に実現するビスケットの数
  const target = parseInt(input);

  // 最終的に実現するビスケットの数に対して、法則性を確認する

  // <1>targetが 2の2乗 より大きく 2の3乗 以下の場合は、3回叩くことで実現できるのか
  // <2>targetが 2の3乗 より大きく 2の4乗 以下の場合は、4回叩くことで実現できるのか
  // この<1><2>が成立するのであれば、それ以外のtargetの取る値の範囲においても同様だと言えるはず。

  // <1> 2^2(4) < target <= 2^3(8) なら、3回で全て実現できるのか : 実現できる
  // - 5枚にする場合 : 1*2 -> (2-2)+ 2*2 -> (4-1)+1*2 = 5
  // - 6枚にする場合 : 1*2 -> (2-2)+ 2*2 -> (4-2)+2*2 = 6
  // - 7枚にする場合 : 1*2 -> (2-2)+ 2*2 -> (4-3)+3*2 = 7
  // - 8枚にする場合 : 1*2 -> (2-2)+ 2*2 -> (4-4)+4*2 = 8

  // <上の数式について説明>
  // 例えば5枚にしたい場合、下記のような手順を踏むことになる。上の数式（っぽいもの）ではこれを表現している。
  // - 最初の1枚を叩いて2倍に : 計1枚 * 2倍 = 計2枚
  // - 計2枚すべてを叩いて2倍に : 計2枚 * 2倍 = 計4枚
  // - 計4枚のうち、1枚だけを叩いて2倍に : (計4枚 - 1枚抜く) + 抜いた1枚 * 2倍 = 計5枚

  // <2> 2^3(8) < target <= 16(2^4)なら、4回で全て実現できるのか : 実現できる
  // -  9枚にする場合 : 1*2 -> (2-2)+ 2*2 -> (4-4)+4*2 -> (8-1)+1*2= 9
  // - 10枚にする場合 : 1*2 -> (2-2)+ 2*2 -> (4-4)+4*2 -> (8-2)+2*2= 10
  // - 11枚にする場合 : 1*2 -> (2-2)+ 2*2 -> (4-4)+4*2 -> (8-3)+3*2= 11
  // - 12枚にする場合 : 1*2 -> (2-2)+ 2*2 -> (4-4)+4*2 -> (8-4)+4*2= 12
  // - 13枚にする場合 : 1*2 -> (2-2)+ 2*2 -> (4-4)+4*2 -> (8-5)+5*2= 13
  // - 14枚にする場合 : 1*2 -> (2-2)+ 2*2 -> (4-4)+4*2 -> (8-6)+6*2= 14
  // - 15枚にする場合 : 1*2 -> (2-2)+ 2*2 -> (4-4)+4*2 -> (8-7)+7*2= 15
  // - 16枚にする場合 : 1*2 -> (2-2)+ 2*2 -> (4-4)+4*2 -> (8-8)+8*2= 16

  // つまり求めるものは、targetが2の何乗以下なのか
  // 問題の要件よりtargetは 10**8 以下なので、2のべき乗で言うと 2**27 以下まで精査すれば良い
  for (let count = 0; count <= 27; count++) {
    if (target <= 2 ** count) {
      console.log(count);
      break;
    }
  }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));
0