CSES - Etäisyydet

Annettuna on lista, jossa on nn eri kokonaislukua. Tehtäväsi on selvittää, mikä on kk:nneksi pienin kahden luvun etäisyys, kun tarkastellaan kaikkia mahdollisia lukupareja.

Esimerkiksi kun lista on [4,1,5,2][4,1,5,2], etäisyydet ovat seuraavat pienimmästä suurimpaan:

  • lukujen 11 ja 22 etäisyys on 11
  • lukujen 44 ja 55 etäisyys on 11
  • lukujen 22 ja 44 etäisyys on 22
  • lukujen 11 ja 44 etäisyys on 33
  • lukujen 22 ja 55 etäisyys on 33
  • lukujen 11 ja 55 etäisyys on 44

Voit olettaa, että nn on enintään 10510^5, jokainen luku on välillä 11091 \dots 10^9 ja kk on enintään 10510^5.

Python

Toteuta tiedostoon distances.py funktio find, joka palauttaa halutun etäisyyden.

def find(t, k):
    # TODO

if __name__ == "__main__":
    t = [4,1,5,2]
    print(find(t,1)) # 1
    print(find(t,2)) # 1
    print(find(t,3)) # 2
    print(find(t,4)) # 3
    print(find(t,5)) # 3
    print(find(t,6)) # 4

Java

Toteuta tiedostoon Distances.java metodi find, joka palauttaa halutun etäisyyden.

public class Distances {
    public int find(int[] t, int k) {
        // TODO
    }

    public static void main(String[] args) {
        Distances d = new Distances();
        int[] t = {1,2,4,5};
        System.out.println(d.find(t,1)); // 1
        System.out.println(d.find(t,2)); // 1
        System.out.println(d.find(t,3)); // 2
        System.out.println(d.find(t,4)); // 3
        System.out.println(d.find(t,5)); // 3
        System.out.println(d.find(t,6)); // 4
    }
}