539

# 题目

## Description

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?

## Input

The first line of the input contains a single integer n (1 ≤ n ≤ 109) — Kolya's initial game-coin score.

## Output

Print "YES" (without quotes) if it's possible that Kolya spent all of his initial n coins buying only houses, cars and computers. Otherwise print "NO" (without quotes).

1359257

YES

17851817

NO

# 题解

dp[i]表示i是否满足
dp[i-1234]dp[i-123456]dp[i-1234567]中有任一个满足，则dp[i]满足

1~1000000000输出发现:n >= 27406118时，所有的都是YES

# 代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！

*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
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("%d",&n) == EOF)
return false;

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

return true;
}

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

• 点击查看/关闭被识别为广告的评论