prithivMLmods/Coder-Stat

1 2 3 4<H1>ジグザグ数 (Zig-Zag Numbers)  </H1>5 6 7 8<h2>  問題</h2>9<p>10正の整数を (先頭に 0 をつけずに) 10 進法で書いて桁の数字を順番に見ていくと増加と減少を交互に繰り返しているとき，その数は「ジグザグ数」であると呼ぶことにしよう．たとえば，2947 は桁の数字が 2 → 9 → 4 → 7 と，増加 → 減少 → 増加 の順になっているのでジグザグ数である．また，71946 は 減少 → 増加 → 減少 → 増加 の順なのでジグザグ数である．一方，123 や 71446 や 71442 や 88 はジグザグ数ではない．なお，1 桁の正の整数はジグザグ数であると考えることとする．11</p>12 13<p>14A 以上 B 以下の M の倍数のうち，ジグザグ数の個数を 10000 で割った余りを求めるプログラムを作成せよ．15</p>16 17<h2>  入力</h2>18<p>19入力は 3 行からなり，1 行に 1 つずつ正の整数が書かれている．20</p>21 22<p>231 行目の整数は A を，2 行目の整数は B を，3 行目の整数は M を表す．これらは 1 ≦ A ≦ B ≦ 10<sup>500</sup>，1 ≦ M ≦ 500 を満たす．24</p>25 26<p>27※ A や B の値は，通常の整数を表すデータ型には収まらない可能性があることに注意せよ．28</p>29 30<h2>  出力</h2>31<p>32A 以上 B 以下の M の倍数のうち，ジグザグ数の個数を 10000 で割った余りを 1 行で出力せよ．33</p>34 35<h2>  入出力例</h2>36 37<h3>入力例 1</h3>38 39  <pre>401004120042543</pre>44 45<h3>出力例 1</h3>46 47   <pre>481349</pre>50 51<p>52入出力例 1 において，100 以上 200 以下の 5 の倍数であるジグザグ数は，105, 120, 130, 140, 150, 160, 165, 170, 175, 180, 185, 190, 195 の 13 個である．53</p>54 55 56<h3>入力例 2</h3>  57 58  <pre>59660123456761362</pre>63 64<h3>出力例 2</h3>65 66<pre>6724668</pre>69 70 71<p>72入出力例 2 において，6 以上 1234567 以下の 3 の倍数であるジグザグ数は 50246 個あるので，それを 10000 で割った余りである 246 を出力する．73</p>74 75 76<div class="source">77<p class="source">78問題文と自動審判に使われるデータは、<a href="http://www.ioi-jp.org">情報オリンピック日本委員会</a>が作成し公開している問題文と採点用テストデータです。79</p>80</div>81