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

<syntaxhighlight lang="python" line>

1. 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>