<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
Kolya is developing an economy simulator game. His most favourite part of the development process is in-game testing. Once he was entertained by the testing so much, that he found out his game-coin score become equal to 0.
Kolya remembers that at the beginning of the game his game-coin score was equal to n and that he have bought only some houses (for 1 234 567 game-coins each), cars (for 123 456 game-coins each) and computers (for 1 234 game-coins each).
Kolya is now interested, whether he could have spent all of his initial n game-coins buying only houses, cars and computers or there is a bug in the game. Formally, is there a triple of non-negative integers a, b and c such that a × 1 234 567 + b × 123 456 + c × 1 234 = n?
Please help Kolya answer this question.
</blockquote>

<h2 id="input">Input</h2>
<blockquote>
The first line of the input contains a single integer n (1 ≤ n ≤ 109) — Kolya's initial game-coin score.
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
Print &quot;YES&quot; (without quotes) if it's possible that Kolya spent all of his initial n coins buying only houses, cars and computers. Otherwise print &quot;NO&quot; (without quotes).
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
<h3 id="input-1">Input</h3>
<blockquote>
1359257
</blockquote>
<h3 id="output-1">Output</h3>
<blockquote>
YES
</blockquote>
<h3 id="input-2">Input</h3>
<blockquote>
17851817
</blockquote>
<h3 id="output-2">Output</h3>
<blockquote>
NO
</blockquote>
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
暴力模拟妥妥的超时 
换用动态规划
<code>dp[i]</code>表示i是否满足 
当<code>dp[i-1234]</code>、<code>dp[i-123456]</code>、<code>dp[i-1234567]</code>中有任一个满足，则<code>dp[i]</code>满足
初始化<code>dp[0]=0</code>
由于<code>n</code>最大为<code>1000000000</code>,仍然是一个非常大的数字 
仅仅打表就需要3、4秒 
因此应该进一步优化
把<code>1~1000000000</code>输出发现:当<code>n &gt;= 27406118</code>时，所有的都是<code>YES</code> 
因此我们的计算量又小了一个数量级。
这时再打表可以瞬间输出答案
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
#include &lt;set&gt;
#include &lt;functional&gt;
using namespace std;

const long long A = 1234567;
const long long B = 123456;
const long long C = 1234;

const int maxn = 27406118;
bool dp[maxn];


bool Do() {

 int n;
 bool OK = false;

 if(scanf(&#34;%d&#34;,&amp;n) == EOF)
 return false;

 

 /*for(long long i = 0;(i*C &lt;= n) &amp;&amp; !OK;i++) {
 for(long long j = 0;(i*C + j*B &lt;= n) &amp;&amp; !OK;j++) {
 for(long long k = 0;(i*C + j*B + k*A &lt;= n) &amp;&amp; !OK;k++) {
 if(i*C + j*B + k*A == n) {
 OK = true;
 printf(&#34;%lld %lld %lld \n&#34;,i,j,k);
 }
 }
 }
 }*/
 if(n&gt;=maxn||dp[n])
 printf(&#34;YES\n&#34;);
 else
 printf(&#34;NO\n&#34;);

 return true;
}

int main() {
 memset(dp,false,sizeof(dp));
 dp[0] = true;
 for(int i = 1;i &lt; maxn;i++) {
 if((i - A &gt;= 0 &amp;&amp; dp[i - A]) || (i - B &gt;= 0 &amp;&amp; dp[i - B]) || (i - C &gt;= 0 &amp;&amp; dp[i - C]))
 dp[i] = true;
 }
 while(Do());
 return 0;
}
</pre>

Codeforces 681B.Economy Game