AIOC Banner

Problem: Vases

Want to try solving this problem? You can submit your code online if you log in or register.


Vases

Input File: vasesin.txt
Output File: vasesout.txt
Time Limit: 1 second
Memory Limit: 1 GB

You have bought N identical flowers to arrange into three vases. As an expert in interior design, there are three important rules you must follow:

  1. Every flower must go into one of the three vases, since throwing flowers away is wasteful.
  2. Each vase must contain at least one flower, since an empty vase looks very odd.
  3. Each vase must contain a different number of flowers, so all the vases look different.

Your task is to determine a possible way to arrange the flowers. Note that there may be multiple possible solutions, or none at all.

Input

The only line of input will contain a single integer: the number of flowers N.

Output

Your program should output three space-separated integers, describing how many flowers to put into each vase. If there are multiple possible ways to arrange the flowers, any will do.

If it is impossible to place flowers according to the rules, print 0 0 0 instead.

Sample Input 1

15

Sample Output 1

4 5 6

Sample Input 2

105

Sample Output 2

100 2 3

Sample Input 3

4

Sample Output 3

0 0 0

Explanation

In the first sample input, you have N = 15 flowers. One way you can arrange the flowers is to put 4 flowers in the first vase, 5 flowers in the second vase and 6 flowers in the third vase. There are other possible solutions.

In the second sample input, you have N = 105 flowers. One way you can arrange the flowers is to put 100 flowers in the first vase, 2 flowers in the second vase and 3 flowers in the third vase. There are other possible solutions.

In the third sample input, you have N = 4 flowers. It is impossible to arrange flowers in vases according to your interior design rules, so the only correct output is 0 0 0.

Subtasks & Constraints

For all cases, 1 ≤ N ≤ 100,000.

 


Privacy statement
© Australian Mathematics Trust 2001-2024

Contact: training@orac.amt.edu.au
Page generated: 28 March 2024,  9:56pm AEDT