Polut

Tehtäväsi on muodostaa syklitön suunnattu verkko, jossa on $100$ solmua ja tasan $x$ erilaista polkua solmusta $1$ solmuun $100$. Verkossa saa olla korkeintaan $1000$ kaarta ja jokaisen kaaren tulee olla erilainen.

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

• $1 \rightarrow 3 \rightarrow 100$
  
• $1 \rightarrow 3 \rightarrow 2 \rightarrow 100$
  
• $1 \rightarrow 5 \rightarrow 2 \rightarrow 100$
  
• $1 \rightarrow 5 \rightarrow 3 \rightarrow 100$
  
• $1 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 100$
  

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

Python

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))

Java

Toteuta tiedostoon Paths.java metodi create, joka palauttaa verkon rakenteen listana kaaria Edge-olioina.

import java.util.*;

public class Paths {
    ArrayList<Edge> create(int x) {
        // TODO
    }

    public static void main(String[] args) {
        Paths p = new Paths();
        System.out.println(p.create(2)); // esim. [(1,2),(1,100),(2,100)]
        System.out.println(p.create(5));
        System.out.println(p.create(10));
        System.out.println(p.create(123456789));
    }
}

Luokka Edge on toteutettu seuraavasti ja se on valmiina palvelimella, eli koodisi voi olettaa, että tällainen luokka on olemassa.

public class Edge {
    int a, b;

    public Edge(int a, int b) {
        this.a = a;
        this.b = b;
    }

    public String toString() {
        return "(" + a + "," + b + ")";
    } 
}