CSES - Tanssiaiset

Tanssiaisiin osallistuu n opiskelijaa Kumpulasta ja n opiskelijaa Viikistä. Molempien kampusten opiskelijat on numeroitu 1,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?

Voit olettaa, että n on enintään 50 ja luokan metodeita kutsutaan enintään 100 kertaa.

Python

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

  • konstruktori, jolle annetaan määrä n
  • add_pair määrittää, että Kumpulan opiskelija a ja Viikin opiskelija b suostuvat tanssimaan keskenään
  • calculate ilmoittaa suurimman mahdollisen tanssiparien määrän
class Ball:
    def __init__(self,n):
        # TODO

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

    def calculate(self):
        # TODO

if __name__ == "__main__":
    b = Ball(4)
    print(b.calculate()) # 0
    b.add_pair(1,2)
    print(b.calculate()) # 1
    b.add_pair(1,3)
    b.add_pair(3,2)
    print(b.calculate()) # 2

Java

Toteuta tiedostoon Ball.java luokka Ball, jossa on seuraavat metodit:

  • konstruktori, jolle annetaan määrä n
  • addPair määrittää, että Kumpulan opiskelija a ja Viikin opiskelija b suostuvat tanssimaan keskenään
  • calculate ilmoittaa suurimman mahdollisen tanssiparien määrän
public class Ball {
    public Ball(int n) {
        // TODO
    }

    public void addPair(int a, int b) {
        // TODO
    }

    public int calculate() {
        // TODO
    }

    public static void main(String[] args) {
        Ball b = new Ball(4);
        System.out.println(b.calculate()); // 0
        b.addPair(1,2);
        System.out.println(b.calculate()); // 1
        b.addPair(1,3);
        b.addPair(3,2);
        System.out.println(b.calculate()); // 2
    }
}