Cristina94: Pagină nouă: ==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...

2024-04-01T09:35:17Z

Pagină nouă: ==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...

New page

==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>
#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>

2957 - Nests - Revision history