Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Apr 1st, 2020 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def check_input(l, n):
  2.     nl = len(l)
  3.     if nl != n:
  4.         return False
  5.     test = [0] * n
  6.     for i in l:
  7.         if i > n - 1 or i < 0:
  8.             return False
  9.         test[i] += 1
  10.         if test[i] > 1:
  11.             return False
  12.     return True
  13.  
  14. print("----------Задача о марьяже----------")
  15. n = int(input("Введите количество мужчин и женщин n: "))
  16.  
  17. m = []    # Wish list for every man
  18. print("Введите предпочтения мужчин в порядке убывания (1 2 ... n)")
  19. for i in range(n):
  20.     f = False
  21.     while not f:
  22.         tmp = [int(x) - 1 for x in input(f"Предпочтения {i + 1}-го мужчины: ").split()]
  23.         f = check_input(tmp, n)
  24.         if not f:
  25.             print("Некорректный ввод. Необходимо ввести разные числа от 1 до n.")
  26.     m.append(tmp)
  27.  
  28. w = []    # Wish list for every woman
  29. print("Введите предпочтения женщин в порядке убывания (1 2...n)")
  30. for i in range(n):
  31.     f = False
  32.     while not f:
  33.         tmp = [int(x) - 1 for x in input(f"Предпочтения {i + 1}-й женщины: ").split()]
  34.         f = check_input(tmp, n)
  35.         if not f:
  36.             print("Некорректный ввод. Необходимо ввести разные числа от 1 до n.")
  37.     w.append(tmp)
  38.  
  39. free_men = [x for x in range(n)]    # List of free men
  40. women_hus = [-1] * n    # List of pairs. Index = woman idx, Value = man idx or -1 if she is free
  41.  
  42. while len(free_men) > 0:    # While free man exists
  43.     tmp = free_men.copy()    # Temporary list because need to change len(free_men)
  44.     for m_idx in tmp:
  45.         w_idx = m[m_idx][0]    # The best woman for m_idx
  46.         cur = women_hus[w_idx]    # Current man for w_idx
  47.        
  48.         if cur == -1:    # She is free
  49.             women_hus[w_idx] = m_idx    # m_idx - man for w_idx
  50.             free_men.remove(m_idx)     # Remove m_idx from free men
  51.         elif w[w_idx].index(m_idx) < w[w_idx].index(cur):    # Her current man worse than m_idx
  52.             women_hus[w_idx] = m_idx    # m_idx - man for w_idx
  53.             free_men.remove(m_idx)    # m_idx not free
  54.             free_men.append(cur)    # Current man becomes free
  55.             m[cur].remove(w_idx)    # Remove w_idx from current man wish list
  56.         else:    # Her current man better than m_idx
  57.             m[m_idx].remove(w_idx)    # Remove w_idx from m_idx wish list
  58.            
  59. print('--------------------')
  60. print("Получившиеся пары (m, w):")
  61. for i in range(n):
  62.     print(f'{i + 1}: ({women_hus[i] + 1}, {i + 1})')
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top