# Problem 'Greedy Santa'

**URL:** <https://forum.olinfo.it/t/problem-greedy-santa/6501>\
**Category:** Olimpiadi\
**Created:** [17 Gennaio 2021, 5:28pm UTC](https://forum.olinfo.it/t/problem-greedy-santa/6501 "2021-01-17T17:28:27Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Leyonad](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/3bc359/32.png) [@Leyonad](https://forum.olinfo.it/u/Leyonad)\
**Post date:** [17 Gennaio 2021, 5:28pm UTC](https://forum.olinfo.it/t/problem-greedy-santa/6501/1 "2021-01-17T17:28:27Z")

</div>

Good evening. On Subtask 2 (N \<= 20), on three tasks, I get the wrong output. Otherwise all outputs are correct.  
Does anyone know what could be the reason for this?

```auto
    #include <stdio.h>
    #include <assert.h>
    #include <bits/stdc++.h>
    using namespace std;

    // constraints
    #define MAXN 10000

    // input data
    int N, B, s, i, j, answer, sum;
    int V[MAXN];

    int main() {
    	answer, sum = 0;
        assert(2 == scanf("%d%d", &N, &B));
        for(s = 0; s < N; s++){
        	assert(1 == scanf("%d", &V[s]));
        	answer += V[s];
    	}
        // insert your code here
        if(answer < B){
        	printf("%d", answer); // print result
    	}
        else{
        	sort(V, V + N);
        	sum = V[N-1];
        	for(int j = N-1, i = j-1; j >= 0;){
    			while(V[j] > B){
                    sum = V[j];
        			j--;
    				i--;
    				//cout << "SWITCH j = "<< j << " i = "<< i << " sum = " << sum << endl;
    			}
    			if(sum == B){
    				answer = sum;
    				break;
    			}
        		sum += V[i];
        		//cout << "SUM = " << sum << endl;
        		if(sum >= B){
        			if(sum < answer){
        				answer = sum;
        				//cout << "NEW HIGHEST = " << answer << endl;
        				if(answer == B){
        					break;
    					}
    				}
    				sum -= V[i];
    				//cout << "SUM = " << sum << endl;
    			}
    			if(i <= 0){
    				j--;
    				i = j-1;
    				sum = V[j];
    				//cout << "SWITCH j = "<< j << " i = "<< i << " sum = " << sum << endl;
    				//cout << "SUM = " << sum << endl;
    			}else{
    				i--;
    			}
    		}
    		printf("%d", answer); // print result
    	}
        return 0;
    }

```

---

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [18 Gennaio 2021, 10:11am UTC](https://forum.olinfo.it/t/problem-greedy-santa/6501/2 "2021-01-18T10:11:11Z")

</div>

> [@Leyonad](#):
>
> On Subtask 2 (N \<= 20), on three tasks, I get the wrong output.

On the scoring paragraph, on subtask 2 it say: " The cost of all the gifts is either 1 or 2 ".  
Try troubleshooting on this case

Can u explain the code?

---

<div class="post-metadata">

**Author:** ![Leyonad](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/3bc359/32.png) [@Leyonad](https://forum.olinfo.it/u/Leyonad)\
**Post date:** [18 Gennaio 2021, 12:58pm UTC](https://forum.olinfo.it/t/problem-greedy-santa/6501/3 "2021-01-18T12:58:59Z")

</div>

Oh sorry, i mean Subtask 3.  
How my code works:  
Step 1:  
First I sort the array. Then I set `j` to the last (largest) element and `i` to the last but one. If the last element is larger than `B`, j and `i` are decreased until an element is found that is smaller than `B` or until j is `0`. If no element is found that is smaller than `B`, the result is the lowest number. This saves time.

Step 2:  
If a number is smaller than `B`, the `i-th` number is added with the found number.  
If the sum is a new minimum that is greater than or equal to `B`, this sum becomes the new minimum. Then the `i-th` number is subtracted again and `i` is decreased by `1` to possibly find an even smaller minimum, which is greater than or equal to `B`.  
But if the sum of the `j-th` element and the `i-th` element is less than `B`, the sum is kept and i is decreased again by `1`. Then it is asked again if the new sum is greater than or equal to `B`. If it is, the `i-th` element is subtracted and `i` is decreased.  
This continues until `B` is found or `i` is `0`. If `i` is `0`, `j` is decreased by `1` and i is set `j-1`.  
Step 2 is repeated until `B` is found or `j` is `0`. If `j` is `0`, the minimum sum greater than `B` is output.