After playing Neo in the legendary "Matrix" trilogy, Keanu Reeves started doubting…
- User
After playing Neo in the legendary "Matrix" trilogy, Keanu Reeves started doubting himself: maybe we really live in virtual reality? To find if this is true, he needs to solve the following problem.
Let's call a string consisting of only zeroes and ones good if it contains different numbers of zeroes and ones. For example, 1, 101, 0000 are good, while 01, 1001, and 111000 are not good.
We are given a string s of length n consisting of only zeroes and ones. We need to cut s into minimal possible number of substrings s_1, s_2, …, s_k such that all of them are good. More formally, we have to find minimal by number of strings sequence of good strings s_1, s_2, …, s_k such that their concatenation (joining) equals s, i.e. s_1 + s_2 + ... + s_k = s.
For example, cuttings 110010 into 110 and 010 or into 11 and 0010 are valid, as 110, 010, 11, 0010 are all good, and we can't cut 110010 to the smaller number of substrings as 110010 isn't good itself. At the same time, cutting of 110010 into 1100 and 10 isn't valid as both strings aren't good. Also, cutting of 110010 into 1, 1, 0010 isn't valid, as it isn't minimal, even though all 3 strings are good.
Can you help Keanu? We can show that the solution always exists. If there are multiple optimal answers, print any. Input
The first line of the input contains a single integer n (1≤ n ≤ 100) — the length of the string s.
The second line contains the string s of length n consisting only from zeros and ones.
Output
In the first line, output a single integer k (1≤ k) — a minimal number of strings you have cut s into.
In the second line, output k strings s_1, s_2, …, s_k separated with spaces. The length of each string has to be positive. Their concatenation has to be equal to s and all of them have to be good.
If there are multiple answers, print any.
Examples
Input
1 1
Output
1 1
Input
2 10
Output
2 1 0
Input
6 100011
Output
2 100 011
Note
In the first example, the string 1 wasn't cut at all. As it is good, the condition is satisfied.
In the second example, 1 and 0 both are good. As 10 isn't good, the answer is indeed minimal.
In the third example, 100 and 011 both are good. As 100011 isn't good, the answer is indeed minimal.
Assistant
We need to solve the problem: given a binary string s of length n (n up to 100), we need to partition it into minimal number of substrings such that each substring is "good": the numbers of zeros and ones in the substring are different (i.e., count0 != count1). So each substring must be unbalanced. The minimal number of substrings is either 1 if the whole string itself is good, or else we need to cut into more pieces. We need to output any optimal partition.
Observations: Since n is small (≤100), we can solve by DP or greedy? Let's analyze properties.
First, note that if a string is not good, then it is balanced? Actually definition: good if it contains different numbers of zeroes and ones. So not good means equal numbers of zeros and ones (including perhaps empty? but substrings are non-empty). So "bad" means count0 = count1.
So the condition for a substring to be not good is that it has equal number of 0s and 1s.
Thus we need to partition into minimal number of substrings, each with count0 != count1.
This is reminiscent of splitting a string into minimal number of substrings that are not balanced. Equivalent to covering s with minimal segments that are each unbalanced.
We want minimal number of segments, so we want each segment as long as possible, but must be unbalanced. We want to see if there is a greedy approach: we can try to take longest prefix that is good? But that might not lead to optimal minimal number because sometimes you might need to cut earlier to avoid a balanced segment later.
But n is only 100, we can use DP: let dp[i] = minimal number of good substrings needed to partition prefix of length i (i from 0 to n). dp[0] = 0 (empty prefix). For each i, we consider j < i such that substring s[j+1...i] (1-indexed) is good, then dp[i] = min(dp[j] + 1). At the end, dp[n] is answer. And we can reconstruct by keeping predecessor. Since n is small (100), O(n^2) is fine.
We need to check if substring from j to i-1 (0-index) is good: count0 != count1. We can precompute prefix sums of zeros and ones to check quickly.
Potential issue: Could there be no partition? But problem states solution always exists. Is it always possible? Let's think: any single character substring: if length 1, count0 != count1 (either 1 zero and 0 ones, or 1 one and 0 zeros) -> good. So we can always partition into singletons. So solution exists.
Thus DP will find minimal number.
We need to output any optimal partition. So after DP, we can backtrack.
Complexity: O(n^2) = 10^4.
Edge Cases: The whole string might be good, dp[n] = 1 directly.
Implementation details:
Input: n, then string s (length n). We'll use 0-index.
Let zeros[i] = number of zeros in s[0..i-1] (prefix). So zeros[0]=0. For i from 1..n: zeros[i]=zeros[i-1] + (s[i-1]=='0'?1:0). Similarly ones[i] or we can compute count1 = (i - zeros[i])? But easier: ones[i] = i - zeros[i]. Or we can keep a second array.
Given start index j (0 <= j < i), substring from j to i-1 inclusive. Count0 = zeros[i] - zeros[j]; count1 = (i-j) - (zeros[i]-zeros[j]) = (i-j) - count0. Or compute ones prefix similarly.
The substring is good if count0 != count1, i.e., count0 != (length/2)? Actually condition: count0 != count1 is equivalent to count0 != length/2 (since count1 = length - count0). But length could be odd: then automatically count0 != count1 because if length is odd, can't have equal counts. So for odd-length substrings, they are always good. For even length, we need count0 != count1, i.e., count0 != length/2.
Thus the only potential "bad" substrings are those of even length with equal number of zeros and ones.
So DP can consider all j < i, but we can skip those where substring is bad.
Given small n, we can simply check each substring.
Now DP: initialize dp[0]=0; for i from 1..n: dp[i]=INF; for j from 0 to i-1: len = i-j; count0 = zeros[i]-zeros[j]; if count0 != len - count0: then dp[i] = min(dp[i], dp[j] + 1); record prev[i] = j.
At the end, dp[n] is answer. Then reconstruct: start at idx=n; while idx>0: prevIdx = prev[idx]; substring = s[prevIdx:idx] (Python slicing). Store in list, then idx=prevIdx. Finally output dp[n] and the substrings in reverse order (since we built from end). Or we can store as we backtrack and then reverse.
But careful: In Python, we need to store substrings separated by spaces. So we can do:
ans = [] pos = n while pos > 0: start = prev[pos] ans.append(s[start:pos]) pos = start ans.reverse() print(len(ans)) print(' '.join(ans))
Edge Cases: n=0 not possible (n>=1). dp[0]=0.
Now we need to confirm that dp returns minimal number. Since we are doing DP over all possibilities, it's correct.
But maybe there is a greedy solution: The minimal number is either 1 or 2? Let's test: Could it ever require more than 2? Example: s = "10". Whole string is balanced (1 zero, 1 one) so not good. Minimal partition? Single characters: "1" and "0" both good, so k=2. Could there be a string requiring 3? For instance, "1010"? Let's see: length 4, balanced? counts: 2 zeros, 2 ones? Actually "1010" has zeros: 2? characters: 1,0,1,0 => zeros=2, ones=2 => balanced so not good. Can we partition into 2 good substrings? Possibly "10" is balanced (not good); "101" (odd length) is good? Check: "101": zeros=1, ones=2 => good. "0": good => So partition: "101" and "0" => k=2. Could we do "1"+"010"? "010": zeros=2, ones=1 => good (since length 3). So also 2. So 2 works.
Try "0101": zeros=2 ones=2? Actually "0101": zeros=2, ones=2 => balanced whole. Partition: "010" (zeros=2, ones=1 => good) + "1" => good => 2. Or "0"+"101": "101" good => 2.
Consider "0011"? Balanced? zeros=2 ones=2 => not good. Partition: "001" (zeros=2, ones=1 => good) + "1" => good => 2. Or "0"+"011": "011" zeros=1? actually "011": zeros=1? characters: 0,1,1 => zeros=1 ones=2 => good. So 2.
Consider "0100"? zeros=3 ones=1 => whole good? counts: zeros=3 ones=1 => not equal => good! So whole is good => k=1.
Thus maybe the answer is either 1 or 2 always? Let's test further: Could there be a string requiring 3? Suppose we have a string that is balanced (count0 = count1), but no single cut can break it into two good substrings? Is that possible? We need to find s such that for every possible split point i (1 <= i <= n-1), either prefix s[0:i] is bad or suffix s[i:n] is bad. And since whole is bad, we need to cut into at least 3 pieces. But is there such a string? Let's try small n.
n=2: "10" or "01": whole bad. Splits: i=1: prefix "1" good, suffix "0" good => so 2 works. So no 3.
n=4: Balanced strings. Need to see if there exists a balanced string where every split yields at least one balanced segment. Balanced strings of length 4: possible: 0011, 0101, 0110, 1001, 1010, 1100. Let's examine each.
- 0011: Split at i=1: prefix "0" good, suffix "011": zeros=2? suffix length3: 0,1,1 => zeros=1, ones=2 -> good. So both good => 2 works.
- 0101: i=1: "0" good, "101" good => works.
- 0110: i=1: "0" good, "110": zeros=1 ones=2 good => works.
- 1001: i=1: "1" good, "001": zeros=2 ones=1 good => works.
- 1010: i=1: "1" good, "010": zeros=2 ones=1 good => works.
- 1100: i=1: "1" good, "100": zeros=2 ones=1 good => works. All work with i=1.
So for n=4, always possible to split into 2 good substrings? It seems yes by taking first character. Since any single character is good, and the remainder length n-1: if n-1 is odd, then it's automatically good. But if n is even, n-1 is odd, so remainder is always good because odd length always has count0 != count1? Actually not necessarily: a string of odd length could still have equal zeros and ones? No, because if length is odd, zeros and ones cannot be equal because equal would require each count = length/2, but length/2 is not integer? Actually if length is odd, length/2 is non-integer, so counts can't be equal since counts are integers. So any odd-length string is automatically good. Therefore, if n is even and the whole string is balanced, we can cut off the first character (length 1, good), then the rest has length n-1 which is odd, thus automatically good. That's a valid partition into two good substrings! Check: The rest could be balanced? But for odd length, it's impossible to have equal zeros and ones because equal would imply length even. So yes, any odd-length string is good regardless of its composition. So this provides a universal construction: if the whole string is not good (i.e., balanced), then cut off the first character; the remainder is odd length, so it's good. Thus we can always partition any balanced string into two good substrings (first character + rest). Wait, is there any edge case? The remainder could be empty if n=1? But n=1, whole string is good anyway. For n=2, remainder length 1, good. So yes, for any string that is not good (balanced even length), we can always split into two good substrings: first character and the rest. But careful: Is the remainder guaranteed to be good? Since remainder length = n-1 is odd, yes it's automatically good because it's impossible to have equal zeros and ones (since length is odd). So that partition is always valid. Therefore minimal number of substrings is either 1 (if whole is good) or 2 (if whole is not good). That means answer k is always either 1 or 2.
But wait, what about the possibility that cutting into two substrings might produce a remainder that is not good if the remainder length is odd? As argued, odd length => cannot have equal counts. So it's always good. So indeed for any balanced (even-length with equal zeros and ones) string, we can achieve k=2. And we cannot have k=1 because whole is not good. So minimal k is exactly 2. So the answer is always either 1 or 2.
But is there any string that is good but we might want to cut into 2 anyway? No, minimal would be 1 if whole good. So the problem reduces to checking if the whole string is good: if count0 != count1, output 1 and the string; else output 2 and partition as first character and the rest. But we must verify that the remainder is indeed good: Since length of remainder = n-1 is odd, it's always good. But wait, is it possible that remainder length 0? That would happen if n=1, but then whole is good because count0 != count1. So we are only in the else case when n>=2 and whole is balanced. Then n-1 >=1 and odd. So remainder good.
Thus we have a trivial solution: if s is good (i.e., count('0') != count('1')) then output 1 and s; else output 2: s[0] and s[1:] (or s[0] and s[1:]? Actually first character and the rest). But we need to check if there is any scenario where the remainder might not be good due to something else? As argued, any odd-length string is good because equal counts require even length. So it's always good.
But let's double-check: The definition: good if it contains different numbers of zeroes and ones. For an odd-length string, it's impossible for counts to be equal because that would require each count = length/2, which is not integer. So yes, odd-length strings are always good. Therefore remainder is good.
Thus minimal number is at most 2. Could it be that there is a partition into 1 substring if whole is not good? No. So answer is 1 or 2.
But wait, the problem statement gave example: 110010 output 2: 100 and 011. In that example, whole string "110010" length 6, count zeros? 110010: zeros: positions: 1,1,0,0,1,0? Actually "110010" => characters: 1,1,0,0,1,0 => zeros=3, ones=3 => balanced, not good. So answer 2. Their example partition is "100" and "011". That's a different split than first character + rest. Their first substring is "100" (which is not the first character) and second "011". So multiple solutions exist. So our simple solution (first char + rest) would give "1" and "10010"? Let's check "10010": length 5 odd -> good. Yes, "1" and "10010". That is also valid. So answer would be 2: "1 10010". But is "10010" good? Let's check: "10010": zeros? characters:1,0,0,1,0 => zeros=3, ones=2 -> different -> good. So that is valid. So it's also minimal. So we can output that.
But we must consider that the problem expects output of any optimal answer. So the simple approach is correct.
But wait, is there any catch? Let's test n=0? Not allowed.
Check n=1: s="0" or "1": count0 != count1 => good, output 1.
Check n=2: s="10": count0=1 count1=1 => not good => output 2: "1 0". That matches example.
Check n=3: any string of length 3 is good because length odd. So output 1.
Check n=4: s="0011": not good => output 2: "0 011". "011" length 3 good. Yes.
Thus solution is trivial. But the problem mentions n up to 100, and DP would be overkill, but we can just implement the trivial logic.
But is there any case where whole string is balanced but the remainder after taking first character might be empty? No, n>=2 for balanced case because balanced requires even length and non-zero? Actually n could be 0? No n>=1. So n=2 yields remainder length 1 >0.
Thus answer is always 1 or 2.
But wait, the problem statement: "We can show that the solution always exists." That matches.
But why would they make n up to 100 if trivial? Possibly to disguise the simplicity, or to allow DP solutions? Or maybe there is a nuance: The definition: good if it contains different numbers of zeroes and ones. That means the substring must have count0 != count1. That's it. So indeed any odd-length substring is automatically good. So for any string of even length that is balanced, we can cut at the first character to get an odd-length remainder. So minimal pieces = 2.
But is it always possible that 2 is minimal? Could there be a case where the whole string is balanced, but we could do 1? No. So answer 2.
Thus the solution is straightforward.
But hold on: Might there be a case where the whole string is not good but we could still partition into 1? No, because if it's not good, it's not allowed as a single substring.
Thus answer is exactly as described.
Double-check: Is it always optimal to cut at first character? Possibly but we just need any partition. So we can output s[0] and s[1:].
But we need to output two strings separated by space. Ensure that we don't have extra spaces.
Implementation: read n, s. Compute count0 = s.count('0'), count1 = n - count0 or s.count('1'). If count0 != count1: print(1); print(s). Else: print(2); print(s[0] + ' ' + s[1:]) (but careful: s[1:] might be empty if n=1? But we are in else only when n>=2 because if n=1 counts would be unequal. So s[1:] is non-empty). So that's it.
Edge Cases: n=0 not possible.
But wait: The problem statement example for input "6 100011" output "2 100 011". Our solution would give "1 00011"? Actually s="100011", first char '1', rest "00011": zeros=3 ones=2 -> good. So output "1 00011"? Wait we need to output two strings: first "1", second "00011"? That is valid. But we need to print as: "1 00011". That is also correct. So answer may vary.
Thus solution is trivial.
But could there be any scenario where the string is balanced and the remainder after first character might not be good? Let's consider if the remainder has odd length, is it always good? As argued, yes because equal counts require even length. But is there any hidden condition? The definition: "contains different numbers of zeroes and ones." So if length is odd, counts cannot be equal. So good. So it's safe.
Thus answer is simply: if count0 != count1 -> 1, else -> 2 with split after first character.
But wait, what if n is even and the string is balanced, but the remainder after first character is odd length, so automatically good. So yes.
Thus the DP is not needed.
But perhaps there is a nuance: The substrings must be good. For odd-length substrings, it's automatically good. So fine.
Hence we can implement.
However, we need to check if there is any possibility that the string is balanced but also of odd length? No, balanced implies equal counts, so total length = count0+count1 = 2*count0, so even. So balanced strings always have even length. So we are fine.
Thus minimal number of substrings is at most 2.
So final answer: if s has unequal numbers of 0 and 1: print 1 and s; else print 2, s[0] and s[1:].
Now, is there any scenario where the whole string is not good but we could still have k=1 by some trick? No.
So that's it.
But we should also consider the possibility that n=0? Not.
Thus the solution is trivial.
But why does the problem have n up to 100? Possibly to allow naive DP or to hide the simple observation.
Thus we will code accordingly.
But before finalizing, let's test with random strings via mental simulation.
Case: s="0000": count0=4 count1=0 -> not equal -> good, output 1.
Case: s="010": count0=2 count1=1 -> good, output 1.
Case: s="1010": count0=2 count1=2 -> not good, output 2: "1 010". "010" is good? length 3 => automatically good. Yes.
Case: s="111000": count0=3 count1=3 -> not good, output 2: "1 11000"? Wait first char '1', rest "11000"? Actually "111000": first char '1', rest "11000": zeros=3? "11000": characters:1,1,0,0,0 -> zeros=3, ones=2 -> good. So valid.
Thus always works.
But note: The problem's sample output for "100011" is "100 011". That's a different split but still valid. So any split works.
Thus we can output simple split.
One more check: In the else branch, we output two strings: first character and the remainder. But we must ensure that we output the remainder as a string, even if it's long. So print(s[0] + ' ' + s[1:]).
Implementation in Python:
def solve(): import sys data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) s = data[1].strip() zeros = s.count('0') ones = n - zeros if zeros != ones: print(1) print(s) else: print(2) print(s[0] + ' ' + s[1:])
But we need to ensure that if n=2 and s="10", this outputs "1 0". That's correct.
Edge: If s length is 2 and balanced, remainder length 1, good.
Thus solution done.
But wait: Could there be any input where the string has newline? We'll handle.
I'll consider if the input might have spaces? No, string consists of zeroes and ones.
Thus final solution.
But perhaps we should consider that the problem might have a twist: The definition of "good" might be misinterpreted: "contains different numbers of zeroes and ones." Could it mean that the string contains at least one zero and at least one one, and the counts are different? Actually "contains different numbers of zeroes and ones" straightforwardly means the count of zeros is not equal to count of ones. So no twist.
One more nuance: The problem statement: "Let's call a string consisting of only zeroes and ones good if it contains different numbers of zeroes and ones." That's clear.
Thus final.
But before final answer, I'll think if there is any scenario where the remainder after first character might be empty? If n=1, then zeros != ones, so else not executed. So safe.
Thus solution trivial.
Given that the problem is from Codeforces? Possibly "1102A" or something? Actually this problem resembles Codeforces 1102A? Not sure. But it's a simple observation.
Thus final answer: implement as described.
But the problem might be tricked: maybe there is a string that is not good but cannot be split into 2 good substrings? But we argued that odd-length strings are automatically good. So after removing first character, remainder length is odd only if original length is even. But what if original length is odd? Then it's already good, so no issue. So for not good case, original length must be even. So remainder is odd -> good. So yes.
Now, what if the first character is removed and the remainder is empty? That would require n=1 but n=1 is good. So no.
Thus minimal k is always 1 or 2.
Now, is there any chance that we could achieve k=1 when string is balanced but we could rearrange? No, partition must be contiguous substrings, not reorder.
So done.
Now, since the problem asks for minimal number and any optimal answer, we can just output the simple split.
Now, I'm going to produce final answer explanation and code.
But note: The input format: first line integer n, second line string s. So reading accordingly.
Time complexity O(n) for counting zeros.
Memory O(1).
We'll provide solution.
Now, let's produce final answer with explanation.
But I should double-check with some random test: s="000111": zeros=3 ones=3 -> not good. Output 2: "0 00111"? Actually first char '0', rest "00111": zeros=3? "00111": zeros=3, ones=2 -> good. So valid.
What about s="01"? output "0 1"? Actually first char '0', rest "1": good. So output "0 1". That's also valid.
But sample 2 output "1 0" (first char '1', rest "0"). That's the same as our split (just swapped). So it's fine.
Thus solution correct.
Now, we must be cautious about trailing spaces or newlines. Use print normally.
Thus finalize.
Now, I'll produce the final answer. ```python
import sys
def solve() -> None: data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) s = data[1].strip()
zeros = s.count('0') if zeros != n - zeros: # whole string is good print(1) print(s) else: # whole string is balanced print(2) print(s[0] + ' ' + s[1:])if name == "main": solve()