AOJ 834.买买买

173


题目


点击显/隐题目

一天Alice打开了她日常玩的游戏,发现她里面还有n个游戏币,她想把这些游戏币花光。
现在可以买的一共三种道具,分别是房子(每一个价值1234567个游戏币),车子(每一个价值123456个游戏币),电脑(每一个价值1234个游戏币)。
现在她想知道,通过买这三种道具是否可以把n个游戏币全部花光。





第一行,一个数字t(1<=t<=100)。代表测试数据数量。
对于每一组测试数据,一个整数n(1<=n<=1000000000),代表现在的游戏币。





输出n行,每行输出"YES"或者"NO",表示她可以或者不可以把游戏币全部花光。





2
1359257
17851817





YES
NO





题解



由于最大的值非常大,如果直接 dfs 会非常慢
而且打表的文件会非常大

而看 12345671000000000 其实差别不是很大
除一下发现最多也就能买 800 多套房子
而即使全部买成汽车也就能买 8000 多辆
乘起来的数据量只有 10e6 完全是可以遍历的
也就是说,只需要枚举房子和车的数量,然后判断剩下的钱能不能整除电脑

这样做不超时的原因是房子和车的价格都非常大,可以将许多数据“跨越”掉
如果这数都很小的话,就没有办法了


代码


点击显/隐代码
`cpp 买买买 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
//*/
#define debug
#include
//*/
#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;

int price[] = {1234567,123456,1234};

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.syncwithstdio(false);

int T;
cin >> T;
while(T--){
LL n;
cin >> n;
bool flag = false;

int max_fz = n / price[0];
for(int i=0;i<=max_fz;i++){
int maxcz = (n-iprice[0]) / price[1];
for(int j=0;j<=max_cz;j++)
if(!((n-iprice[0]-jprice[1]) % price[2])){
flag = true;
break;
}
}
cout << (flag?"YES":"NO") << endl;
}

#ifdef debug
printf("Time:%.3fs.n", double(clock() - START) / CLOCKSPERSEC);
#endif
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论