1    # Nemes Tihamér OITV 2014
2    # Harmadik forduló II. korcsoport
3    # 2. feladat: Párosítás (22 pont)
4    # Két azonos létszámú csapat egyéni küzdelmet vív egymással, a te csapatod minden tagja az
5    # ellenfél egy másik tagjával mérkőzik párosításban. Két játékos közül mindig a nagyobb tudású
6    # győz. Ismerjük mindkét csapat tagjainak tudását.
7    # Készíts programot, amely megad egy olyan párosítást, amely esetén a csapatod a lehető
8    # legtöbbször győz!
9    # A standard bemenet első sora a csapattagok N számát (1≤N≤10000) tartalmazza. Mindkét csapat
10   # tagjait az 1,…,N számokkal azonosítjuk. A második sor pontosan N egész számot tartalmaz
11   # egy-egy szóközzel elválasztva, az i-edik szám a csapatod # i-edik tagjának Ai erőssége
12   # (1≤Ai≤100000). A harmadik sor is pontosan N egész számot tartalmaz egy-egy szóközzel
13   # elválasztva, az i-edik szám az ellenfél i-edik tagjának Bi erőssége (1≤Bi≤100000).
14   # A standard kimenet első sorába az elérhető győzelmek maximális számát kell írni! A második
15   # sor egy olyan párosítást adjon meg, amely maximális számú győzelmet eredményez csapatodnak!
16   # A sor pontosan N különböző egész számot tartalmazzon egy-egy szóközzel elválasztva, az i-edik
17   # szám az ellenfél csapatából annak a versenyzőnek a sorszáma legyen, aki a csapatod i-edik
18   # tagjával mérkőzik. Több megoldás esetén bármelyik megadható.
19   # Példa:
20   # bemenet                   kimenet
21   # 6             5
22   # 1 9 2 3 6 4           6 5 1 2 4 3
23   # 1 2 3 4 5 6
24   
25   
26   #MOHÓ STRATÉGIA
27   
28   #Párosítási feladat: Adott két csapat (saját és ellenfél) a csapattagok erősségével.
29   #Párosítsuk úgy a csapatunk tagjait az ellenféllel, hogy a lehető legtöbb győzelem jöjjön össze!
30   
31   #Adatbeolvasás a standard bemenetről...
32   tagszam=int(input('Csapattagok száma:'))
33   #Csapatnál és ellenfélnél is a sorszámot és az erősséget tároljuk együtt: (sorszám, erősség)
34   csapat=[(i,int(ero)) for i,ero in enumerate(input('Erősség:').strip().split(),1)]
35   ellenf=[(i,int(ero)) for i,ero in enumerate(input('Erősség:').strip().split(),1)]
36   
37   print('Rendezetlenül:\n',csapat,'\n',ellenf)
38   
39   #rendezés erősség szerint növekvő sorrendbe
40   csapat=sorted(csapat,key=lambda x:x[1])
41   ellenf=sorted(ellenf,key=lambda x:x[1])
42   
43   print('Erősség szerint rendezetten:\n',csapat,'\n',ellenf)
44   
45   parok=[0]*tagszam
46   db=0    #győzelmek száma     
47   
48   while len(csapat)>0:
49       if csapat[0][1]>ellenf[0][1]: 	#mohó választás
50           parok[csapat[0][0]-1]=ellenf[0][0]
51           ellenf.pop(0)
52           db+=1
53       else:
54           #nincs olyan ellenfél, akit le tudna győzni...
55           parok[csapat[0][0]-1]=ellenf[-1][0]
56           ellenf.pop(-1)
57   
58       csapat.pop(0)
59   
60   print('Maximális győzelmek száma: %d' %db)
61   print('Párosítás:\n',parok)
62   
63   
64