首页 > 代码库 > 【HDOJ】4982 Goffi and Squary Partition
【HDOJ】4982 Goffi and Squary Partition
题意就是整数划分,选出和为n的K个整数,其中K-1个数的和为完全平方数S。
选择整数时需要从1,2,3..连续选择,当选择整数与n-S相等时,需要跳过n-S,即选择n-S+1。
如此选择K-2个数,从而可确定第K-1个数,若该数已经出现(小于或等于K-2),则划分失败;
若第K-1个数不等于n-S,则肯定划分成功,否则K-1个数若等于n-S。
即需要通过将第K-2个数+1,同时第K-1个数-1得到正确的划分,并且需要保证调整后第K-2个数仍小于第K-1个数,因此,两数之间的距离至少大于2。
1 #include <cstdio> 2 #include <cmath> 3 4 int n, k; 5 6 bool judge(int s) { 7 int p, q; 8 int i, j = 0, sum = 0, tmp; 9 10 p = s*s;11 if (n == p)12 return false;13 q = n-p;14 15 for (i=1; i<=k-2; ++i) {16 ++j;17 if (j == q)18 ++j;19 sum += j;20 }21 if (sum >= p)22 return false;23 tmp = p - sum;24 if (tmp <= j)25 return false;26 if (tmp == q) {27 if (q <= j+2)28 return false;29 }30 return true;31 }32 33 int main() {34 int m;35 36 while (scanf("%d %d", &n, &k) != EOF) {37 m = sqrt((n-1)*1.0);38 39 if (judge(m))40 printf("YES\n");41 else42 printf("NO\n");43 }44 45 return 0;46 }
【HDOJ】4982 Goffi and Squary Partition
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。