首页 > 代码库 > HDU 4982 Goffi and Squary Partition
HDU 4982 Goffi and Squary Partition
Goffi and Squary Partition
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 856 Accepted Submission(s): 50
Problem Description
Recently, Goffi is interested in squary partition of integers.
A set X of k distinct positive integers is called squary partition of n if and only if it satisfies the following conditions:
For example, a set {1, 5, 6, 10} is a squary partition of 22 because 1 + 5 + 6 + 10 = 22 and 1 + 5 + 10 = 16 = 4 × 4.
Goffi wants to know, for some integers n and k, whether there exists a squary partition of n to k distinct positive integers.
A set X of k distinct positive integers is called squary partition of n if and only if it satisfies the following conditions:
- the sum of k positive integers is equal to n
- one of the subsets of X containing k−1 numbers sums up to a square of integer.
For example, a set {1, 5, 6, 10} is a squary partition of 22 because 1 + 5 + 6 + 10 = 22 and 1 + 5 + 10 = 16 = 4 × 4.
Goffi wants to know, for some integers n and k, whether there exists a squary partition of n to k distinct positive integers.
Input
Input contains multiple test cases (less than 10000). For each test case, there‘s one line containing two integers n and k (2≤n≤200000,2≤k≤30).
Output
For each case, if there exists a squary partition of n to k distinct positive integers, output "YES" in a line. Otherwise, output "NO".
Sample Input
2 24 222 4
Sample Output
NOYESYES
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> using namespace std;#define _int64 long longint main(){ int n,k,tmp,sum,rem,b1,i; while (scanf("%d%d",&n,&k)!=EOF) { sum=(k*(k-1)/2);
//假设这个序列是从1到k-1的
//此处记录1到k-1的和 b1=0;
//flag for (i=1;i*i<n;i++) { rem=n-i*i; tmp=i*i; if (tmp<sum) continue; if ((rem<=k-1)&&(tmp-sum<k-rem)) continue; //if ((tmp==sum)&&(rem<=k-1)) continue; if ((tmp==sum+1)&&(rem==k)) continue; b1=1; //cout<<i<<endl; break; } if (b1==1) printf("YES\n"); else printf("NO\n"); } return 0;}
HDU 4982 Goffi and Squary Partition
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。