Przedziały
Limit pamięci: 32 MB
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.
Komunikacja wejścia/wyjścia ze sprawdzaczką
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:
- wypisać na standardowe wyjście liczbę przedziałów zawierających się w ,
- wczytać ze standardowego wejścia liczbę całkowitą , ,
oznaczającą numerek wygenerowanego przedziału,
- wypisać dwie liczby całkowite i oddzielone pojedynczym odstępem oznaczające
wybrany przedział ,
- usunąć przedział ze zbioru .
Przykład
Dla danych wejściowych:
5
6
2
0
poprawną odpowiedzią jest:
15
2 3
4
4 5
1
1 1
Autor zadania: Jakub Pawlewicz.