Zadanie z treningu do OIG

Jest N stosów żetonów, znana jest liczba żetonów w każdym ze stosów. Gracz ma zebrać jak największą liczbę żetonów. W jednym ruchu bierze jeden dowolny stos. Dwóch graczy wykonuje ruchy na przemian.

Jeśli TY rozpoczniesz grę i oboje z przeciwnikiem zagracie optymalnie, czy będziesz w stanie zgarnąć przynajmniej K żetonów?

Dane: w pierwszej linii N i K, w drugiej linii liczby żetonów w kolejnych N stosach.

Strategia rozwiązania bazuje na algorytmie zachłannym: w każdym kroku podejmuj taką decyzję, która w bieżącej chwili wydaje się najkorzystniejsza.
Tu: należy zgarniać w każdym kroku największy możliwy stos.

Kroki algorytmu:

Wczytaj liczebności stosów do tablicy S

Posortuj tablicę S, czyli stosy, według liczebności żetonów, np. rosnąco

i = N-1; // bieżący element (największy) jest ostatnim elementem w tablicy S

moje = 0;

dopóki (moje<K oraz i>=0) powtarzaj:

moje = moje + S[i]; // Dodaję i-ty stos do tego co już mam

i = i-2; // Przesuwam się o 2 stosy w kierunku mniejszych stosów

// ponieważ stos o numerze i-1 weźmie przeciwnik

jeśli (moje>=K) zwróć „TAK” ; // Po zakończeniu pętli zwracam wynik
w przeciwnym razie zwróć „NIE”

Przykładowy kod programu i jego wykonanie:

int n,k

scanf("%d %d",&n, &k);

int S[100];

for (int i=0; i<n; i++) scanf("%d",&S[i]);

sort(S, S+n);

printf("\nposortowane:\n");

for (int i=0; i<n; i++) printf("%d ",S[i]);

printf("\n\n");

int i=n-1; // numer max stosu do wziecia

int moje=0;

while (moje<k && i>=0) {

moje += S[i];

printf("biore %d \n",S[i]);

i-=2;

}

if (moje>=k) printf("TAK\n"); else printf("NIE\n");}