結果

問題 No.15 カタログショッピング
ユーザー 明智重蔵明智重蔵
提出日時 2015-08-02 15:38:50
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 6,052 bytes
コンパイル時間 1,156 ms
コンパイル使用メモリ 118,664 KB
実行使用メモリ 29,600 KB
最終ジャッジ日時 2024-07-18 00:48:18
合計ジャッジ時間 2,247 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 43 ms
25,652 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 = "Input4";

    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);

        //下限値枝切り用
        int[] RestPriceSumArr = new int[SyouhinArr.Length];
        int PriceSum = SyouhinArr.Sum(X => X.Price);
        for (int I = 0; I <= RestPriceSumArr.GetUpperBound(0); I++) {
            RestPriceSumArr[I] = PriceSum;
            PriceSum -= SyouhinArr[I].Price;
        }

        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++) {
                //下限値枝切り
                if (Popped.SumPrice + RestPriceSumArr[I] < S) break;

                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