Editing 2957 - Nests (section)

==Rezolvare==
<syntaxhighlight lang="python" line>
#2957 nests
def nth_lexicographic_permutation(N, K):
  # Convertim numărul K din baza 2 în baza 10
  K_base10 = int(K, 2)
  
  # Inițializăm permutarea cu cifrele de la 0 la N-1
  permutation = list(range(N))
  
  # Algoritmul lui Narayana pentru generarea permutărilor lexicografice
  for _ in range(K_base10):
    i = N - 2
    while i >= 0 and permutation[i] > permutation[i + 1]:
      i -= 1
    
    j = N - 1
    while permutation[j] < permutation[i]:
      j -= 1
    
    permutation[i], permutation[j] = permutation[j], permutation[i]
    permutation[i + 1:] = reversed(permutation[i + 1:])

  return permutation

def validate_input(N, K):
  try:
    N = int(N)
    if not 1 <= N <= 1000000:
      raise ValueError("N trebuie să fie între 1 și 1.000.000")
  except ValueError:
    return False, "N trebuie să fie un număr natural între 1 și 1.000.000"

  if not K.isdigit() or set(K) - {'0', '1'}:
    return False, "K trebuie să fie un număr în baza 2"

  return True, ""

def main():
  # Citirea datelor de intrare
  N = input("Introduceți numărul N: ")
  K = input("Introduceți numărul K în baza 2: ").strip()

  # Validarea datelor de intrare
  is_valid, error_message = validate_input(N, K)
  if not is_valid:
    print("Date invalide:", error_message)
    return

  # Generarea permutării și afișarea ei
  result = nth_lexicographic_permutation(int(N), K)
  print("Permutarea lexicografică corespunzătoare poziției K:", ' '.join(map(str, result)))

if __name__ == "__main__":
  main()
</syntaxhighlight>