In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Dany jest zbiór liczb całkowitych .
Dla
i
całkowitych,
,
przedziałem
nazywamy zbiór kolejnych liczb całkowitych od
do
:
.
Rozbiciem zbioru
na przedziały nazywamy taki ciąg parami rozłącznych przedziałów,
że suma tych przedziałów daje zbiór
.
Twoim zadaniem jest napisać losowy generator rozbić zbioru na przedziały.
Generator będzie działał w sposób iteracyjny.
W danym momencie pamiętamy zbiór liczb całkowitych, które są w
,
a nie zostały użyte jeszcze w żadnym przedziale.
Zaczynamy od całego zbioru
.
Następnie w każdej iteracji losujemy jakiś przedział i usuwamy go ze zbioru.
Postępujemy tak dopóki pamiętany zbiór nie jest pusty.
Losowanie przedziału należy wykonać jak następuje.
Mamy pewien podzbiór zbioru .
Oznaczmy go przez
.
Wylosowany przedział musi się zawierać w
.
Numerujemy wszystkie przedziały, które się zawierają w
, od zera
w kolejności leksykograficznej względem początku i końca przedziału.
Np. dla
kolejne przedziały to:
i mają one odpowiednio numery
.
Wybór przedziału dokonujemy przez wylosowanie numerka.
Numerek losuje sprawdzaczka.
Twój program powinien działać według następującego schematu.
Najpierw należy wczytać jedną liczbę całkowitą ,
.
Następnie należy zainicjować
.
Teraz, dopóki
, należy wykonywać kolejne iteracje.
W pojedynczej iteracji należy:
Dla danych wejściowych:
5 6 2 0
poprawną odpowiedzią jest:
15 2 3 4 4 5 1 1 1
Autor zadania: Jakub Pawlewicz.