Cześć
Mam zadanko, próbuje je zrobić ale wyskakuje mi błąd gdy oddaje pracę:
ZADANIE
Rozważmy zbiór wszystkich możliwych multizbiorów nad zbiorem liczb naturalnych. Definiujemy dwa operatory dla tak określonej dziedziny:
- |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},
- [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+F,e|, jeżeli suma elementów multizbioru E jest parzysta,
[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,103] i [1,107]. Krotność k analizowanego złożenia ograniczona od dołu przez 1 i od góry przez 107. Rozmiar multizbiorów z rodziny X oraz wartość maksymalnego elementu należącego do wymienionych multizbiorów ograniczone przedziałami kolejno [1,104] 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 3
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
MOJE BLEDNĘ ROZWIĄZANEI
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int m;
public static int[] zlaczenie(int[] y1, int[] y2) {
int[] al = new int[y1.length + y2.length];
for(int i = 0; i < y1.length; i++) {
al[i] = y1[i];
//if(i < y2.length) al[i+y1.length] = y2[i];
}
for(int i = y1.length; i < y1.length+y2.length; i++) {
al[i] = y2[i-y1.length];
}
Arrays.sort(al);
int max = m > al.length ? al.length : m;
int[] wynik = new int[max];
for(int i = 0; i < max; i++) wynik[i] = al[i];
return wynik;
}
public static int[] obciecie(int x1[], int x2[], int x3[]) {
int suma = 0;
for(int i = 0; i < x1.length; i++) {
suma += x1[i];
}
if(suma % 2 == 0) {
return zlaczenie(x1, x2);
} else {
return zlaczenie(x1, x3);
}
}
public static void main(String[] args) {
//long startTime = System.currentTimeMillis();
Scanner scan = new Scanner(System.in);
/*FileReader fr = null;
try {
fr = new FileReader(new File("F:/Moje programy/asd.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner scan = new Scanner(fr);*/
int n = scan.nextInt();
m = scan.nextInt();
int k = scan.nextInt();
int[][] zbiory = new int[n][];
for(int i = 0; i < n; i++) {
int t = scan.nextInt();
zbiory[i] = new int[t];
for(int j = 0; j < t; j++) {
zbiory[i][j] = scan.nextInt();
}
}
int[] out = new int[0];
for(int i = 0; i < k; i++) {
//out = obciecie(out, zbiory[scan.nextInt()], zbiory[scan.nextInt()]);
int suma = 0;
for(int j = 0; j < out.length; j++) {
suma += out[j];
}
if(suma % 2 == 0) {
out = zlaczenie(out, zbiory[scan.nextInt()]);
scan.nextInt();
} else {
scan.nextInt();
out = zlaczenie(out, zbiory[scan.nextInt()]);
}
}
int wynik1 = 0;
int wynik2 = 0;
for(int i = 0; i < out.length; i++) {
wynik1 += out[i];
if(i == 0 || out[i] != out[i-1]) wynik2++;
}
System.out.println(wynik1 + " " + wynik2);
//System.out.println((new Date()).getTime() - startTime);
}
}