Pelissä on $n$ planeettaa, jotka on numeroitu $1,2,\dots,n$. Pelaaja aloittaa planeetalta $1$ ja voittaa pelin, kun pääsee planeetalle $n$.

Planeettojen välillä voi liikkua teleporteilla. Jokainen teleportti voidaan kuvata parilla $(a,b)$, missä $a<b$: teleportti vie planeetalta $a$ planeetalle $b$.

Olet päässyt pelin läpi itse, mutta haluat estää, että kukaan voi enää voittaa peliä. Montako teleporttia sinun tulee poistaa vähintään pelistä?

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

Python

Toteuta tiedostoon planets.py luokka Planets, jossa on seuraavat metodit:

• konstruktori, jolle annetaan määrä $n$
• add_teleport lisää teleportin planeetalta $a$ planeetalle $b$
• calculate ilmoittaa pienimmän poistettavien teleporttien määrän

class Planets:
    def __init__(self,n):
        # TODO

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

    def calculate(self):
        # TODO

if __name__ == "__main__":
    p = Planets(5)
    print(p.calculate()) # 0
    p.add_teleport(1,2)
    p.add_teleport(2,5)
    print(p.calculate()) # 1
    p.add_teleport(1,5)
    print(p.calculate()) # 2

Java

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

• konstruktori, jolle annetaan määrä $n$
• addTeleport lisää teleportin planeetalta $a$ planeetalle $b$
• calculate ilmoittaa pienimmän poistettavan teleporttien määrän

public class Planets {
    public Planets(int n) {
        // TODO
    }

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

    public int calculate() {
        // TODO
    }

    public static void main(String[] args) {
        Planets p = new Planets(5);
        System.out.println(p.calculate()); // 0
        p.addTeleport(1,2);
        p.addTeleport(2,5);
        System.out.println(p.calculate()); // 1
        p.addTeleport(1,5);
        System.out.println(p.calculate()); // 2
    }
}