結果

問題 No.15 カタログショッピング
ユーザー 明智重蔵明智重蔵
提出日時 2015-08-02 15:28:51
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 5,631 bytes
コンパイル時間 1,062 ms
コンパイル使用メモリ 116,956 KB
実行使用メモリ 35,456 KB
最終ジャッジ日時 2024-07-18 00:48:14
合計ジャッジ時間 7,743 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
27,520 KB
testcase_01 AC 38 ms
25,776 KB
testcase_02 AC 39 ms
27,824 KB
testcase_03 AC 46 ms
33,688 KB
testcase_04 AC 41 ms
25,868 KB
testcase_05 TLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input6";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 220");
            WillReturn.Add("180");
            WillReturn.Add("220");
            WillReturn.Add("280");
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 150");
            WillReturn.Add("10");
            WillReturn.Add("30");
            WillReturn.Add("40");
            WillReturn.Add("20");
            WillReturn.Add("50");
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("12 348940");
            WillReturn.Add("47250");
            WillReturn.Add("76500");
            WillReturn.Add("9520");
            WillReturn.Add("29960");
            WillReturn.Add("19520");
            WillReturn.Add("70960");
            WillReturn.Add("91390");
            WillReturn.Add("35610");
            WillReturn.Add("71190");
            WillReturn.Add("25840");
            WillReturn.Add("10150");
            WillReturn.Add("35000");
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("15 445566");
            WillReturn.Add("13075");
            WillReturn.Add("16966");
            WillReturn.Add("20695");
            WillReturn.Add("21052");
            WillReturn.Add("25917");
            WillReturn.Add("25917");
            WillReturn.Add("28431");
            WillReturn.Add("31001");
            WillReturn.Add("44064");
            WillReturn.Add("47151");
            WillReturn.Add("59372");
            WillReturn.Add("63934");
            WillReturn.Add("63934");
            WillReturn.Add("66757");
            WillReturn.Add("88888");
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("4 20000");
            WillReturn.Add("10000");
            WillReturn.Add("10000");
            WillReturn.Add("10000");
            WillReturn.Add("10000");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal int CurrP;
        internal int SumPrice;
        internal List<int> SelectedIDList;
    }

    struct SyouhinDef
    {
        internal int ID;
        internal int Price;
    }

    //No.15 カタログショッピング
    static void Main()
    {
        List<string> InputList = GetInputList();
        int S = int.Parse(InputList[0].Split(' ').Last());

        var SyouhinList = new List<SyouhinDef>();
        int wkID = 1;
        foreach (string EachStr in InputList.Skip(1)) {
            SyouhinDef WillAdd;
            WillAdd.ID = wkID++;
            WillAdd.Price = int.Parse(EachStr);
            SyouhinList.Add(WillAdd);
        }

        //合計金額より価格の高い商品をRemove
        SyouhinList.RemoveAll(X => X.Price > S);

        //価格の昇順にソートしておく
        SyouhinDef[] SyouhinArr =
            SyouhinList.OrderBy(X => X.Price).ThenBy(X => X.ID).ToArray();
        int UB = SyouhinArr.GetUpperBound(0);

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        for (int I = 0; I <= UB; I++) {
            WillPush.CurrP = I;
            WillPush.SelectedIDList = new List<int>() { SyouhinArr[I].ID };
            WillPush.SumPrice = SyouhinArr[I].Price;
            stk.Push(WillPush);
        }

        var AnswerList = new List<int[]>();

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            if (Popped.SumPrice == S) {
                AnswerList.Add(Popped.SelectedIDList.OrderBy(X => X).ToArray());
                continue;
            }

            for (int I = Popped.CurrP + 1; I <= UB; I++) {
                WillPush.CurrP = I;
                int CurrPrice = SyouhinArr[I].Price;
                WillPush.SumPrice = Popped.SumPrice + CurrPrice;

                //合計金額を超えるならbreak
                if (S < WillPush.SumPrice) break;

                //合計金額未満で、その金額の2倍を足して、
                //合計金額を超えるならContinue
                if (WillPush.SumPrice < S
                 && S < WillPush.SumPrice + CurrPrice)
                    continue;

                WillPush.SelectedIDList = new List<int>(Popped.SelectedIDList);
                WillPush.SelectedIDList.Add(SyouhinArr[I].ID);

                stk.Push(WillPush);
            }
        }
        //解を出力
        PrintAnswer(AnswerList);
    }

    //解を出力
    static void PrintAnswer(List<int[]> pAnswerList)
    {
        pAnswerList.Sort((A, B) =>
        {
            int MaxUB = Math.Max(A.GetUpperBound(0), B.GetUpperBound(0));
            for (int I = 0; I <= MaxUB; I++) {
                if (I > A.GetUpperBound(0)) return -1;
                if (I > B.GetUpperBound(0)) return 1;
                if (A[I] > B[I]) return 1;
                if (A[I] < B[I]) return -1;
            }
            return 0;
        });

        foreach (int[] EachIntArr in pAnswerList) {
            var sb = new System.Text.StringBuilder();
            for (int I = 0; I <= EachIntArr.GetUpperBound(0); I++) {
                sb.Append(EachIntArr[I]);
                if (I < EachIntArr.GetUpperBound(0))
                    sb.Append(' ');
            }
            Console.WriteLine(sb.ToString());
        }
    }
}
0