• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Oct 20th, 2019 125 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from collections import defaultdict
2. import random
3.
4.
5. def programming_team_selection():
6.     while True:
7.         n_pairs = int(input())
8.         if n_pairs == 0:
9.             return
11.         for i in range(n_pairs):
12.             s1, s2 = input().split()
16.             print("possible")
17.         else:
18.             print("impossible")
19.
20.
21. def find_teamless(has_team):
22.     keys = list(has_team.keys())
23.     random.shuffle(keys)
24.     for key in keys:
25.         if has_team[key] == False:
26.             return key
27.     return None
28.
29.
31.     #def print(x):
32.     #    pass
33.     #print("====== New Test Case ======")
35.     def local_recurrer(used, teams):
36.         #print("Recursion with:")
37.         #print(used)
38.         #print(teams)
39.         # find first unused guy, he's the team captain ;)
40.         captain = find_teamless(used)
41.         # if there isn't one, everyone has a clique and we're happy
42.         if captain is None:
43.             return True
44.         used[captain] = True
45.         #print(f"The captain is {captain}")
46.
47.         # otherwise we have to fill the team
49.             if used[lieutenant]:
50.                 continue
51.             used[lieutenant] = True
52.             # ok, we have a possible second guy
54.                 if used[third_guy] or third_guy not in adj_list[lieutenant]:
55.                     continue
56.                 used[third_guy] = True
57.                 # and a possible third guy
58.                 teams.append([captain, lieutenant, third_guy])
59.                 if local_recurrer(used, teams):
60.                     return True
61.                 used[third_guy] = False
62.                 teams.remove([captain, lieutenant, third_guy])
63.             used[lieutenant] = False
64.         #print("Got stuck!")
65.         used[captain] = False
66.         return False
67.
68.     teams = []
69.     used = {name: False for name in adj_list.keys()}
70.     result = local_recurrer(used, teams)
71.     if result:
72.         print(teams)
73.         return teams
74.     else:
75.         return None
76.
77.
78. def main():
79.     programming_team_selection()
80.
81.
82. if __name__ == '__main__':
83.     main()
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.

Top