W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Multizbiorem nazywamy obiekt matematyczny podobny do zbioru, w którym jednak ten sam element może występować wielokrotnie. Podobnie jak w przypadku zbioru, także dla multizbioru wszystkie elementy można ustawić w ciąg i to zazwyczaj na wiele sposobów; każde takie ustawienie nazywamy permutacją multizbioru. Dla przykładu, permutacjami multizbioru są między innymi oraz .
Powiemy, że jedna permutacja danego multizbioru jest mniejsza (w porządku leksykograficznym) od drugiej, jeżeli na pierwszej pozycji, na której te permutacje się różnią, pierwsza z nich zawiera element mniejszy niż druga. Wszystkie permutacje danego multizbioru można ponumerować (zaczynając od jedynki) w kolejności od najmniejszej do największej.
Napisz program, który:
Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem. Oznaczają one odpowiednio liczbę elementów multizbioru oraz ... liczbę . Drugi wiersz wejścia zawiera dodatnich liczb całkowitych (), pooddzielanych pojedynczymi odstępami i oznaczających kolejne elementy danej permutacji multizbioru.
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą resztę z dzielenia przez numeru podanej permutacji w porządku leksykograficznym.
Dla danych wejściowych:
4 1000 2 1 10 2
poprawną odpowiedzią jest:
5
Wszystkie permutacje mniejsze od zadanej to (w kolejności leksykograficznej): , , oraz .
Autor zadania: Jakub Radoszewski.