CSES - Polut

Tehtäväsi on muodostaa syklitön suunnattu verkko, jossa on 100100 solmua ja tasan xx erilaista polkua solmusta 11 solmuun 100100. Verkossa saa olla korkeintaan 10001000 kaarta ja jokaisen kaaren tulee olla erilainen.

Esimerkiksi kun x=5x=5, yksi mahdollinen ratkaisu muodostuu kaarista (1,3),(1,5),(2,100),(3,2),(3,100),(5,2),(5,3).(1,3),(1,5),(2,100),(3,2),(3,100),(5,2),(5,3). Tässä tapauksessa polut ovat seuraavat:

  • 131001 \rightarrow 3 \rightarrow 100
  • 1321001 \rightarrow 3 \rightarrow 2 \rightarrow 100
  • 1521001 \rightarrow 5 \rightarrow 2 \rightarrow 100
  • 1531001 \rightarrow 5 \rightarrow 3 \rightarrow 100
  • 15321001 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 100

Voit olettaa, että xx on kokonaisluku välillä 11091 \dots 10^9. Voit muodostaa minkä tahansa verkon, joka täyttää yllä olevat vaatimukset.

Toteuta tiedostoon paths.py funktio create, joka palauttaa verkon rakenteen listana kaaria tupleina.

def create(x):
    #TODO

if __name__ == "__main__":
    print(create(2)) # esim. [(1,2),(1,100),(2,100)]
    print(create(5))
    print(create(10))
    print(create(123456789))