#P11204. Stick Partition into Triangles

    ID: 13271 Type: Default 1000ms 256MiB

Stick Partition into Triangles

Stick Partition into Triangles

She is given a wooden stick of length \(m\) and wishes to have it divided into \(n\) small sticks such that:

  • Each small stick has a positive integer length; and
  • Any three of the small sticks can form a triangle when connected end‐to‐end (i.e. they satisfy the triangle inequality).

Recall that three positive lengths \(a\), \(b\), \(c\) (arranged in non-decreasing order \(a \le b \le c\)) can form a triangle if and only if \(a+b>c\).

Your task is to determine whether such a partition is possible.

Additional observations:

  • For \(n=3\), the only triple is the entire partition and the triangle condition reduces to choosing three positive integers summing to \(m\) with the largest less than the sum of the other two. It turns out that one valid construction is often possible except for the case \(m=4\) (since the only partition is \(1,1,2\) which does not form a triangle).
  • For \(n \ge 4\), if any two sticks are very small then they might cause a violation when paired with a larger stick. In fact, one can prove that a necessary and sufficient condition in this case is that all the small sticks are equal. Thus, for \(n\ge4\) a valid partition exists if and only if \(m\) is divisible by \(n\) (and of course \(m\ge n\)).

Input Note: You may assume that \(m\) and \(n\) are such that \(m\ge n\) and \(n\ge3\) in the test cases.

inputFormat

The input consists of a single line containing two integers \(m\) and \(n\) separated by a space.

\(m\) denotes the length of the stick and \(n\) the number of parts to split into.

outputFormat

Output a single line containing the string YES if it is possible to partition the stick meeting the above conditions, and NO otherwise.

sample

3 3
YES