結果

問題 No.4 おもりと天秤
コンテスト
ユーザー らっしー(raccy)
提出日時 2014-12-23 11:57:03
言語 Ruby
(3.4.1)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,829 bytes
コンパイル時間 349 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 20,512 KB
最終ジャッジ日時 2024-06-12 03:52:38
合計ジャッジ時間 9,156 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 TLE * 1 -- * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

# coding: utf-8
# おもりのリストのクラス
class Omoris
  # 初期化時にソートする。
  def initialize(list)
    @list = list.sort
  end

  # おもりの合計を返す。
  def sum
    @list.inject {|sum, i| sum + i}
  end

  # end番目以前の組み合わせで合計がtargetになるか？
  def check(target, last)
    # 0なら合致しているのでOK
    return true if target == 0
    # 最後の前まで調べる。
    (1..last).to_a.reverse.each do |i|
      if i < last && @list[i + 1] == @list[i]
        # 2回目以降で前と一緒なら調べる必要なし。
        next
      elsif target < @list[i]
        # 越えちゃったので次を調べる。
        next
      else
        # 少ないときはtargetから今の分を減らして、さらにcheckする。
        if check(target - @list[i], i - 1)
          # 合致したのでOK。
          return true
        else
          # あわなくても次を調べる。
          next
        end
      end
    end
    # 1番最初の時を調べる。
    if target == @list[0]
      return true
    else
      return false
    end
  end

  # 重りのインデックス
  def [](index)
    @list[index]
  end

  # 重りの数
  def size
    @list.size
  end
end

# 1行目はRubyでは不要。
gets
# 数字のリストを取得。
omoris = Omoris.new(gets.split.map(&:to_i))
sum = omoris.sum
# 合計が偶数で無いと組み合わせは無い。
# 2個以上重りが無いと組み合わせは無い。
# 一番大きい重りが半分以下で無いと組み合わせは無い。
# 合計の半分の組み合わせをチェックする。
if sum.even? &&
    omoris.size > 1 &&
    omoris[-1] <= sum / 2 &&
    omoris.check((sum / 2 - omoris[-1]), omoris.size - 2)
  puts "possible"
else
  puts "impossible"
end
0