CSES - Tanssiaiset

Tanssiaisiin osallistuu nn opiskelijaa Kumpulasta ja nn opiskelijaa Viikistä. Molempien kampusten opiskelijat on numeroitu 1,2,,n1,2,\dots,n.

Jokaisessa tanssiparissa toinen opiskelija on Kumpulasta ja toinen Viikistä, ja tiedät kaikki parit, jotka suostuvat tanssimaan keskenään. Jokainen opiskelija voi kuulua enintään yhteen tanssipariin. Mikä on suurin määrä pareja, jotka on mahdollista muodostaa?

Toteuta tiedostoon ball.py luokka Ball, jossa on seuraavat metodit:

  • add_pair määrittää, että Kumpulan opiskelija aa ja Viikin opiskelija bb suostuvat tanssimaan keskenään
  • max_pairs ilmoittaa suurimman mahdollisen tanssiparien määrän
class Ball:
    def __init__(self, n):
        # TODO

    def add_pair(self, a, b):
        # TODO

    def max_pairs(self):
        # TODO

if __name__ == "__main__":
    ball = Ball(4)

    print(ball.max_pairs()) # 0

    ball.add_pair(1, 2)
    print(ball.max_pairs()) # 1

    ball.add_pair(1, 3)
    ball.add_pair(3, 2)
    print(ball.max_pairs()) # 2

    ball.add_pair(2, 1)
    print(ball.max_pairs()) # 3

Yllä olevassa esimerkissä lopputilanteessa voidaan muodostaa seuraavat parit:

  • Kumpulan opiskelija 11 tanssii Viikin opiskelijan 33 kanssa
  • Kumpulan opiskelija 22 tanssii Viikin opiskelijan 11 kanssa
  • Kumpulan opiskelija 33 tanssii Viikin opiskelijan 22 kanssa

Huomaa, että molemmilla kampuksilla on nn opiskelijaa. Esimerkiksi Kumpulan opiskelija 11 ja Viikin opiskelija 11 ovat kaksi eri opiskelijaa.