CSES - Lukujono

Lukujonon ensimmäinen alkio on 1. Tämän jälkeen jokainen alkio on kuvaus edellisestä alkiosta. Kuvaus saadaan kertomalla vasemmalta oikealle, montako kertaa mikäkin numero esiintyy luvussa peräkkäin.

Luvussa 1 on yksi ykkönen, joten sen kuvaus on 11. Luvussa 11 on kaksi ykköstä, joten sen kuvaus on 21. Luvussa 21 on ensin yksi kakkonen ja sitten yksi ykkönen, joten sen kuvaus on 1211. Luvussa 1211 on ensin yksi ykkönen (kuvataan 11), sitten yksi kakkonen (kuvataan 12) ja lopulta kaksi ykköstä (kuvataan 21), joten sen kuvaus on 111221.

Lukujonon ensimmäiset 6 alkiota ovat siis 1, 11, 21, 1211, 111221, 312211.

Tehtäväsi on selvittää, mikä on lukujonon kohdassa n oleva alkio. Voit olettaa, että n on enintään 30.

Python

Toteuta tiedostoon sequence.py funktio generate, joka palauttaa halutun alkion merkkijonona.

def generate(n):
    # TODO

if __name__ == "__main__":
    print(generate(1)) # 1
    print(generate(2)) # 11
    print(generate(3)) # 21
    print(generate(4)) # 1211
    print(generate(5)) # 111221

Java

Toteuta tiedostoon Sequence.java metodi generate, joka palauttaa halutun alkion merkkijonona.

public class Sequence {
    public String generate(int n) {
        // TODO
    }

    public static void main(String[] args) {
        Sequence s = new Sequence();
        System.out.println(s.generate(1)); // 1
        System.out.println(s.generate(2)); // 11
        System.out.println(s.generate(3)); // 21
        System.out.println(s.generate(4)); // 1211
        System.out.println(s.generate(5)); // 111221
    }
}