結果

問題 No.4 おもりと天秤
ユーザー らっしー(raccy)らっしー(raccy)
提出日時 2014-12-23 11:57:03
言語 Ruby
(3.2.2)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,829 bytes
コンパイル時間 424 ms
コンパイル使用メモリ 11,480 KB
実行使用メモリ 15,344 KB
最終ジャッジ日時 2023-09-02 21:37:20
合計ジャッジ時間 10,930 ms
ジャッジサーバーID
(参考情報)
judge12 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
15,052 KB
testcase_01 AC 80 ms
15,116 KB
testcase_02 AC 83 ms
15,168 KB
testcase_03 AC 78 ms
15,252 KB
testcase_04 AC 80 ms
15,116 KB
testcase_05 AC 82 ms
15,108 KB
testcase_06 AC 82 ms
15,192 KB
testcase_07 AC 81 ms
15,236 KB
testcase_08 AC 80 ms
15,132 KB
testcase_09 AC 82 ms
15,040 KB
testcase_10 AC 81 ms
15,112 KB
testcase_11 AC 81 ms
15,272 KB
testcase_12 AC 84 ms
15,252 KB
testcase_13 AC 82 ms
15,296 KB
testcase_14 AC 79 ms
15,108 KB
testcase_15 AC 82 ms
15,344 KB
testcase_16 AC 80 ms
15,216 KB
testcase_17 AC 81 ms
15,076 KB
testcase_18 TLE -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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