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