2957 - Nests

Enunţ

Pe vârfurile unui poligon regulat și-au făcut cuibul 𝑁 păsări. Cele 𝑁 vârfuri ale poligonului sunt numerotate cu numere de la 0 la 𝑁−1 în ordine sens trigonometric. Fiecare pasăre se găsește în câte un cuib. La un moment dat păsările își schimbe cuiburile. Se obține astfel o permutare (𝑐0 ,𝑐1 ,𝑐2 ,..., 𝑐𝑁−1) unde 𝑐𝑖 reprezintă cuibul în care s-a mutat pasărea care locuia inițial în cuibul 𝑖. Pentru ca toate păsările sa depună același efort cuiburile vor fi alese astfel încât distanța între cuibul inițial 𝑖 și cel final 𝑐𝑖 să fie aceeași pentru toate cele 𝑁 păsări. Se consideră toate permutările (𝑐0 ,𝑐1 ,𝑐2 ,..., 𝑐𝑁−1) obținute după mutarea păsărilor și se ordonează lexicografic.

Cerința

Scrieți un program citește două numere naturale 𝑁 și 𝐾 și care afișează permutarea situată pe poziția 𝐾 în ordine lexicografică după ordonarea permutărilor obținute prin mutarea păsărilor. ATENȚIE: numărul K va fi dat în baza 2.

Date de intrare

De la intrarea standard se va citi de pe prima linie numărul 𝑁 și de pe a doua linie un șir de valori 0 sau 1 neseparate prin spatii reprezentând cifrele numărului K scris în baza 2.

Date de ieșire

La ieșirea standard vor fi afișate N numere întregi distincte, separate prin câte un spațiu, cu valori între 0 și 𝑁−1, reprezentând permutarea situată pe poziția 𝐾 în ordine lexicografică între toate permutările posibile obținute după mutarea păsărilor.

Restricții și precizări

• 1 ≤ N ≤ 1.000.000
• Se asigură că pentru N dat există cel puțin K posibilități pentru mutarea păsărilor.

Exemplul 1

Intrare

4

101

Ieșire

0 3 2 1

Exemplul 2

Intrare

-5

101

Ieșire

Date invalide: N trebuie să fie un număr natural între 1 și 1.000.000

Rezolvare

#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()