首页 > 代码库 > HDOJ 4982 Goffi and Squary Partition

HDOJ 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): 374    Accepted Submission(s): 145


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:
[ol]
  • 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.[/ol]
    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 \le n \le 200000, 2 \le k \le 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 2 4 2 22 4
     

    Sample Output
    NO YES YES
     

    Source
    BestCoder Round #6
     



    <script src="https://code.csdn.net/snippets/457806.js" type="text/javascript"></script>


    HDOJ 4982 Goffi and Squary Partition