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 + ")";
    } 
}