結果
問題 | No.41 貯金箱の溜息(EASY) |
ユーザー |
![]() |
提出日時 | 2016-11-02 05:23:22 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 78 ms / 5,000 ms |
コード長 | 1,042 bytes |
コンパイル時間 | 4,381 ms |
コンパイル使用メモリ | 110,960 KB |
実行使用メモリ | 27,400 KB |
最終ジャッジ日時 | 2024-11-25 01:23:35 |
合計ジャッジ時間 | 1,629 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 |
コンパイルメッセージ
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;using System.Text;using System.Threading.Tasks;class Magatro{const int MAX = 100000;static int T = int.Parse(Console.ReadLine());const int MOD = 1000000009;static int[,] dp = new int[10, MAX+1];static void Main(){Calc();for (int i = 0; i < T; i++){long M = long.Parse(Console.ReadLine());Console.WriteLine(cnt(M));}}static long cnt(long m){long c = m / 111111;long ret = 0;ret = dp[9, c];return ret;}static void Calc(){for(int i = 0; i < MAX; i++){dp[0, i] = 1;}for(int i = 1; i <= 9; i++){for(int j = 0; j <= MAX; j++){dp[i, j] = dp[i - 1, j];if (j >= i){dp[i, j] = (dp[i, j] + dp[i, j - i]) % MOD;}}}}}