题目链接:4596 Yet another end of the world
题目大意:给定若干组x,y,z,问是否能找到一个整数d,使得至少两组x,y,z满足y≤d%x≤z。
解题思路:首先枚举出两组x,y,z。
然后判断这两组是否能找到一个d,使得满足题目条件。
现在假设a、b,有a*x1+y1≤d≤a*x1+z1和b*x2+y2≤d≤b*x2+z2;
若两段区间有交集,必有a*x1+y1≤b*x2+z2且b*x2+y2≤a*x1+z1;
化简得a*x1-b*x2≤z2-y1 且a*x1-b*x2≥y2-z1;
若a,b有整数解,根据拓展欧几里得定理ax1+bx2=u有整数解的情况为u/gcd(x1,x2)==0;
所以若存在y2-z1≤u≤z2-y1,使得u/gcd(x1,x2)==0即可。
#include <stdio.h>
#include <string.h>
const int N = 1005;
int n, x[N], y[N], z[N];
int gcd (int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
bool judge (int t, int a, int b) {
if (a % t == 0 || b % t == 0) return true;
if (a < 0 && b > 0) return true;
if (b/t - a/t >= 1) return true;
return false;
}
bool solve () {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int t = gcd(x[i], x[j]);
if (judge(t, y[j]-z[i], z[j]-y[i])) return false;
}
}
return true;
}
int main () {
while (scanf("%d", &n) == 1) {
for (int i = 0; i < n; i++)
scanf("%d%d%d", &x[i], &y[i], &z[i]);
printf("%s\n", solve () ? "Can Take off" : "Cannot Take off");
}
return 0;
}
分享到:
相关推荐
The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases. In each test case, there are two integers k,m(1≤k≤1018,1≤m≤100). Output For each test case, print ...
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
【项目资源】: 包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。 ... 【项目质量】: 所有源码都经过严格测试,...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
HDU最全ac代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu动态规划算法集锦