A number is called quasibinary if its decimal representation contains only digits 0 or…
- User
A number is called quasibinary if its decimal representation contains only digits 0 or 1. For example, numbers 0, 1, 101, 110011 — are quasibinary and numbers 2, 12, 900 are not.
You are given a positive integer n. Represent it as a sum of minimum number of quasibinary numbers. Input
The first line contains a single integer n (1 ≤ n ≤ 106).
Output
In the first line print a single integer k — the minimum number of numbers in the representation of number n as a sum of quasibinary numbers.
In the second line print k numbers — the elements of the sum. All these numbers should be quasibinary according to the definition above, their sum should equal n. Do not have to print the leading zeroes in the numbers. The order of numbers doesn't matter. If there are multiple possible representations, you are allowed to print any of them.
Examples
Input
9
Output
9 1 1 1 1 1 1 1 1 1
Input
32
Output
3 10 11 11
Assistant
We need to solve: Given n (1 to 10^6), represent as sum of minimum number of quasibinary numbers (digits 0 or 1). We need to output the minimum k and the numbers.
Observation: A quasibinary number is a number with digits only 0 or 1. For example, 101, 11, 10, 1, 0 etc.
We want to partition n into sum of such numbers with minimal count.
This is a known problem: Codeforces 538B - Quasi Binary. The standard solution: The minimal number of quasibinary numbers needed is equal to the maximum digit of n in decimal representation. Because each quasibinary number contributes at most 1 to each digit place when added (since digits are 0 or 1, and sum of numbers yields digits possibly with carry? Wait: When we add numbers, there can be carries. But we are summing numbers without carries? Actually the sum of numbers is standard addition, so digits may produce carries. But the idea is to construct numbers such that at each digit position, we use as many 1s as the digit value, but limited to the maximum digit. For example, n = 9 => digits: 9. So we need at least 9 quasibinary numbers because each quasibinary number can contribute at most 1 to that digit place (since they are 0 or 1). However, carries from lower positions could affect? But if we have a digit 9, to get sum 9 in that column, we need at least 9 numbers with a 1 in that column, because each contributes 0 or 1. So minimal k is at least the maximum digit. It can be achieved: For each digit position, we assign 1s to some numbers. Essentially we can represent n as sum of m numbers where m = maxDigit. For each digit position, we set the digit of the i-th number to 1 if the original digit at that position is >= i (i from 1 to m). This yields m quasibinary numbers whose sum equals n. That's the standard construction.
Example: n=9 => max digit=9 => we need 9 numbers. For each number i from 1 to 9, set the digit (only ones place) to 1 => each number=1, sum=9.
n=32 => digits: tens=3, ones=2. max digit=3. So we need 3 numbers. Construct:
- For i=1: number with tens digit = (3>=1)?1:0, ones digit = (2>=1)?1:0 => 11
- i=2: (3>=2)?1:0 => 1, (2>=2)?1:0 => 1 => 11
- i=3: (3>=3)?1:0 => 1, (2>=3)?0:0 => 0 => 10 => numbers: 11,11,10 sum=32. So output 3 and those numbers.
Edge cases: n=0? but n>=1, so ignore.
Also note numbers should not have leading zeroes; in construction we may have numbers like "01"? We don't output leading zeroes; we just output integer numbers, so fine.
Implementation: Read n as int. Convert to string to get digits. Determine m = max digit (as integer). Initialize an array of m strings, each initially empty? Better: For each digit position (from most significant to least? Actually we can construct numbers by building integer values directly). Since n <= 10^6, max digits = 7 (since 1e6 has 7 digits: 1000000). So m <= 9 (since max digit 9). So we can simply create an array of m integers initially 0. For each digit of n (from highest to lowest), we get digit d. For i from 0 to m-1 (i.e., for each of the m numbers), if d > i (or >= i+1) then we add appropriate power of 10 to the i-th number. Specifically, we treat i from 0 to m-1 as index representing numbers that correspond to "level" i+1. For each digit place with value d, for each of the m numbers, if the count (i+1) <= d then set 1 in that digit place for that number. So we need to add 10^place to the i-th number if (i+1) <= d.
Alternatively, we can generate the numbers by constructing strings digit by digit: iterate over each digit of n (as string), for each digit char, for each of m numbers, append '1' or '0' depending if remaining count. But careful: we need to process digits from most significant to least, but building strings directly might add leading zeroes at the front of some numbers? However, we can start with empty strings and later parse as integer to drop leading zeros? Since numbers should not have leading zeroes; however, if the most significant digit is 0, we would have a leading zero. But in the construction, for some numbers the highest digit might be zero. For example, n=10? n=10 digits: '1','0' max digit=1. So m=1. For the only number: for digit '1' set '1', for digit '0' set '0' => number string "10". That's fine. But if m>1, some numbers might have zero in the highest position: e.g., n=32, we constructed numbers: 11,11,10. Here highest digit (tens) for third number is '1', not zero. Actually for n=100? n=100 digits: '1','0','0' max digit=1 => m=1 => number "100". Fine. For n=202? digits: 2,0,2, max digit=2 => m=2. Construct numbers: for hundreds: d=2, for i=1: (1<=2) => 1, i=2: (2<=2) => 1 => both numbers get a 1 in hundreds place. Tens: d=0, so no 1 for any. Ones: d=2, both get 1. So numbers: 101 and 101? Actually hundreds=1, tens=0, ones=1 => 101 for both? Wait: For ones place, d=2, so both get 1. So numbers are 101 and 101 => sum=202? 101+101=202. But what about the tens digit? Both zero. So numbers are 101,101. That's fine; they have no leading zeros. If we had a number where the most significant digit is zero, then the number would be like "001"? But we can just convert to integer when printing, but we need to output the number without leading zeros. If we build integers, we won't have leading zeros. So building integers is easier.
Given n up to 1e6, we can just compute powers of ten. Digits: we can extract digits by repeated modulo. Let's extract digits into an array from least significant to most. But we need to iterate over places. Let's determine number of digits: we can compute or convert to string.
Simplify: convert n to string s. Let m = max digit (int). Initialize a list of m integers, all 0. Then for each character in s (from left to right, i.e., most significant to least), we compute place value: starting with power = 10^{len(s)-1-index}. For each digit d (int), we iterate j from 0 to m-1 (representing number j), and if (j+1) <= d, then add power to numbers[j]. Then after processing the digit, divide power by 10 for next.
Since n <= 10^6, max power 10^6, and m <= 9, operations trivial.
After constructing, we have m numbers. Some numbers may be zero? Could any be zero? If max digit is m>0, each number gets at least one 1? Not necessarily. Consider n=10, m=1, number=10, not zero. For m>1, each number gets at least one 1? Because the maximum digit is m, meaning there is at least one digit equal to m. For that digit, all m numbers get a 1 (since for all j, j+1 <= m). So each number gets at least a 1 at that digit place, so all numbers > 0. So no zeros.
Thus output m and the m numbers (any order). But note: The problem statement says "Do not have to print the leading zeroes in the numbers. The order of numbers doesn't matter." So we can output as is.
Edge case: n=0? not allowed.
Now, examples: Input 9 -> m=9, numbers = each get 1 from the only digit: power=1, d=9, for j=0..8, j+1 <=9 so add 1 => each gets 1. So output nine 1's. That matches.
Input 32 -> above yields 10,11,11 but order not important; we might have 11,11,10.
Now confirm: n=1000000 => digits: 1 and six zeros. max digit=1 => m=1 => number = 1000000. Output 1 and 1000000.
n=999999 => digits all 9, max=9 => m=9, we get numbers each with all digits 1? Actually for each digit (6 digits) d=9, for each number j, if j+1 <=9 => always true, so each number gets 1 at every digit => each number = 111111. So sum = 9*111111 = 999999. That's fine.
Thus the solution is straightforward.
Now, we need to produce code in the answer. The user likely expects a solution in Python? The problem is from Codeforces, typical solution in any language. Since the environment is unspecified, I'll produce Python solution.
But we need to be mindful: The problem might require to output numbers separated by spaces, and the first line with k. The second line with k numbers. In the example, they output a trailing space after the numbers? We can print with spaces, not necessary trailing. We'll use print(' '.join(map(str, numbers))) to avoid trailing space.
Now, there is nuance: The construction yields numbers that are quasibinary indeed. Because each number's digits are either 0 or 1 (since we only add power when condition true, and each digit place we only add at most once to each number). So digits are either 0 or 1. Also note that numbers can be up to 10^6, but with m up to 9, numbers can be up to the same magnitude as n.
Thus solution:
- Read integer n.
- Convert to string s.
- Compute m = max(int(c) for c in s).
- Initialize array ans = [0]*m.
- Let power = 10**(len(s)-1).
- For each character c in s: d = int(c) for i in range(m): if d > i: # because i from 0, we need to check if i+1 <= d => if d > i ans[i] += power power //= 10
- Print(m)
- Print(' '.join(map(str, ans)))
Alternative: Instead of power, we can process from rightmost using modulo, but this is fine.
Potential issue: When power becomes zero? At the last digit (units), power = 1? Actually after processing the last digit, we divide power by 10, but we don't use it. So it's fine.
Edge case: n=0? not needed.
Test: n=10: s="10", len=2, power=10. For first digit '1': d=1, for i in range(1): i=0, d>0? 1>0 True => ans[0] +=10 => ans[0]=10. power=1. Next digit '0': d=0, for i: 0>0? False, so ans[0] unchanged. So ans=[10]. Output: 1, 10. Correct.
n=101: s="101", len=3, power=100. digits: '1' -> d=1, for i=0 (since m=1) d>0? True => ans[0]+=100 =>100. power=10. Next '0': d=0, no add. power=1. Next '1': d=1, ans[0]+=1 =>101. So ans=[101]. Output 1 101. That's a quasibinary? 101 digits are 1,0,1 -> yes.
n=2: s="2", m=2? Actually max digit=2 => m=2. power=1. For digit '2': d=2. For i=0: d>0 => ans[0]+=1 =>1. i=1: d>1? 2>1 => ans[1]+=1 =>1. So ans=[1,1]. Output 2, and numbers 1 1. Sum=2, correct.
n=11: s="11", max digit=1 => m=1, ans=[11]? Let's see: len=2, power=10. First digit '1': d=1, i=0: d>0? true => ans[0]+=10 =>10; power=1; next digit '1': ans[0]+=1 =>11. So output 1 and 11. But 11 is quasibinary. However, could we represent 11 as sum of fewer than 1? No, because it's already quasibinary. So k=1. Good.
n=12: s="12", max digit=2 => m=2. power=10: digit '1': d=1 -> i=0: d>0? true => ans[0]+=10; i=1: d>1? 1>1 false => no. So ans[0]=10, ans[1]=0. power=1: digit '2': d=2 -> i=0: d>0 true => ans[0]+=1 =>11; i=1: d>1 true => ans[1]+=1 =>1. So ans=[11,1]. Output 2 and numbers 11 and 1. Sum=12. That's valid.
So algorithm works.
Now, about minimality: Since max digit is at least the minimum number needed, and we achieve exactly that many numbers, it's optimal.
Now, we need to produce the final answer: Usually we output code snippet. Provide explanation? The user request: "You are given a positive integer n. Represent it as a sum of minimum number of quasibinary numbers." So they likely want the solution. Probably they want the algorithm description? However, the platform expects code? The problem is from Codeforces, but here we are ChatGPT answering. Probably the user wants a solution (maybe code) in the answer. Usually in these problem contexts, we provide a solution with explanation and code. Since it's a "solve the problem" prompt, I should provide a full solution: explanation of the greedy method and the code.
Thus I'll write:
-
Explanation: The minimal number is the maximum digit. Construct numbers by distributing ones across columns.
-
Complexity: O(d * m) where d is number of digits (<=7) and m<=9, trivial.
-
Implementation in Python.
Will include code.
Now, check constraints: n up to 10^6, but also could be up to 10^6? Actually the problem says 1 ≤ n ≤ 10^6. However, I've seen Codeforces problem says n ≤ 10^6, but the method works for larger as well.
Edge Cases: None.
Thus final answer: Provide code.
We should ensure reading input correctly, and printing output.
We'll output:
k numbers separated by space
In case the second line must contain exactly k numbers, and maybe trailing space is okay, but we will not include trailing space.
Now, the code:
def solve(): import sys data = sys.stdin.read().strip().split() if not data: return n = data[0] s = n.strip() m = max(int(ch) for ch in s) ans = [0] * m power = 10 ** (len(s)-1) for ch in s: d = int(ch) for i in range(m): if d > i: # effectively i+1 <= d ans[i] += power power //= 10 print(m) print(' '.join(map(str, ans)))
if name == "main": solve()
That's good.
But be careful: When reading input, there might be newline. Using sys.stdin.read reads all. It's fine.
Alternatively, could read directly.
Now, there is a nuance: When m=0? Not possible because n>=1, so max digit >=1.
Now, final answer: Provide explanation and code.
Since the user might want a C++ solution? But the prompt doesn't specify language. Usually in these problem statements, one can answer with Python. I'll include Python code. I can also mention that the approach works.
Now, answer. The minimum number of quasibinary numbers required is equal to the maximum digit in the decimal representation of (n). This is because each quasibinary number contributes at most 1 to any digit place, so to achieve a digit (d) we need at least (d) numbers with a 1 in that place. Moreover, this lower bound is achievable by constructing exactly (m = \max\text{digit}) numbers as follows:
For each digit position of (n) (from most significant to least) with value (d), and for each of the (m) numbers (indexed from 1 to (m)), set the digit in that position to 1 if the index (i) satisfies (i \le d); otherwise set it to 0. This yields (m) valid quasibinary numbers whose sum equals (n).
The time complexity is (O(d \cdot m)), where (d) is the number of digits (at most 7) and (m \le 9), so it is effectively constant.
Below is a Python implementation:
import sys def solve() -> None: n_str = sys.stdin.readline().strip() if not n_str: return # Minimum number of quasibinary numbers = maximum digit m = max(int(ch) for ch in n_str) # Initialize m numbers ans = [0] * m power = 10 ** (len(n_str) - 1) for ch in n_str: d = int(ch) for i in range(m): # Use condition d > i (equivalent to i+1 <= d) if d > i: ans[i] += power power //= 10 # Output print(m) print(' '.join(map(str, ans))) if __name__ == "__main__": solve()Input:
9Output:
9 1 1 1 1 1 1 1 1 1Input:
32Output:
3 10 11 11