結果

問題 No.15 カタログショッピング
ユーザー letrangerjpletrangerjp
提出日時 2017-05-27 01:38:40
言語 Ruby
(3.3.0)
結果
AC  
実行時間 222 ms / 5,000 ms
コード長 691 bytes
コンパイル時間 55 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 30,848 KB
最終ジャッジ日時 2024-09-19 20:13:31
合計ジャッジ時間 2,075 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
12,032 KB
testcase_01 AC 84 ms
12,160 KB
testcase_02 AC 76 ms
12,160 KB
testcase_03 AC 76 ms
12,032 KB
testcase_04 AC 76 ms
12,160 KB
testcase_05 AC 215 ms
30,720 KB
testcase_06 AC 216 ms
30,720 KB
testcase_07 AC 213 ms
30,848 KB
testcase_08 AC 214 ms
30,848 KB
testcase_09 AC 222 ms
30,592 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

def f(n, s, a)
  latter_a = a.dup
  first_a = latter_a.shift(n/2)

  g = lambda{|i, sum, a, rr, h|
    h[sum] ||= []
    h[sum] << rr
    (i...a.size).each{|ii|
      g.(ii + 1, sum + a[ii], a, rr + [ii], h)
    }
    h
  }
  firsts = g.(0, 0, first_a, [], {})
  latters = g.(0, 0, latter_a, [], {})

  r = []
  firsts.each{|f_sum, f_a|
    if latters.key?(s - f_sum)
      l_a = latters[s - f_sum].map{|a| a.map{|i|first_a.size + i}}
      f_a.product(l_a).each{|a|
        r << a.flatten
      }
    end
  }
  # p [first_a, latter_a]
  # p [firsts, latters]
  r.map{|v|v.map(&:succ)}.sort
end

N, S = gets.split.map(&:to_i)
P = N.times.map{gets.to_i}

f(N, S, P).each{|a|
  puts a * " "
}
0