|
I I U C O N L I N E C O N T E S T 2 0 0 8 |
|
|
Problem H: Binary*3 Type Multiple |
|
|
Input: standard input |
|
|
|
|
|
Mahbub thinks that he has found something interesting but he is not sure whether he is right or not. For each integer he seems to find a multiple of it such that it is only composed of 3s and 0s. Can you help him?
You will be given a positive integer K. You have to find a positive multiple of K which is only composed of 3s and 0s. And in addition to this, the digits of that multiple have to be in non-increasing order. If there are more than one such multiple you have to choose the one which is shortest in length. Even after this if more than one multiple remain then you should choose the lexicographically largest one.
For example, For K = 4, our desired multiple is 300. For K = 7, it is 333333. And for K = 14, it will be 3333330.
|
|
|
Input |
|
|
The input consists of several lines containing one positive integer K.
|
|
|
Output |
|
|
Your code should produce one line of output containing space separated 3 integers. First integer is the length of the multiple, second integer number of 3s in the multiple and third integer number of 0s in your multiple.
|
|
|
Constraints |
|
|
- K ≤ 1000000
|
|
|
Sample Input |
Sample Input |
|
4 7 14 |
4 7 14 |
|
|
|
|
Problem setter: Md. Mahbubul Hasan Special thanks to: Abduallah Al Mahmud Source: BdOI Warmup |
|