結果
問題 | No.115 遠足のおやつ |
ユーザー | 明智重蔵 |
提出日時 | 2015-08-15 05:27:28 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 393 ms / 5,000 ms |
コード長 | 3,737 bytes |
コンパイル時間 | 2,505 ms |
コンパイル使用メモリ | 106,880 KB |
実行使用メモリ | 30,976 KB |
最終ジャッジ日時 | 2023-08-31 00:35:02 |
合計ジャッジ時間 | 9,597 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 64 ms
21,816 KB |
testcase_01 | AC | 85 ms
22,772 KB |
testcase_02 | AC | 89 ms
24,680 KB |
testcase_03 | AC | 65 ms
21,944 KB |
testcase_04 | AC | 282 ms
29,608 KB |
testcase_05 | AC | 86 ms
24,624 KB |
testcase_06 | AC | 87 ms
24,812 KB |
testcase_07 | AC | 88 ms
22,684 KB |
testcase_08 | AC | 65 ms
21,856 KB |
testcase_09 | AC | 65 ms
21,852 KB |
testcase_10 | AC | 66 ms
23,908 KB |
testcase_11 | AC | 64 ms
23,892 KB |
testcase_12 | AC | 65 ms
21,800 KB |
testcase_13 | AC | 86 ms
20,692 KB |
testcase_14 | AC | 92 ms
22,552 KB |
testcase_15 | AC | 193 ms
28,996 KB |
testcase_16 | AC | 260 ms
29,220 KB |
testcase_17 | AC | 130 ms
24,716 KB |
testcase_18 | AC | 64 ms
19,908 KB |
testcase_19 | AC | 89 ms
24,696 KB |
testcase_20 | AC | 91 ms
24,756 KB |
testcase_21 | AC | 65 ms
21,972 KB |
testcase_22 | AC | 142 ms
28,856 KB |
testcase_23 | AC | 92 ms
24,752 KB |
testcase_24 | AC | 130 ms
28,880 KB |
testcase_25 | AC | 123 ms
24,656 KB |
testcase_26 | AC | 99 ms
22,524 KB |
testcase_27 | AC | 111 ms
24,668 KB |
testcase_28 | AC | 100 ms
24,692 KB |
testcase_29 | AC | 110 ms
22,660 KB |
testcase_30 | AC | 134 ms
28,784 KB |
testcase_31 | AC | 100 ms
22,644 KB |
testcase_32 | AC | 212 ms
24,820 KB |
testcase_33 | AC | 89 ms
22,760 KB |
testcase_34 | AC | 276 ms
29,748 KB |
testcase_35 | AC | 126 ms
24,676 KB |
testcase_36 | AC | 123 ms
24,812 KB |
testcase_37 | AC | 222 ms
26,908 KB |
testcase_38 | AC | 393 ms
30,976 KB |
testcase_39 | AC | 392 ms
29,016 KB |
testcase_40 | AC | 65 ms
23,884 KB |
testcase_41 | AC | 65 ms
21,852 KB |
testcase_42 | AC | 87 ms
22,768 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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("10 9 3"); //1 2 6 //ルールを満たす御菓子の組み合わせは //(1円,2円,6円) //(1円,3円,5円) //(2円,3円,4円) //の3つがありますが、 //このうち辞書順が最小になる(1円,2円,6円)の組み合わせが答えになります。 } else if (InputPattern == "Input2") { WillReturn.Add("10 9 4"); //-1 //残念ながら直樹くんは御菓子を買うことができませんでした・・・ } else if (InputPattern == "Input3") { WillReturn.Add("30 40 4"); //1 2 7 30 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static void Main() { List<string> InputList = GetInputList(); int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray(); int N = wkArr[0]; int D = wkArr[1]; int K = wkArr[2]; //[御菓子の数,金額合計]までの辞書式最小パスの2次元配列 string[,] CurrDP = new string[K + 1, D + 1]; string[,] PrevDP = new string[K + 1, D + 1]; PrevDP[0, 0] = ""; //初期化 string AnswerPath = null; for (int LoopN = 1; LoopN <= N; LoopN++) { Array.Copy(PrevDP, CurrDP, PrevDP.Length); for (int LoopK = 0; LoopK <= K - 1; LoopK++) { for (int LoopD = 0; LoopD <= D; LoopD++) { if (PrevDP[LoopK, LoopD] == null) continue; int NewIndK = LoopK + 1; int NewIndD = LoopD + LoopN; if (NewIndD > D) continue; string NewPath = PrevDP[LoopK, LoopD] + " " + LoopN.ToString().PadLeft(3, '0'); if (CurrDP[NewIndK, NewIndD] == null || CurrDP[NewIndK, NewIndD].CompareTo(NewPath) > 0) { CurrDP[NewIndK, NewIndD] = NewPath; } } } //Console.WriteLine(new string('■',15)); //Console.WriteLine("{0}円の御菓子までのDPの結果", LoopN); //PrintDP(CurrDP); //辞書順最小パスの更新 if (CurrDP[K, D] != null) { AnswerPath = CurrDP[K, D]; } Array.Copy(CurrDP, PrevDP, CurrDP.Length); } if (AnswerPath != null) { int[] AnswerIntArr = AnswerPath.Trim().Split(' '). Select(X => int.Parse(X)).ToArray(); string[] AnswerStrArr = Array.ConvertAll(AnswerIntArr, X => X.ToString()); Console.WriteLine(string.Join(" ", AnswerStrArr)); } else Console.WriteLine(-1); } static void PrintDP(string[,] pCurrDP) { var sb = new System.Text.StringBuilder(); for (int LoopK = 0; LoopK <= pCurrDP.GetUpperBound(0); LoopK++) { for (int LoopD = 0; LoopD <= pCurrDP.GetUpperBound(1); LoopD++) { if (pCurrDP[LoopK, LoopD] == null) continue; sb.AppendFormat("{0}個で{1}円の辞書順最小パスは{2}", LoopK, LoopD, pCurrDP[LoopK, LoopD]); sb.AppendLine(); } } Console.WriteLine(sb.ToString()); } }