CSES - Planeetat

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

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

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ä?

Toteuta luokka Planets, jossa on seuraavat metodit:

  • add_teleport lisää teleportin planeetalta aa planeetalle bb
  • calculate ilmoittaa pienimmän poistettavien teleporttien määrän

Toteuta luokka tiedostoon planets.py seuraavan esimerkin mukaisesti.

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