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.