Prepogosto
Objavljeno: Če Jun 08, 2017 1:42 pm
Podan imamo seznam N števil, v katerem se nekatera števila pojavijo večkrat. Obdržali bi radi samo zadnjih K pojavitev (gledano od leve proti desni) istega števila, ostale pa želimo izbrisati. Napisati morate program, ki bo učinkovito izračunal, kakšen je novonastali seznam.
Naloga
Začetni seznam je zelo dolg, zato je podan v obliki generatorja seznama. Podani sta prvo in drugo število v seznamu (tj. števili [math]) ter pravilo za izračun naslednjih členov seznama: [math].
Napišite program, ki se bo znebil prepogostih števil in izpisal preostanek seznama od mest A do B.
Opozorila:
Bodite pozorni na količino (razpoložljivega) pomnilnika!
Omejitve
Čas: 10 s
Spomin: 512 MB
Vhodni podatki
V prvi vrstici se nahajata celi števili N in K. V drugi vrstici so podani parametri za generiranje seznama: [math] X, Y in M. Tretja vrstica pa vsebuje števili A in B, ki definirata izpis.
Omejitve vhodnih podatkov
1≤N≤70000000
1≤K,M≤1000000
0≤[math]<M
1≤A≤B
V seznamu bo ostalo najmanj B števil.
0≤B−A≤100
Izhodni podatki
Izpišite s presledki ločena števila, ki se v končnem seznamu nahajajo od mesta A do B.
Primer vhoda
Pripadajoč izhod
Komentar
Seznam števil opisan v testnem primeru je [6, 1, 5, 0, 7, 10, 7, 11, 1, 12, 10, 1, 8, 8, 10, 11, 0, 5, 9, 5]. Če obdržimo samo zadnje prepogoste pojavitve števil, dobimo seznam [6, 0, 7, 7, 11, 1, 12, 10, 1, 8, 8, 10, 11, 0, 5, 9, 5]. Ko izpišemo elemente od 2. do 6. mesta, dobimo iskan rezultat.
Naloga
Začetni seznam je zelo dolg, zato je podan v obliki generatorja seznama. Podani sta prvo in drugo število v seznamu (tj. števili [math]) ter pravilo za izračun naslednjih členov seznama: [math].
Napišite program, ki se bo znebil prepogostih števil in izpisal preostanek seznama od mest A do B.
Opozorila:
Bodite pozorni na količino (razpoložljivega) pomnilnika!
Omejitve
Čas: 10 s
Spomin: 512 MB
Vhodni podatki
V prvi vrstici se nahajata celi števili N in K. V drugi vrstici so podani parametri za generiranje seznama: [math] X, Y in M. Tretja vrstica pa vsebuje števili A in B, ki definirata izpis.
Omejitve vhodnih podatkov
1≤N≤70000000
1≤K,M≤1000000
0≤[math]<M
1≤A≤B
V seznamu bo ostalo najmanj B števil.
0≤B−A≤100
Izhodni podatki
Izpišite s presledki ločena števila, ki se v končnem seznamu nahajajo od mesta A do B.
Primer vhoda
Koda: Izberi vse
20 2
6 1 4 7 13
2 6
Pripadajoč izhod
Koda: Izberi vse
0 7 7 11 1
Komentar
Seznam števil opisan v testnem primeru je [6, 1, 5, 0, 7, 10, 7, 11, 1, 12, 10, 1, 8, 8, 10, 11, 0, 5, 9, 5]. Če obdržimo samo zadnje prepogoste pojavitve števil, dobimo seznam [6, 0, 7, 7, 11, 1, 12, 10, 1, 8, 8, 10, 11, 0, 5, 9, 5]. Ko izpišemo elemente od 2. do 6. mesta, dobimo iskan rezultat.