【アルゴリズム問題】yukicoder no.15 カタログショッピング byなおさん (level ☆☆☆)
閉じる
閉じる

新しい記事を投稿しました。シェアして読者に伝えましょう

×

【アルゴリズム問題】yukicoder no.15 カタログショッピング byなおさん (level ☆☆☆)

2014-08-18 00:22
    太郎君はカタログショッピングが大好き。

    今日もカタログから商品を選んで購入したのだが、
    太郎君はとてもお金持ちなので適当に商品を選んでしまい、
    何を購入したかいつも忘れてしまいます。

    幸い、クレジットカードの明細は手元にあるので、
    購入した合計金額だけはわかりました。

    太郎君が何を購入したのかを計算し、その商品番号を太郎君に教えてあげてください。
    一つの商品を複数買うのはないとします。

    【入力】
    N S
    P_1
    P_2
    ・・・
    P_N

    【制約】
    1 <= N <= 31 : カタログに載っている商品の数
    1 <= S <= 310000000 : 購入した合計金額
    1 <= Pi <= 10000000 : 商品番号i の金額 (1 <= i <= N)

    【出力】
    購入した商品の商品番号を1行に、昇順で、1つの空白文字区切りで出力してください。
    購入した商品の組み合わせが複数あり得る場合、どれか1つのみ出力すれば良いです。

    【追加得点】
    あり得る組み合わせをすべて過不足無くすべて出力できた場合は追加で+20。
    (順番は問わない)


    【sample1】
    3 220
    180
    220
    280

    【ans1】
    2

    太郎君は3つの商品の中から、2番の商品だけを購入しました。



    【sample2】
    5 150
    10
    30
    40
    20
    50

    【ans2】
    1 2 3 4 5

    太郎君は5つの商品をすべて購入しました。



    【sample3】
    12 348940
    47250
    76500
    9520
    29960
    19520
    70960
    91390
    35610
    71190
    25840
    10150
    35000

    【ans3】
    2 3 4 6 7 8 12



    【sample4】
    15 445566
    13075
    16966
    20695
    21052
    25917
    25917
    28431
    31001
    44064
    47151
    59372
    63934
    63934
    66757
    88888

    【ans4】
    4 5 7 9 10 11 12 14 15
    4 5 7 9 10 11 13 14 15
    4 6 7 9 10 11 12 14 15
    4 6 7 9 10 11 13 14 15

    同じ値段の商品が複数存在する場合があります。
    あり得る4つの組み合わせのうち、いずれか1つを出力できれば良いです。



    【sample5】
    4 20000
    10000
    10000
    10000
    10000

    【ans5】
    1 2
    1 3
    1 4
    2 3
    2 4
    3 4

    すべて同じ値段なので、どれか2つを購入したようです。
    6つの組み合わせのうち、いずれも正解です。


    【本入力】

    https://gist.githubusercontent.com/yuki2006/faa728a91cd08ed594e5/raw/9a7c733938e545b9e283af762935e72688d78d7a/yukicoder15.txt



    ヒント:半分全列挙

    1st. くろとんさん C++
    http://ideone.com/xnEvlK

    haskell回答
    http://ideone.com/pKpZNc

    2nd.scacheさん Java
    http://ideone.com/9greN9


    3nd.ヒロソフさん C
    https://gist.github.com/HiroSof/471950287230e25c799c
    (TLEですが、深さ優先探索で回答)
    広告
    コメントを書く
    コメントをするには、
    ログインして下さい。