View difference between Paste ID: HYyvTDJA and PENCiv5F

-ZADANIE
+
 
 - |E,e|, obcięcie multizbioru E do pierwszych e elementów zapisanych w kolejności niemalejącej, np.
 
- - |E,e|, obcięcie multizbioru E do pierwszych e elementów zapisanych w kolejności niemalejącej, np.
+ |{0,3,2,2,0} , 3| = |{0,0,2,2,3},3| = {0,0,2},
 
- |{0,3,2,2,0},3|=|{0,0,2,2,3},3|={0,0,2},
+- [E,F,G,e], suma alternatywna z obcięciem multizbiorów E oraz F, albo E oraz G, taka, że:
 
- - [E,F,G,e], suma alternatywna z obcięciem multizbiorów E oraz F, albo E oraz G, taka, że:
+
 
 [E,F,G,e]=|E+G,e|, jeżeli suma elementów multizbioru E jest nieparzysta,
 
 gdzie + jest klasycznym operatorem sumy multizbiorów, np.
 
 [{0,2},{1,2},{0,3},3]=|{0,2}+{1,2},3|=|{0,2,1,2},3|=|{0,1,2,2},3|={0,1,2}.
 
 Dalej jest X={x(0), x(1), …, x(n-1)} jest rodziną n niepustych multizbiorów nad zbiorem liczb naturalnych oraz m jest pewną ustaloną dodatnią liczbą naturalną. Wyznacz sumę elementów multizbioru będącego rezultatem k-krotnego złożenia operatora sumy alternatywnej z obcięciem na zbiorze pustym {}, takiego, że
 
 […[[{},x(i_0),x(j_0),m],x(i_1),x(j_1),m]…,x(i_(k-1)),x(j_(k-1)),m],
 
 gdzie 0<=i_p,j_q<n, dla 0<=p,q<k. Dodatkowo podaj liczbę różnych elementów multizbioru będącego rezultatem tego złożenia.
 
 
 
 WEJŚCIE
 
 Wiersz zawierający liczby n, m oraz k oddzielone znakiem odstępu (kod ASCII 32) i zakończony znakiem nowej linii (kod ASCII 10). Następnie n wierszy reprezentujących elementy kolejnych multizbiorów x(i), dla 0<=i<n, poprzedzone liczbą określającą rozmiar danego multizbioru oraz znakiem odstępu. Elementy wierszy rozdzielone są znakiem odstępu, a każdy wiersz zakończony jest znakiem nowej linii. Dalej k wierszy reprezentujący pary indeksów multizbiorów należących do rodziny X odpowiadające kolejności ich występowania w rozważanym złożeniu operatora sumy alternatywnej z obcięciem (czytane od lewej do prawej strony). Elementy wierszy rozdzielone są znakiem odstępu, a każdy wiersz zakończony jest znakiem nowej linii.
 
 
 WYJŚCIE
 
 Wiersz zawierający dwie liczby naturalne oddzielone znakiem odstępu stanowiące rozwiązanie problemu.
 
 OGRANICZENIA
 
 Liczby n i m zawarte w przedziałach odpowiednio [1,10^3] i [1,10^7].  Krotność k analizowanego złożenia ograniczona od dołu przez 1 i od góry przez 10^7. Rozmiar multizbiorów z rodziny X oraz wartość maksymalnego elementu należącego do wymienionych multizbiorów ograniczone przedziałami kolejno [1,10^4] i [0,10^7].
 
 
 LIMITY
 
 Złożoność czasowa i pamięciowa ograniczone możliwością poprawnego wykonania rozwiązania na platformie SPOX :-)
 
 PRZYKŁAD 1
 
 wejście:
 
 3 5 4
 
 1 1
 5 0 8 5 8 9
 5 1 0 3 1 2
 0 1
 1 0
 0 2
 2 1
 
 wyjście:
 
 8 3
 
 KOMENTARZ DO ROZWIĄZANIA
 
 Zgodnie z danymi wejściowymi zachodzi
 
 x(0)={1}
 
 x(1)={0,8,5,8,9}
 
 x{2}={1,0,3,1,2}
 
 Dalej, rozważane 4 krotne złożenie operatora sumy alternatywnej z obcięciem na zbiorze pustym, gdzie m=5, ma postać:
 
 krok nr 1: [{},x{0},x{1},5]=|{}+x{0},5|={1}
 
 krok nr 2: [{1},x{1},x{0},5]=|{1}+x{0},5|={1,1}
 
 krok nr 3: [{1,1},x{0},x{2},5|=|{1,1}+x{0},5|={1,1,1}
 
 krok nr 4: [{1,1,1},x{2},x{1},5|=|{1,1,1}+x{1},5|=|{0,1,1,1,5,8,8,9},5|={0,1,1,1,5}
 
 Stąd suma elementów multizbioru będącego rezultatem rozważanego złożenia jest równa 8, a sam multizbiór składa się z elementów o trzech różnych wartościach.
 
 Zatem odpowiedź stanowi dwójka liczb 8 oraz 3.
 
 PRZYKŁAD 2
 
 wejście:
 
 6 10 10
 
 7 9 9 7 3 9 3 1
 4 6 8 5 2
 7 8 6 9 6 7 3 1
 4 1 9 0 3
 9 9 8 8 8 6 4 3 3 6
 4 1 9 5 6
-/*
+
 1 4
 1 4
 0 4
 5 4
 3 4
 1 5
 4 1
 4 5
 5 4
 
 wyjście:
 
 22 3
 
 PRZYKŁAD 3
 
 wejście:
 
 12 20 20
 
 20 1 8 4 5 8 7 3 8 3 1 4 1 2 9 3 9 3 8 4 6
 4 2 2 7 2
 16 0 1 9 1 8 7 4 1 7 7 5 9 9 5 2 1
 20 7 6 4 0 8 1 3 9 8 1 8 7 3 6 6 9 5 9 6 6
 15 7 4 2 7 9 6 7 6 3 9 8 3 5 8 0
 12 1 4 9 1 9 8 9 5 0 6 7 9
 12 5 2 1 6 7 2 9 4 9 4 5 9
 7 3 7 9 6 9 8 8
 9 8 1 7 9 9 4 8 7 5
 10 6 1 2 0 2 0 2 1 0 7
 3 5 1 8
 1 0
 1 11
 7 1
 2 5
 8 6
 11 0
 9 9
 7 9
 4 1
 0 3
 5 10
 9 7
 6 10
 9 3
 8 9
 5 1
 2 10
 8 8
 7 2
 9 1
 6 4
 
 wyjście:
 
 0 1