1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>

int my_compare(const void* pierwszy,const void* drugi) {
	long a1 = *(long*) pierwszy;
	long a2 = *(long*) drugi;
	if (a1 > a2) { return -1;}
	return 1;
}

int check(int number,long* pck,long* prz,int nr_prz) {
	int* lista = (int*) malloc (sizeof(int)*nr_prz);
	int akt_prz = 0;
	int i = 0;
//for (int i=0;i<number;i++) { printf("%d ",pck[i]); printf("\n"); }
//for (int i=0;i<nr_prz;i++) { printf("%d ",prz[i]); printf("\n"); }
//printf("Numer: %d\n",number);
	while(1) {
//printf("%d\n",akt_prz);
//for (int k=0;k<number;k++) { printf("%d ",pck[k]);} printf("\n"); 
		if (akt_prz == nr_prz-1) {
			return(1);
		}
		if (akt_prz <= 0 and i == number) {
			return(0);
		}
		for ( ; i< number;i++) {
			if (pck[i] > prz[akt_prz]) {
				pck[i] -= prz[akt_prz];
				lista[akt_prz] = i;
				akt_prz++;
				i = 0;
				break;
			}
		}
		if (i == number) {
			akt_prz--;
			pck[ lista[akt_prz] ] += prz[akt_prz];
			i = lista[akt_prz]+1;
		}
	}
}

int main() {
	int przedmioty;
	int plecaki;
	scanf("%d",&przedmioty);
	scanf("%d",&plecaki);
	long* wagi_prz = (long*) malloc(sizeof(long)*przedmioty);
	long* wagi_pck = (long*) malloc(sizeof(long)*plecaki);
	for (int i=0;i<przedmioty;i++) { scanf("%ld",wagi_prz+i); }
	for (int i=0;i<plecaki;i++)    { scanf("%ld",wagi_pck+i); }

	qsort((void*)wagi_prz,przedmioty,sizeof(long*),my_compare);
	qsort((void*)wagi_pck,plecaki,sizeof(long*),my_compare);
	int suma_przedmiotow = 0;
	for (int i=0;i<przedmioty;i++) {suma_przedmiotow+=wagi_prz[i];}

	int min_plecak = 0; int pakownosc = suma_przedmiotow;
	for (int i=0;i<plecaki;i++) {
		min_plecak++;
		pakownosc -= wagi_pck[i];
		if (pakownosc < 0) { break; }
		if (min_plecak == plecaki) { printf("NIE\n"); return(0); }
	}

	for (int i=min_plecak;i<=plecaki;i++) {
		int wynik = check(i,wagi_pck,wagi_prz,przedmioty);
		if (wynik==1) { printf("%d\n",i); return(0); }
	}
	printf("NIE\n");
	return(0);
}