Riječi sa različitim slovima
Opis zadatka:
Dat je uređen niz od 10 slova
S = (A, B, C, D, E, F, G, H, I, J).
Od ovih slova pravimo riječi u kojima se slova ne ponavljaju. Za jednu takvu riječ kažemo
da je manja od neke druge takve riječi sa istim brojem slova, ako se nalazi ispred nje po
leksikografskom poretku. Leksikografski poredak znači sljedeće: upoređujemo, s lijeva na desno,
slovo po slovo prve riječi sa slovima druge riječi. Kada naiđemo na prvo slovo koje se
razlikuje u te dvije riječi, onda kažemo da je prva riječ manja od druge ako se nađeno
slovo prve riječi nalazi ispred odgovarajućeg slova druge riječi u datom nizu S.
Ulazna datoteka sadrži cijeli broj D <= 10 i on govori koliko prvih
slova iz niza S se uzima u obzir. Na primjer, za
D = 7 slova H, I i J se ne uzimaju u razmatranje.
Drugi cijeli broj K, u ulaznoj datoteci, govori kolika je dužina riječi koje se
razmatraju. Na primjer, za k = 4 razmatraju se riječi od 4 slova. Za naš
primjer, prva riječ je ABCD, druga ABCE, treća ABCF, zatim slijede ABCG, ABEC, ABEF, ABEG,
ABFC, ABFE, ABFG itd.
Napisati program koji iz ulazne datoteke čita cijele brojeve D (broj slova od kojih se prave
riječi), K (dužina riječi koje se razmatraju) i N, i koji zatim
određuje N-tu riječ sa različitim slovima u leksikografskom poretku svih
riječi koje imaju dužinu od K slova, a pisane su samo sa prvih
D slova iz niza S. Također treba izračunati koliko ukupno ima riječi sa
različitim slovima, koje su napisane sa K slova, gdje se slova mogu birati
u nizu od D mogućih slova.
Ulazna datoteka:
Ulazi podaci se nalaze u tekstualnoj datoteci pod imenom RIJEC.IN. U prvom redu se
nalazi cijeli broj D koji govori koliko se prvih slova iz niza S uzima u razmatranje.
U drugom redu se nalazi cijeli broj k koji govori od koliko se slova sastoje riječi.
Pri tome vrijedi k <= D. U trećem redu se nalazi cijeli broj N.
Izlazna datoteka:
Vaš program u prvom redu izlazne datoteke pod imenom RIJEC.OUT, treba da napiše
N-tu riječi sa različitim slovima u leksikografskom poretku među svim riječima
dužine od K slova i koje se pišu sa D prvih slova u nizu N, ako
takva postoji. Ako tražena riječ ne postoji, u prvom redu izlazne datoteke treba da stoji
samo znak "-". U drugom redu treba da piše ukupni broj riječi sa traženim osobinama za
zadano d i k.
Vremensko ograničenje:
Za svaki testni primjer program treba da ponudi rješenje za najviše 10 sekundi.
Primjeri:
RIJEC.IN
7
4
314
RIJEC.OUT
CEFB
840
Objašnjenje: Koriste se slova (A,B,C,D,E,F,G), razmatraju se riječi dužine 4, i traži se
314-ta riječ sa zadanim osobinama. Ta riječ je CEFB, a ima ukupno 840 riječi sa traženim
osobinama.