結果

問題 No.3658 Darumaka Number 2
コンテスト
ユーザー tomerun
提出日時 2026-08-30 14:09:09
言語 Crystal
(1.21.0)
コンパイル:
crystal build -Donline_judge -o a.out --release --no-debug _filename_
実行:
./a.out
結果
AC  
実行時間 354 ms / 2,000 ms
+ 818µs
コード長 603 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 10,938 ms
コンパイル使用メモリ 338,052 KB
実行使用メモリ 7,284 KB
最終ジャッジ日時 2026-08-30 14:09:34
合計ジャッジ時間 17,026 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n = read_line.chars.map(&.to_i)
cand = Array.new(n.size, 4)
if n < cand
  puts "5" * (n.size - 1)
  exit
end
cand.fill(5)
if cand <= n
  puts cand.join
  exit
end
lo = Array.new(n.size, 0)
hi = Array.new(n.size, 1)
mid = Array.new(n.size + 1, 0)
1000.times do |turn|
  carry = 0
  n.size.times do |i|
    carry += lo[i] + hi[i]
    mid[i] = carry % 2
    if i > 0
      cand[-i] = carry % 2 == 0 ? 4 : 5
    end
    carry //= 2
  end
  mid[n.size] = carry
  cand[0] = carry == 0 ? 4 : 5
  if cand <= n
    lo = mid[1..]
  else
    hi = mid[1..]
  end
end
puts lo.map { |v| v == 0 ? 4 : 5 }.reverse.join
0