3162 - cife bin back

Cerința

Se dă un număr natural n. Afișați în ordine lexicografică toate secvențele de cifre binare care au atâtea cifre de 0 și atâtea cifre de 1 câte are reprezentarea binară a lui n.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran combinațiile de cifre binare cerute, câte una pe fiecare rând.

Restricții și precizări

• 1 ≤ n ≤ 2.000.000

Exemplu 1

Intrare

17

Iesire

00011
00101
00110
01001
01010
01100
10001
10010
10100
11000

Rezolvare

<syntaxhighlight lang="python" line> from itertools import permutations

def generate_binary_sequences(n):

   binary_representation = bin(n)[2:]
   count_ones = binary_representation.count('1')
   count_zeros = len(binary_representation) - count_ones

   # Create the base string with the correct number of 1s and 0s
   base_string = '1' * count_ones + '0' * count_zeros

   # Generate all unique permutations of the base string
   unique_permutations = sorted(set(permutations(base_string)))

   # Convert tuples back to strings
   result = [.join(p) for p in unique_permutations]

   return result

def main():

   n = int(input().strip())
   results = generate_binary_sequences(n)
   for result in results:
       print(result)

if __name__ == "__main__":

   main()

</syntaxhighlight>